Combinazioni
Consideriamo un insieme con un numero finito di elementi, ad esempio
\[A=\{1, 2, 3, 4, 5\}\,\, (*).\]
Una combinazione di k elementi tra gli n dati è un sottoinsieme (non ordinato) di A costituito da k elementi. L'insieme delle combinazione di 2 elementi tra i 5 dati di A (*) è
\[C=\{12, 13, 14, 15, 23, 24, 25, 34, 35, 45\}\]
(per comodità uso la notazione 12 per indicare il sottoinsieme {1,2}).
Il numero di combinazioni di k elementi tra gli n dati è
\[ C_{n,k}=\frac{n!}{(n-k)!k!} \]
Nell'esempio precedente ho n=5, k=2, dunque
\[C_{5,2}=\frac{5!}{(5-2)!2!}=\frac{(5)(4)(3)(2)}{(3)(2)(2)}=10\]
che effettivamente è il numero di elementi di C.
Tale formula la si può ottenere osservando che
\[ C_{n,k}=D_{n,k}/P_k. \]
Cioè il numero delle combinazioni di k elementi su n dati si può ottenere considerando le disposizioni semplici di k elementi tra n dati, dove l'ordine di ogni singola disposizione non deve essere considerato. Ecco perchè si divide per il numero di permutazioni di k elementi \(P_k=k!\). Nell'esempio se consideriamo le disposizioni, esse sono esattamente il doppio delle combinazioni. Infatti
\[D=\{12, 21, 13, 31, 14, 41, 15, 51, 23, 32, 24, 42, 25, 52, 34, 43, 35, 53, 45, 54\}\]
Dunque devo dividere per 2! che è esattamente il numero di permutazioni di ogni disposizione in D. Ad esempio 12 ha 2 permutazioni possibili 12 e 21.
Vedi anche disposizioni semplici e con ripetizioni.