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$$




  • Esercizio
  • In una scuola ci sono 20 professori e 100 studenti. Si devono eleggere dei rappresentanti di cui 3 eletti tra i professori e 2 eletti tra gli studenti. In quanti modi è possibile fare la scelta?