Permutazioni e combinazioni

Il calcolo combinatorio studia in quanti modi si possono fare scelte e disposizioni. Tre strumenti chiave: permutazioni, disposizioni, combinazioni.

Una permutazione di $n$ oggetti è un loro ordinamento. Il numero di permutazioni di $n$ oggetti è il fattoriale:

$$P_n=n!=n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$$

Esempio: 5 libri si possono ordinare in $5!=120$ modi.

Una disposizione di $n$ oggetti scelti $k$ alla volta (con $k\le n$) è una scelta ordinata di $k$ tra gli $n$:

$$D_{n,k}=\frac{n!}{(n-k)!}$$

Esempio: tra 10 cavalli, in quanti modi si può fare il podio (1°, 2°, 3°)? $D_{10,3}=\frac{10!}{7!}=720$.

Una combinazione di $n$ oggetti $k$ alla volta è una scelta non ordinata di $k$ tra $n$:

$$C_{n,k}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$$

Esempio: in quanti modi posso scegliere 3 amici tra 10 da invitare a cena? $\left(\genfrac{}{}{0ex}{}{10}{3}\right)=\frac{10!}{3!\cdot 7!}=120$.

Disposizione = scegli $k$ tra $n$ e l'ordine conta. Combinazione = scegli $k$ tra $n$ e l'ordine NON conta. Le combinazioni sono sempre meno delle disposizioni.