Capitolo 21 Richiami di Calcolo Combinatorio

Sia \(n\in\mathbb{N}\) un numero naturale, si definisce \(n\) fattoriale, il numero \[n!=n(n-1)(n-2)...3\cdot 2 \cdot 1\] conta in quanti modo posso rimescolare \(n\) oggetti.

Esempi \(3!=3\cdot 2\cdot 1=6\), \(10!=10\cdot 9\cdot... \cdot1 =3628800\), \(52!=8.0658\times 10^{67}\)

Nota. Per definizione \(0!=1\)

21.1 Il coefficiente binomiale

Il coefficiente binomiale \(\binom{n}{k}\) conta in quanti modi posso disporre \(k\) oggetti indistinguibili in \(n\ge k\) posti: \[\binom{n}{ k}=\frac {n!}{k!(n-k)!}\]

Proprietà utili

\[\begin{eqnarray*} \binom{n}{ k} &=&\binom{n}{ n-k},\qquad\text{Per esempio:} \\ \binom{5}{ 3} &=&\binom{5}{ 2}=10,\\ \binom{n}{ 0} &=&\binom{n}{ n} = 1 \\ \binom{n}{ 1} &=&\binom{n}{ n-1}=n \end{eqnarray*}\]

In matematica \(\binom{n}{ k}\) è il \(k\)-esimo elemento della \(n\)-esima riga del triangolo di Tartaglia.

	0	1	2	3	4	5	6	7
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1