Combinazioni
Quando si vogliono contare le sequenze di oggetti
senza però considerare l'
ordine si usano le combinazioni.
Più precisamente una combinazione di \(n\) elementi presi \(k\) alla volta (o una combinazione di \(n\) elementi di classe \(k\)) è un sottoinsieme (per cui l'ordine non ha alcuna importanza) di \(k\) elementi presi da un insieme di \(n\).
Combinazioni semplici
Dato un insieme di \(n\) elementi vogliamo contare quanti sottoinsieme di \(k\) elementi si possono formare, senza che abbia importanza l'ordine e
senza ripetere gli elementi. Il numero di questi sottoinsiemi o
combinazioni semplici è dato da
$$C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} $$
dove \(\binom{n}{k} \) è chiamato
coefficiente binomiale.
Per capire la formula notiamo che è uguale al numero di disposizioni di \(n\) oggetti \(k\) alla volta, \( D_{n,k} = \frac{n!}{(n-k)!} \),
diviso per il numero di modi in cui si possono
permutare i \(k\) elementi, cioè \(k!\). Questo perché dal momento che non ci interessa l'ordine, tutte le possibili permutazioni degli stessi elementi contano come una sola.
Da un mazzo di 52 carte ne viene estratta una mano di 5 carte. Quante possibili mani si possono formare?
L'ordine delle carte in mano non conta, usiamo quindi le combinazioni con \(n=52\) e \(k=5\). Le possibili mani sono
$$C_{52,5} = \binom{52}{5} = \frac{52!}{5!47!} = \frac{52\cdot51\cdot50\cdot49\cdot48}{5!} = 2598960 $$
Quante possibili strette di mano diverse ci possono essere in un gruppo di 20 persone?
Pensiamo schematicamente ad una stretta di mano come una coppia (A,B) di due persone. Il problema chiede di trovare quante possibili coppie diverse di persone si possono formare. In questo caso l'ordine non conta (la stretta di mano (A,B) tra la persona A e la persona B è esattamente la stessa di (B,A) cioè tra la persona B e la persona A). Usiamo quindi le combinazioni semplici con \(n=20\) e \(k=2\):
$$C_{20,2} = \binom{20}{2} = \frac{20 \cdot 19}{2!} = 190$$