Calcolo Combinatorio

Note

Articles in this blog's slice are, for the time being, ony in italian.
Gli articoli in questa parte di blog sono, per ora, solo in italiano.

Introduzione al calcolo combinatorio

Il calcolo combinatorio studia il numero di modi in cui è possibile raggruppare, disporre od ordinare gli elementi di un insieme finito.

Funzione fattoriale

Definizione

$n$ fattoriale si esprime con $n!$ ed indica il prodotto dei primi $n$ numeri naturali, escluso lo zero. Siano $0! = 1$ e $1! = 1$, allora:

$n! = n(n-1)(n-2)(n-3)...\cdot 2 \cdot 1$ con $n \geq 2$

La definizione può essere espressa con una sorta di funzione ricorsiva:

$$n! = n \cdot (n-1)!$$

Coefficiente binomiale

Definizione

Siano $n, k \in \mathbb{N}$ e $0 < k \leq n$, il coefficiente binomiale di $n\;k$:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}= \frac{n(n-1) \cdots (n-k+1)}{k!}$$

Formula di ricorrenza

$$\binom{n}{k+1}=\binom{n}{k} \cdot \frac{n-k}{k+1}$$

La formula di ricorrenza è utile quando si conosce il valore del coefficiente binomiale per un dato valore di $k$ e si devono trovare i valori delle classi successive o precedenti.

Legge della classi complementari

$$\binom{n}{k}=\binom{n}{n-k}$$ Dimostrazione $$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!\cdot k!}=\frac{n!}{(n-k)![n-(n-k)]!}=\binom{n}{n-k}$$

Altre proprietà del coefficiente binomiale

$$\begin{equation} \begin{split} \binom{n}{0} = & \binom{n}{n} = 1 \\ \binom{n}{1} = & \binom{n}{n+1} = n \end{split} \end{equation}$$ $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ Dimostrazione $$\begin{equation} \begin{split} \binom{n-1}{k-1} + \binom{n-1}{k} & = \frac{(n-1)!}{(k-1)! \cdot(n-1-k+1)!} + \frac{(n-1)!}{k! (n-1-k)!} = \\ \\ & = (n-1)! \frac{k + n - k}{k! (n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k} \end{split} \end{equation}$$

Disposizioni

Disposizioni semplici

Definizione

Siano $n, k \in \mathbb{N}$ e $0 < k \leq n$, le disposizioni semplici di $n$ elementi di classe $k$ sono tutti i gruppi di $k$ elementi che differiscono per almeno un elemento o per l’ordine con cui gli elementi sono collocati.

$$D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot ... \cdot (n-k+1)$$

Questa espressione può essere semplificata utilizzando i numeri fattoriali:

$$D_{n,k} = \frac{n!}{(n-k)!}$$ Esempio $$\begin{align*} D_{7,3} = & 7 \cdot (7-1) \cdot (7-3+1) = 7\cdot 6 \cdot 5 = 210 \\ D_{7,3} = & \frac{7!}{4!} = \frac{7 \cdot 6 \cdot 5 \cdot 4!}{4!} = 7\cdot 6 \cdot 5 = 210 \end{align*}$$

Disposizioni con ripetizione

Definizione

Siano $n, k \in \mathbb{N}$ e $0 < k \leq n$, le disposizioni con ripetizione di $n$ elementi di classe $k$ sono tutti i gruppi di $k$ elementi che differiscono per almeno un elemento o per l’ordine con cui gli elementi sono collocati.

$$D'_{n,k} = n^k$$

Esempio:

$$D'_{22,3} = 22^3 = 10648$$

Permutazioni

Permutazioni semplici

Definizione

Sia $n \in \mathbb{N}, n \geq 2$, le permutazioni semplici di $n$ elementi sono tutti i gruppi formati dagli $n$ elementi che differiscono per il loro ordine.

$$P_n = n!$$

Esempio Si intende trovare tutti i numeri di 6 cifre distinte si possono scrivere utilizzando gli elementi dell’insieme $A = \{2, 3, 4, 7, 8, 9\}$.

$$P_6 = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$$

Permutazioni con ripetizione

Definizione Siano $n, k \in \mathbb{N}, n \geq 2$ e $0 < k \leq n$, le permutazioni con ripetizione di $n$ elementi, di cui $k$ ripetuti, sono tutti i gruppi formati dagli $n$ elementi che differiscono per il loro ordine.

$$P^{(k)}_n = \frac{n!}{k!}$$

Esempio Si vuole calcolare i modi in cui 5 sedie possono essere occupate da 3 persone. Si deve quindi calcolare il numero di permutazioni di 5 elementi, 2 dei quali (le sedie vuote) sono ripetuti.

$$P^{(2)}_k = \frac{5!}{2!} = \frac{5!}{2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2!}{2!} = 5\cdot 4 \cdot 3 = 60$$

Combinazioni

Combinazioni semplici

Definizione

Siano $n, k \in \mathbb{N}-\{0\}, 0 < k \leq n$, le combinazioni semplici di $n$ elementi distinti di classe $k$ sono tutti i gruppi di $k$ elementi che differiscono per almeno un elemento ma non per l’ordine.

$$C_{n,\;k} = \frac{D_{n,\;k}}{P_k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot ... \cdot (n-k+1)}{k!}=\binom{n}{k}$$

Esempio 1 Dato un insieme $A = \{ 1, 15, 23, 44, 56\}$ che rappresenti i numeri di 5 bici, si vuole calcolare come queste possono essere assegnate a 2 piloti.

$$C_{5,\;2} = \frac{D_{5,\;2}}{P_2} = \frac{5!}{3!} \cdot \frac{1}{2!} = \frac{5 \cdot 4 \cdot 3!}{3!} \cdot \frac{1}{2!} = \frac{5 \cdot 4 }{2!} = \frac{20}{2} = 10$$

Si ottiene lo stesso risultato applicando alle combinazioni semplici la definizione di coefficiente binomiale:

$$\binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2! \cdot 3!} = \frac{5 \cdot 4 \cdot 3!}{2! \cdot 3!} = \frac{5 \cdot 4}{2!} = \frac{20}{2} = 10$$

