Combinazioni

Usiamo le combinazioni quando da un insieme di oggetti scegliamo un certo numero di elementi e l’ordine in cui li scegliamo non conta. Un problema tipico è il lotto 6 su 49: in un’urna abbiamo 49 numeri e ne estraiamo 6, e non importa in quale ordine escono.

Deduzione della formula

Ruota della fortuna

Consideriamo un insieme M, ad esempio M = {a, b, c, d, e}. Una combinazione di classe k è un sottoinsieme K ⊆ M che contiene esattamente k elementi. Poiché K è un insieme, l’ordine ovviamente non conta. Una combinazione di classe 3 dell’insieme M potrebbe quindi essere {a, b, d} oppure {b, c, d}.

La differenza rispetto alle disposizioni è che nelle disposizioni l’ordine contava, quindi (a; b; e) ed (e; b; a) sono disposizioni diverse, ma sono la stessa combinazione, perché sia (a; b; e) sia (e; b; a) contengono gli stessi elementi; che siano in un ordine diverso, nelle combinazioni non ci interessa.

Possiamo però usare le disposizioni per ottenere la formula del numero di tutte le diverse combinazioni. Sappiamo che le disposizioni semplici di classe k di un insieme di n elementi sono esattamente

$D_{n, k} = \frac{n!}{(n - k)!} .$

Se contassimo così tutte le disposizioni di classe 3 dell’insieme M = {a, b, c, d, e} di prima, otterremmo D_5,3 = 60 disposizioni diverse. Però per ogni terna ci sarebbero anche tutte le sue permutazioni. Cioè avremmo la terna abc, ma anche le terne acb, bac, bca, cab e cba. Sono sei disposizioni diverse, ma è una sola combinazione, perché hanno tutte gli stessi elementi.

Se abbiamo una terna, quante permutazioni diverse di questa terna esistono? Esattamente 3!. In altre parole, le disposizioni di classe 3 sono esattamente 3! volte più numerose delle combinazioni di classe 3. Invece di contare una sola combinazione, contiamo 3! disposizioni, una per ogni permutazione della terna. Quindi, se dividiamo il numero di disposizioni per 3!, otteniamo il numero di combinazioni.

Possiamo generalizzare il procedimento e dire che, se cerchiamo il numero di tutte le diverse combinazioni di classe k di un insieme di n elementi, questo numero, che indichiamo con C_n,k, è uguale a

$C_{n, k} = \frac{D_{n, k}}{k!},$

cioè il numero di disposizioni diviso per k!, che è il numero di permutazioni di ogni k-upla. Possiamo semplificare la formula sostituendo quella delle disposizioni:

$C_{n, k} = \frac{D_{n, k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Esempio: il numero di combinazioni di classe 2 dell’insieme {a, b, c} è

$C_{3, 2} = \frac{3!}{1! \cdot 2!} = 3$

e le combinazioni sono queste: {a, b}, {a, c} e {b, c}. Per le combinazioni di classe 3 dell’insieme originale M = {a, b, c, d, e} otterremmo il numero

$C_{5, 3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

e le combinazioni sono queste: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Coefficiente binomiale

La scrittura precedente della formula con C_n,k non si usa molto; al suo posto si usa il cosiddetto coefficiente binomiale, che ha questa forma

$(\binom{n}{k})$

È una specie di frazione senza la linea di frazione (che per abitudine scriverai comunque), ma con le parentesi (che non sono facoltative: ci devono essere). Il coefficiente binomiale si legge «n su k». Il suo valore è uguale a C_n,k.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Quindi, se abbiamo un insieme di 5 elementi e ne scegliamo delle quaterne, il loro numero totale sarà

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Relazioni fondamentali

Per il coefficiente binomiale e per n ∈ ℕ^* vale:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Inoltre, per n, k ∈ ℕ e k ≤ n vale

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

E per n, k ∈ ℕ e k < n vale

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Calcolatore

Il calcolatore seguente ti calcola il coefficiente binomiale n su k.

Esercizi svolti

Cominciamo dal lotto 6 su 49 già citato. Da un’urna con 49 palline se ne estraggono in tutto 6. Quante estrazioni diverse possiamo ottenere?

Prima di tutto: conta l’ordine di estrazione dei numeri? No, puntiamo solo sui numeri, non sul loro ordine. Useremo le combinazioni. Abbiamo in tutto 49 palline e ne estraiamo 6, quindi otteniamo il coefficiente binomiale

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Ci sono in tutto 13.983.816 possibili estrazioni. Questo ci dà, tra l’altro, una probabilità di vincita con una singola giocata di 1/13.983.816, cioè 0,00000715112%.
Marco, noto rubacuori, è a una festa di paese, dove ci sono in tutto 13 belle ragazze che gli interessano. Marco sa che in una serata riesce a conquistare 4 ragazze diverse. Tra quante quaterne diverse può scegliere Marco?

Anche questo è un semplice esercizio sulle combinazioni: l’ordine non conta, Marco sarà bravo con la prima ragazza come con l’ultima. Abbiamo quindi un insieme di 13 ragazze, da cui scegliamo sempre 4 ragazze. Questo porta al coefficiente binomiale

$(\binom{13}{4}) = 715.$
Hai un gruppo di cinquanta persone: metà uomini e metà donne. Quante terne diverse di persone esistono, se non possono essere formate da persone di un solo sesso (cioè nella terna non devono comparire tre uomini o tre donne)?

Questa è una combinazione un po’ più complicata. Se escludiamo le terne di persone dello stesso sesso, restano solo due possibilità per la composizione della terna: due uomini e una donna, oppure un uomo e due donne, e il numero di combinazioni del primo gruppo (due uomini e una donna) sarà uguale al numero di combinazioni del secondo gruppo. Ci basta quindi calcolare il numero di combinazioni del primo gruppo e poi moltiplicarlo per due. Ora è di nuovo un gioco da ragazzi. Determiniamo il numero di combinazioni di coppie diverse di uomini, cioè venticinque su due, e lo moltiplichiamo per il numero di combinazioni di una donna (che è venticinque, vedi le relazioni fondamentali qui sopra, in particolare la seconda riga). Moltiplichiamo infine questo risultato per due e otteniamo il risultato finale.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
In una scatola ci sono 15 prodotti, di cui 4 difettosi. In quanti modi si possono scegliere 6 prodotti in modo che
- nessuno sia difettoso? In questo caso scegliamo 6 prodotti tra i 15 − 4 = 11 prodotti non difettosi. Otteniamo quindi il coefficiente binomiale
  
  $(\binom{11}{6}) = 462.$
- sia difettoso esattamente uno? Scegliamo quindi un insieme che contiene 5 prodotti funzionanti e 1 difettoso. I prodotti funzionanti sono in tutto 11, quelli difettosi 4. Usiamo il principio del prodotto e otteniamo il risultato:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- sia difettoso al massimo uno? Per la soluzione usiamo i risultati precedenti. Sappiamo che abbiamo 462 possibilità di scegliere esattamente 6 prodotti funzionanti e 1848 possibilità di scegliere cinque prodotti funzionanti e uno difettoso. Usiamo quindi il principio della somma, sommiamo questi risultati e otteniamo il risultato che cerchiamo, cioè al massimo un prodotto difettoso (= o nessun prodotto difettoso, oppure esattamente uno). Il risultato è quindi: 462 + 1848 = 2310.

Capitoli: Calcolo combinatorio, Disposizioni, Permutazioni, Combinazioni, Disposizioni con ripetizione, Combinazioni con ripetizione, Quanti PIN diversi esistono?

« Precedente: Permutazioni

Successivo: Disposizioni con ripetizione »