Tre oggetti del calcolo combinatorio confondono quasi tutti all'inizio: permutazioni, disposizioni e combinazioni. La distinzione si riduce in realtà a due domande: l'ordine conta? e si scelgono tutti gli elementi o solo alcuni? Una volta risposto, la formula segue dalla regola del prodotto e dalla regola della divisione, senza bisogno di memorizzare nulla.
Il fattoriale
Il fattoriale di n, scritto n!, è il prodotto dei numeri da 1 a n: 5! = 5 · 4 · 3 · 2 · 1 = 120. Per convenzione 0! = 1, il che rende coerenti tutte le formule che seguono.
Il fattoriale cresce più in fretta di qualsiasi potenza a base fissa: 10! = 3.628.800, e 20! supera già 2 · 10¹⁸.
Permutazioni: ordinare tutti gli elementi
Una permutazione di n oggetti distinti è un loro ordinamento. Per il primo posto ci sono n scelte, per il secondo n − 1, e così via fino a 1. Per la regola del prodotto:
P(n) = n!
Esempio: le 6 permutazioni di {A, B, C} sono ABC, ACB, BAC, BCA, CAB, CBA.
In informatica: un algoritmo di ordinamento basato su confronti deve distinguere tra n! possibili ordinamenti dell'input. Poiché ogni confronto ha due esiti, servono almeno log₂(n!) confronti nel caso peggiore, una quantità dell'ordine di n log n. È il motivo per cui nessun ordinamento per confronti può fare meglio di n log n.
Disposizioni: scegliere k elementi in ordine
Una disposizione semplice di n oggetti presi k alla volta è una sequenza ordinata di k oggetti distinti scelti tra n. La regola del prodotto si ferma dopo k fattori:
D(n, k) = n · (n − 1) · … · (n − k + 1) = n! / (n − k)!
Esempio: in una gara con 8 concorrenti, i possibili podi (oro, argento, bronzo) sono 8 · 7 · 6 = 336.
Combinazioni: scegliere k elementi senza ordine
Una combinazione semplice di n oggetti presi k alla volta è un sottoinsieme di k elementi, senza ordine. Ogni combinazione corrisponde a k! disposizioni diverse (i modi di ordinare i k elementi scelti). Per la regola della divisione:
C(n, k) = D(n, k) / k! = n! / (k! (n − k)!)
Questo numero si chiama coefficiente binomiale e si legge «n su k».
Esempio: i gruppi di 3 persone che si possono formare da 8 sono 336 / 6 = 56. Il podio ha 336 casi perché l'ordine conta; la commissione di 3 persone ne ha 56 perché non conta.
Lo schema per scegliere
| Domanda | Ordine conta | Ordine non conta |
|---|---|---|
| Tutti gli n elementi | permutazioni, n! | una sola scelta |
| k elementi su n, senza ripetizione | disposizioni, n!/(n−k)! | combinazioni, C(n, k) |
| k elementi su n, con ripetizione | nᵏ | C(n + k − 1, k) |
L'ultima riga riguarda le scelte in cui lo stesso elemento può comparire più volte: nᵏ è il numero di stringhe di lunghezza k su un alfabeto di n simboli, mentre C(n + k − 1, k) conta le combinazioni con ripetizione, che meritano un discorso a parte.
Proprietà del coefficiente binomiale
- Simmetria: C(n, k) = C(n, n − k). Scegliere chi entra equivale a scegliere chi resta fuori.
- Relazione di Stifel: C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Fissato un elemento, o lo si sceglie (e restano k − 1 scelte tra n − 1) o no (e restano k scelte tra n − 1).
- Somma di una riga: C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ, cioè il numero di tutti i sottoinsiemi di un insieme di n elementi.
La relazione di Stifel genera il triangolo di Tartaglia (noto in altri paesi come triangolo di Pascal), in cui ogni numero è la somma dei due sopra di esso:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
La riga n contiene i coefficienti dello sviluppo di (a + b)ⁿ: per esempio (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴. È il teorema binomiale, da cui il nome di questi coefficienti.
Calcolarli senza overflow
Calcolare C(n, k) come n! / (k!(n − k)!) produce numeri intermedi enormi. È meglio moltiplicare e dividere un passo alla volta, sfruttando il fatto che ogni risultato parziale è intero:
def binomiale(n, k):
k = min(k, n - k)
r = 1
for i in range(1, k + 1):
r = r * (n - k + i) // i
return r
In Python esiste anche math.comb(n, k), che fa lo stesso lavoro.
Un esempio realistico
Una lotteria estrae 6 numeri da 90, senza ordine. Le combinazioni possibili sono C(90, 6) = 622.614.630. Chi gioca una sola combinazione ha quindi una probabilità di indovinarle tutte pari a una su oltre 622 milioni. Se invece contasse l'ordine di estrazione, i casi sarebbero 6! = 720 volte di più.
In sintesi
- Prima domanda: l'ordine conta? Seconda: si scelgono tutti gli elementi o solo k?
- Permutazioni: n!; disposizioni: n!/(n − k)!; combinazioni: n!/(k!(n − k)!).
- Le combinazioni si ottengono dalle disposizioni dividendo per k!, i modi di ordinare i k scelti.
- Il triangolo di Tartaglia nasce dalla relazione di Stifel e dà i coefficienti di (a + b)ⁿ.
- Per calcolare C(n, k) si alternano moltiplicazioni e divisioni, evitando i fattoriali completi.