Esempio 2 Calcolare il numero di strette di mano che si scambiano 6 persone che partecipano ad una riunione di lavoro.

$$C_{5,\;2} = \frac{D_{6,\;2}}{P_2} = \frac{5!}{4!} \cdot \frac{1}{2!} = \frac{6 \cdot 5 \cdot 4!}{4!} \cdot \frac{1}{2!} = \frac{6 \cdot 5}{2!} = \frac{30}{2} = 15$$ $$\binom{6}{2} = \frac{6!}{2!(6 - 2)!} = \frac{6!}{2! \cdot 4!} = \frac{6 \cdot 5 \cdot 4!}{2! \cdot 4!} = \frac{6 \cdot 5}{2} = \frac{30}{2} = 15$$

Combinazioni con ripetizione

Definizione

Siano $n, k \in \mathbb{N}-\{0\}, 0 < k \leq n$, le combinazioni con ripetizione di $n$ elementi distinti di classe $k$ sono tutti i gruppi di $k$ elementi che soddisfino i seguenti requisiti:

1. ogni elemento può essere ripetuto fino a $k$ volte
2. l’ordine con cui si presentano gli elementi non ha importanza
3. il numero di volte che il quale un elemento compare è diverso

$$C'_{n,\;k} = C_{n+k-1,\;k} = \frac{n \cdot (n+k-1) \cdot (n+k-2) ... \cdot (n+1)}{k!}=\binom{n+k-1}{k}$$

Esempio Si vuole calcolare in quanti modi diversi si possono distribuire 6 libri in 4 scaffali diversi.

N.B. Alcuni scaffali possono rimanere vuoti.

$$\begin{equation} \begin{split} C'_{4,\;6} = & \binom{4+6-1}{6} = \binom{9}{6} = \frac{9!}{6! \cdot (9-6)!} = \frac{9!}{6! \cdot 3!} = \\ & = \frac{9 \cdot 8 \cdot 7 \cdot 6!}{6! \cdot 3!} = \frac{9 \cdot 8 \cdot 7}{3!} = \frac{504}{6} = 84 \end{split} \end{equation}$$

Triangolo di Tartaglia (o di Pascal)

Binomio di Newton

Siano $a, \; b \in \R$ e $n \in \N$, per calcolare le potenze di un binomio con esponente $n > 3$, si ricorre al triangolo di Tartaglia. I lati obliqui del triangolo sono formati da diversi $1$, mentre ogni coefficiente interno è la somma dei due coefficienti della riga precedente che sono alla sua destra e alla sua sinistra. La potenza con esponente $n$ ha il seguente sviluppo:

$$(a+b)^n = (...)a^n b^0 + (...)a^{n-1} b^1 + ... + a^0 b^n$$

Siano $(...)$ i coefficienti dell’n-esima riga. Si prenda come esempio $n = 4$:

$$(a+b)^4 = 1a^4 b^0 + 4a^3 b^1 + 6a^2 b^2 + 4ab^3 + b^4$$

Si indichi con $k$ la posizione di un numero della riga e sia $k = 0$ il primo numero a sinistra. La k-esima posizione dell’n-esima riga è occupata dal numero che corrisponde al coefficiente binomiale $\binom{n}{k}$

