Combinatorio

Calcolo combinatorio: combinazioni, disposizioni, permutazioni, fattoriale

Tutto il calcolo combinatorio risponde a una sola domanda — «in quanti modi?» — e per rispondere servono due informazioni: l'ordine conta? e si possono ripetere gli elementi? Le quattro risposte possibili sono le quattro formule fondamentali.

Le quattro regole del conteggio

• Ordine no, ripetizione no → combinazioni semplici: C(n, k) = n! / (k! · (n−k)!). È il caso del SuperEnalotto: C(90, 6) = 622.614.630.
• Ordine sì, ripetizione no → disposizioni semplici: D(n, k) = n! / (n−k)!. È il podio di una gara: con 10 atleti, D(10, 3) = 720 podi diversi.
• Ordine sì, ripetizione sì → disposizioni con ripetizione: nᵏ. È il PIN del bancomat: 10⁴ = 10.000 combinazioni.
• Ordine no, ripetizione sì → combinazioni con ripetizione: C(n+k−1, k). È il caso dei gusti di gelato: 3 palline scelte fra 5 gusti, potendo ripetere, fanno C(7, 3) = 35 coni diversi.

Il fattoriale è il caso limite delle disposizioni: quando si usano tutti gli elementi (k = n) restano solo gli ordinamenti, e sono n!. La convenzione 0! = 1 non è un capriccio: esiste esattamente un modo di ordinare l'insieme vuoto, ed è quello che rende coerenti tutte le formule.

Combinazioni o disposizioni? La domanda che decide

Il test più rapido è chiedersi se scambiando due elementi si ottiene un caso diverso. Le sei carte del SuperEnalotto estratte in ordine diverso sono la stessa giocata: l'ordine non conta, sono combinazioni. Oro, argento e bronzo scambiati fra loro sono un podio diverso: l'ordine conta, sono disposizioni. Il legame fra i due conti è semplice: D(n, k) = C(n, k) · k!, perché ogni gruppo scelto si può ordinare in k! modi.

Il triangolo di Tartaglia

In Italia si chiama triangolo di Tartaglia (altrove di Pascal) la tabella in cui la riga n contiene i coefficienti C(n, 0), C(n, 1)… C(n, n). Ogni numero è la somma dei due sopra di lui — è la regola di Pascal: C(n, k) = C(n−1, k−1) + C(n−1, k). Quei numeri sono anche i coefficienti dello sviluppo del binomio: (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴, dove 1, 4, 6, 4, 1 è la quinta riga. La somma di una riga vale 2ⁿ, cioè il numero di tutti i sottoinsiemi possibili.

Gli anagrammi e le lettere ripetute

Se tutte le lettere di una parola fossero diverse gli anagrammi sarebbero n!. Ogni lettera ripetuta però produce scambi che non si vedono, e va divisa via: gli anagrammi di una parola di n lettere sono n! diviso il prodotto dei fattoriali delle ripetizioni. MATEMATICA ha 10 lettere con tre A, due M e due T: 10! / (3! · 2! · 2!) = 3.628.800 / 24 = 151.200 anagrammi. Con MAMMA (tre M e due A) si scende a 5! / (3! · 2!) = 10.

Numeri che vale la pena conoscere

• SuperEnalotto: C(90, 6) = 622.614.630. La probabilità del «6» è 1 su 622 milioni.
• Lotto: ambo su una ruota C(90, 2) = 4.005; terno C(90, 3) = 117.480; cinquina C(90, 5) = 43.949.268.
• Poker: le mani da 5 carte su 52 sono C(52, 5) = 2.598.960.
• Mazzo di carte: gli ordinamenti di un mazzo francese sono 52!, un numero di 68 cifre — più dei granelli di sabbia della Terra.
• Formazione: 11 titolari scelti in una rosa di 25 sono C(25, 11) = 4.457.400.
• PIN e password: 10⁴ = 10.000 PIN; una password di 8 caratteri su un alfabeto di 94 simboli dà 94⁸ ≈ 6,1 × 10¹⁵ possibilità.

Quanto crescono, e dove si rompono le calcolatrici

Il fattoriale cresce più in fretta di qualunque esponenziale: 13! supera i 6 miliardi, 20! ≈ 2,43 × 10¹⁸ è l'ultimo che entra in un intero a 64 bit, 100! ha 158 cifre e finisce con 24 zeri, e 171! supera il massimo numero rappresentabile in virgola mobile (circa 1,8 × 10³⁰⁸): una calcolatrice normale risponde Infinito. Anche il coefficiente binomiale si rompe prima di quanto sembri: C(100, 50) vale 100.891.344.545.564.193.334.812.497.256, ma in virgola mobile diventa 1,0089134454556418 × 10²⁹ e le ultime tredici cifre spariscono. Qui ogni conteggio è in aritmetica intera esatta, quindi le cifre ci sono tutte.

Gli zeri finali di n! si contano senza calcolare il fattoriale, con la formula di Legendre: quanti fattori 5 ci sono da 1 a n, cioè ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … Per 100! fa 20 + 4 = 24. I fattori 2 sono sempre più numerosi dei 5, quindi sono i 5 a dettare il numero di zeri.

Quando i numeri sono enormi si usa l'approssimazione di Stirling: n! ≈ √(2πn) · (n/e)ⁿ. L'errore relativo è già sotto lo 0,5 % a n = 20 e continua a calare: non serve per il valore esatto, ma dice in un colpo d'occhio quante cifre aspettarsi.

Dal conteggio alla probabilità

Contare è il passo che precede la probabilità. Se tutti i casi sono ugualmente possibili, la probabilità di un evento è il numero di casi favorevoli diviso il numero di casi possibili: giocando una sola schedina al SuperEnalotto i casi favorevoli sono 1 e i possibili 622.614.630, quindi la probabilità è 1 / 622.614.630 ≈ 0,00000016 %. È anche il motivo per cui la formula del binomio compare nella distribuzione binomiale: C(n, k) conta in quanti ordini diversi possono presentarsi k successi su n tentativi.