9 Ordinare e contare Supponiamo, per esempio, di avere un insieme di 4 elementi: A = {a, b, c, d}. Le combinazioni di classe 3 di questi 4 elementi sono le possibili scelte non ordinate di 3 elementi, e cioè: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} Il numero delle combinazioni di 4 elementi di classe 3 è quindi calcolabile in questo modo: numero di combinazioni di 4 elementi di classe 3 = = numero di scelte non ordinate = #disposizioni di 4 elementi in 3 posti 4 3 2 = ______________________________ = _ = 4 #permutazioni di 3 elementi 3 2 1 Possiamo generalizzare il ragionamento condotto sopra a un qualunque insieme finito di cardinalità n, nel quale vogliamo scegliere k elementi (senza che interessi l ordine con cui tali elementi sono scelti). Il numero delle combinazioni di n elementi di classe k, che indichiamo con Cn,k, è allora dato da: #disposizioni di n elementi in k posti C n,k = ______________________________ = #permutazioni di k elementi ATTENZIONE! A Il simbolo # indica il numero di elementi di un insieme finito. n (n 1) (n 2) (n (k 1)) = ______________________________ k! esempio O Quante e quali sono le combinazioni di 3 elementi di classe 2? Il numero delle disposizioni di 3 elementi in 2 posti è 3 2 = 6. Il numero delle permutazioni di 2 elementi è 2 1 = 2. Il numero delle combinazioni di 6 3 elementi di classe 2 è il rapporto tra i due numeri precedenti, e quindi è __ = 3. 2 Infatti, se indichiamo con {a, b, c} l insieme dei tre elementi, le loro combinazioni di classe 2 sono: {a, b}, {a, c}, {b, c} n(n 1)(n 2) (n (k 1)) Poiché il numero ______________________________ si indica comunemente k! n con il simbolo ( ) (che si legge n sopra k ) il numero delle combinazioni di n k elementi di classe k viene anche indicato con: n Cn,k = ( ) k Per ottenere una formula più facile da memorizzare, possiamo applicare i principi di equivalenza moltiplicando sia il numeratore sia il denominatore per: (n k)! = (n k)(n k 1)(n k 2) 2 1 ottenendo così: n(n 1)(n 2) (n (k 1)) n ______________________________ = (k) = k! n(n 1)(n 2) (n (k 1))(n k)(n k 1) 2 1 n! = _____________________________________________________ = ________ k!(n k)(n k 1) 2 1 k!(n k)! Abbiamo dunque che il numero delle combinazioni di n elementi di classe k è: n! n C n,k = ( ) = ________ k!(n k)! k APPROFONDIMENTO A n! Poiché _______ esprime il numero k!(n k)! n delle combinazioni, il numero ( ), k in cui k, n N e k n, è un numero naturale. La frazione n! espressa nella formula _______ k!(n k)! è quindi sempre equivalente a un numero naturale. Infatti: Q nella successione dei numeri naturali, i multipli di un numero k compaiono ogni k numeri (per esempio, i numeri pari sono ogni 2 numeri, i multipli di 3 sono ogni 3 numeri, e così via); Q il numeratore della frazione è il prodotto di n numeri consecutivi (con n k); quindi, uno di essi è sicuramente un multiplo di k; vi sarà anche un multiplo di k 1, un multiplo di k 2 e così via; Q ognuno di questi multipli divide uno dei fattori che compaiono al denominatore; la frazione così si semplifica e può essere scritta con denominatore uguale a 1, cioè come numero naturale. 423