I coefficienti binomiali si possono usare per lo sviluppo di $(a+b)^n$ ottenendo la formula del binomio di Newton:

$$(a+b)^n = \binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1} b^1 + ... + \binom{n}{n-1}a^1 b^{n-1} + \binom{n}{n}a^0 b^n$$

La formula può essere scritta più sinteticamente utilizzando il simbolo della sommatoria: si ricordi infatti che $\sum\limits_{k=0}^n$ significa somma dei termini che si ottengono quando k varia da 0 a n, allora la formula del binomio di Newton è riscritta come segue:

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^k$$ Esempio $$\begin{equation} \begin{split} (a+b)^6 = \\ & = \binom{6}{0}a^6 + \binom{6}{1}a^5 b + \binom{6}{2}a^4 b^2 + \binom{6}{3}a^3 b^3 + \binom{6}{4}a^2 b^4 + \binom{6}{5}a b^5 + \binom{6}{6}b^6 = \\ \\ & = a^6 + 6a^5 b + 15a^4 b^2 + 20a^3 b^3 + 15a^2 b^4 + 6a b^5 + b^6 \end{split} \end{equation}$$

Il quadrato ed il cubo di un binomio

Si dimostri la risoluzione del quadrato di un binomio secondo la formula del binomio di Newton.

$$\begin{equation} \begin{split} (a+b)^2 = \\ & = \binom{2}{0}a^2 b^0 + \binom{2}{1}a^1 b^1 + \binom{2}{2}a^0 b^2 = \\ \\ & = 1 \cdot a^2 b^0 + 2 \cdot a^1 b^1 + 1 \cdot a^0 b^2 = \\ \\ & = a^2 + 2ab + b^2 \end{split} \end{equation}$$

Si dimostri la risoluzione del cubo di un binomio secondo la formula del binomio di Newton.

$$\begin{equation} \begin{split} (a+b)^3 = \\ & = \binom{3}{0}a^3 b^0 + \binom{3}{1}a^2 b^1 + \binom{3}{2}a^1 b^2 + \binom{3}{3}a^0 b^3 = \\ \\ & = 1 \cdot a^3 b^0 + 3 \cdot a^2 b^1 + 3 \cdot a^1 b^2 + 1 \cdot a^0 b^3 = \\ \\ & = a^3 + 3a^2 b + 3ab^2 + b^3 \end{split} \end{equation}$$

Dimostrazione per induzione del binomio di Newton

Si dimostri, secondo il primo principio di induzione, il binomio di Newton.

1. $n = 0:$

$$\begin{equation} \begin{split} & (a + b)^0 = \sum_{k = 0}^{0}\binom{0}{k} a^n b^0 \\ \\ \implies & (a + b)^0 = \binom{0}{0}a^0 b^0 \\ \\ \implies & (a + b)^0 = 1 \\ \\ \implies & 1 = 1 \end{split} \end{equation}$$

2. Si supponga vera la tesi per $n$ e si dimostri per $n+1$ che:

$$(a+b)^{n+1} = (a+b)^n \cdot (a+b)$$ $$\begin{equation} \begin{split} (a+b)^n \cdot (a+b) &=\\ &= (a+b)^n \sum_{k=0}^{n} \binom{n}{k} a^{n-k} \; b^k = \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} \; b^k + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} \; b^{k+1} \\ & k' = k + 1\\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} \; b^k + \sum_{k' = 1}^{n+1} \binom{n}{k'-1} a^{n-k'+1} \; b^{k'} \\ \\ & \text{per raccogliere le due sommatorie è necessario} \\ & \text{tirare fuori} \; \; k = 0 \; \; \text{dalla prima sommatoria e} \\ & n + 1 \; \; \text{dalla seconda.} \\ &= a^{n+1} \sum_{k = 1}^{n} \binom{n}{k} a^{n+1-k} \; b^k + b^{n+1} + \sum_{k = 1}^{n} \binom{n}{k-1} a^{n-k+1} \; b^{k} =\\ &=a^{n+1} + b^{n+1} \sum_{k = 1}^{n} \left[ \binom{n}{k} + \binom{n}{k-1} \right] a^{n+1-k} \; b^k =\\ &=a^{n+1} + b^{n+1} \sum_{k = 1}^{n} \binom{n+1}{k} a^{n+1-k} \; b^k =\\ &=\sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} \; b^k \end{split} \end{equation}$$

Formula di Stifel

Definizione

Nel triangolo di Tartaglia, ogni coefficiente è la somma dei due coefficienti della riga precedente a destra e sinistra.

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$