Calcolo combinatorio
Contare bene significa descrivere una scelta senza elencare tutti i casi.
Principio fondamentale del conteggio: se una scelta avviene in \(m\) modi e, per ciascuno, una seconda scelta in \(n\) modi, le coppie possibili sono \(mn\).
Ordine e ripetizione
- Permutazioni di \(n\) elementi: \(P_n=n!\).
- Disposizioni semplici di \(n\) elementi presi \(k\) alla volta: \(D_{n,k}=\frac{n!}{(n-k)!}\).
- Combinazioni semplici: \(\binom nk=\frac{n!}{k!(n-k)!}\).
Da \(8\) persone scegliamo presidente, vicepresidente e segretario. I ruoli distinguono le scelte, quindi l'ordine conta: \(D_{8,3}=8\cdot7\cdot6=336.\)
Se scegliessimo soltanto una commissione di tre persone, useremmo \(\binom83=56\).
Con elementi ripetuti, \(n\) oggetti di cui \(n_1,n_2,\ldots\) indistinguibili si ordinano in \(\frac{n!}{n_1!n_2!\cdots}\) modi.
Le anagrammazioni distinte di MAMMA sono \(\frac{5!}{3!2!}=10\).
Prima della formula chiediti: l'ordine conta? Si possono ripetere gli elementi? Si scelgono tutti gli elementi o solo alcuni?
Prova tu
- Quanti PIN di quattro cifre esistono se le cifre possono ripetersi?
- In quanti modi si scelgono \(5\) libri tra \(12\)?
- Quante parole distinte si ottengono riordinando TETTO?