Combinazioni, disposizioni e fattoriale
Quanti modi di scegliere, ordinare o disporre elementi? Il calcolo combinatorio risponde con tre strumenti: il fattoriale, le disposizioni (l'ordine conta) e le combinazioni (l'ordine è indifferente). Indica il totale n e il numero scelto k, con o senza ripetizione.
La domanda chiave: l'ordine conta? Un podio (oro, argento, bronzo) è una disposizione — l'ordine distingue i risultati. Una mano di carte o i numeri del lotto sono una combinazione — conta solo l'insieme, non l'ordine dell'estrazione.
Dati
Risultato
- C(49, 6) 13.983.816
| n (elementi disponibili) | 49 |
| k (elementi scelti) | 6 |
| Combinazioni senza ripetizione C(n, k) | 13.983.816 |
| Combinazioni con ripetizione C(n+k−1, k) | 25.827.165 |
C(n, k) = n! / [ k! · (n − k)! ]
Il fattoriale, il mattone di tutto
Il calcolo combinatorio poggia su un solo mattone: il fattoriale. n! conta i modi di mettere in fila n oggetti distinti. n scelte per il primo posto, n − 1 per il secondo, n − 2 per il terzo, giù fino a 1. Quella catena è n!.
Capiamoci: 5 libri sullo scaffale sono 5 × 4 × 3 × 2 × 1 = 120 allineamenti. Dieci ospiti intorno a un tavolo numerato: 10! = 3.628.800. 0! vale 1, per convenzione: c'è un modo di ordinare nulla, e le formule più sotto restano vere anche quando k = n. Una permutazione è proprio questo caso: k = n, si usano tutti, conta solo l'ordine. Pn = n! = D(n, n).
n! = 1 × 2 × 3 × … × n (0! = 1) · D(n, k) = n! / (n − k)! · C(n, k) = D(n, k) / k!
Disposizioni e combinazioni non sono un altro mondo. Si ottengono spezzando o dividendo questo prodotto. In sostanza, se sapete se l'ordine conta, sapete già quale pezzo della formula tenere.
Disposizioni D(n, k): l'ordine conta
Una disposizione semplice D(n, k) — in tanti testi nPk, o P(n, k) — conta i modi di estrarre k elementi da n tenendo l'ordine. Podio di 3 tra 8 atleti: 8 × 7 × 6 = 336. Chi prende l'oro non è chi prende il bronzo. 336 podi, non 336 terne.
Classifiche, lucchetti a combinazione in cui 1-2-3 è diverso da 3-2-1, file d'attesa, permutazioni parziali: la faccenda è sempre D. Il prodotto si ferma dopo k fattori, non dopo n. Detto in altro modo, D(n, k) = n! / (n − k)! è n! con i (n − k)! del «resto inutilizzato» semplificati via. Non serve calcolare 49! per un D(49, 6).
D(n, k) = n × (n − 1) × … × (n − k + 1)
Se k = n si ricade sulle permutazioni. Se k = 1, D(n, 1) = n: avete solo scelto chi sta al primo posto.
Combinazioni C(n, k): conta solo il gruppo
Una combinazione C(n, k) — nCk, coefficiente binomiale — estrae k elementi da n senza badare all'ordine. La mano di carte {asso, re, donna, fante, 10} è una sola, qualunque sia l'ordine in cui le avete prese dal mazzo. Si prende D(n, k) e si divide per k!: i k! modi di rimescolare gli stessi k oggetti, che qui non devono contare.
C(n, k) = n! / [ k! · (n − k)! ]
Cinque carte su cinquantadue: C(52, 5) = 2.598.960 mani. Il bello è il rapporto fisso: D(n, k) = C(n, k) × k!. Stesso n, stesso k, la disposizione è sempre più grande della combinazione, salvo k = 0 o k = 1, dove coincidono. E allora, prima di premere il pulsante: state contando file o mucchi? File → D. Mucchi → C.
C(n, k) = C(n, n − k). Scegliere 6 numeri da tenere o 43 da scartare è lo stesso elenco di schedine. Il calcolatore usa questa simmetria per non far esplodere i fattoriali a metà strada.
Con o senza reimmissione
Due estrazioni. Senza reimmissione (senza ripetizione): pallina tolta, non torna. Sono le D(n, k) e C(n, k) classiche, quelle del lotto, del poker, del podio. Con reimmissione (con ripetizione): la pallina torna nell'urna, un elemento può ripresentarsi.
- Disposizioni con ripetizione — nk. Ogni posto ha n scelte, indipendenti. Un PIN di 4 cifre: 104 = 10.000, dallo 0000 al 9999.
- Combinazioni con ripetizione — C(n + k − 1, k). Conta i mucchi in cui un oggetto può comparire più volte, l'ordine no. Gelati a 3 palline su 5 gusti, ripetizioni ammesse: C(5 + 3 − 1, 3) = C(7, 3) = 35.
A dirla tutta, «con o senza reimmissione» e «l'ordine conta o no» sono due manopole distinte. Quattro caselle, quattro formule. PIN: ordine sì, ripetizione sì → nk. Podio: ordine sì, ripetizione no → D(n, k). Lotto: ordine no, ripetizione no → C(n, k). Il quarto angolo (ordine no, ripetizione sì) è quello dei gelati, poco visibile nei giochi a premi, frequentissimo quando si distribuiscono k posti identici su n tipi.
Niente di strano se il calcolatore, in modalità combinazioni, vi stampa anche C(n + k − 1, k) sotto il C(n, k): è il cugino con reimmissione, non un secondo risultato dello stesso problema.
Sei numeri su 49: il lotto classico
Lotto «6 su 49»: l'ordine dell'estrazione non conta, un numero non può uscire due volte. Le schedine distinte sono C(49, 6) = 13.983.816. La probabilità della sestina secca è 1 su quasi 14 milioni. Provate n = 49 e k = 6: è il default del modulo, non a caso.
Alla fine, «quasi 14 milioni» è il denominatore di ogni slogan sul 6 esatto. Il 5, il 4, il 3 sono altri C: C(6, 5)×C(43, 1) per i cinque numeri giusti e uno sbagliato, e così via. Questa pagina vi dà il mucchio totale. I premi intermedi li scompone chi fa il regolamento.
In due parole: se l'ordine contasse, saremmo a D(49, 6) = 10.068.347.520, settecento volte tanto. Non è il gioco. Le palline escono in un ordine, la schedina non lo chiede.
SuperEnalotto: sei numeri su novanta
In Italia il gioco che tutti citano non è il 6/49. È il SuperEnalotto: 6 numeri da 1 a 90, ordine indifferente, senza ripetizione. C(90, 6) = 622.614.630. Più di seicentoventidue milioni. Circa 44 volte il 6/49. Poi arrivano Jolly e Superstar, che moltiplicano ancora: qui parliamo solo dei sei numeri, il nucleo combinatorio.
Il prodotto è (90 × 89 × 88 × 87 × 86 × 85) / 6!. Il numeratore è D(90, 6); il 720 del 6! toglie l'ordine. Magari vi viene voglia di scrivere 90!: non fatelo, 90! è già un mostro, e i 84! a denominatore si cancellano. Il calcolatore fa il prodotto corto, quello che si può scrivere a mano in un minuto.
Un «6» al SuperEnalotto è, in probabilità, un evento di un altro ordine rispetto al 6/49. Stessa forma C(n, 6), n che passa da 49 a 90: il denominatore esplode. Le pubblicità vendono il montepremi. Il C(90, 6) vende il mestiere.
PIN, password e il caso in cui l'ordine è tutto
Quattro cifre, ripetizione ammessa: 104 = 10.000 PIN. Senza ripetizione, 10 × 9 × 8 × 7 = 5.040. Il lucchetto «a combinazione» che rifiuta le cifre ripetute è più povero, non più ricco: avete chiuso delle strade. Dal canto suo un PIN di 6 cifre con ripetizione sale a un milione. Ogni cifra in più moltiplica per 10, non aggiunge 10.
Una password è la stessa formula, alfabeto più largo. Otto caratteri su 26 lettere minuscole: 268 ≈ 2,09 × 1011. Aggiungete maiuscole e cifre, 628 ≈ 2,18 × 1014. L'ordine conta, la ripetizione è ammessa (due «a» di fila sono legali): disposizioni con ripetizione, nk, non combinazioni. Voglio dire: trattare una password come C(62, 8) è un errore di mestiere, non di aritmetica. C(62, 8) conta i sottoinsiemi di 8 lettere distinte, e «Aaaaaaaa» non ci sta.
Peccato che «combinazione del lucchetto» in italiano sia proprio una disposizione. La lingua di tutti i giorni e quella del liceo non coincidono. Sul lucchetto l'ordine conta. Sulla schedina no.
Poker: 2.598.960 mani, poche di loro contano
C(52, 5) = 2.598.960 l'abbiamo già. Vale la pena di spezzarlo, perché il poker è il posto in cui si vede cosa significa «raro» in combinazioni, senza campane né z.
- Scala reale — 4 mani (un colore solo, 10-A). Una su 649.740.
- Poker (quattro uguali) — 624 mani. Una su circa 4.165.
- Full — 3.744. Una su circa 694.
- Coppia — 1.098.240. Circa il 42 % delle mani. Al contrario, «non avere niente» (carta alta) è ancora più comune: 1.302.540 mani, circa il 50 %.
Semmai qualcuno vi dice che «esce sempre una coppia», i numeri gli danno ragione a metà: coppia sì, spesso; full no, quasi mai. Tutte queste quantità si ottengono da prodotti di C: C(13, 1)×C(4, 2)×C(12, 3)×[C(4, 1)]³ per la coppia semplice, e via di questo passo. Il punteggio z qui non c'entra: il mazzo è discreto, finito, senza campana. Si conta.
A ben vedere, il Texas hold'em complica il disegno (due carte tue, cinque comuni), ma il mattone resta C. Prima si capisce C(52, 5), poi si passa alle carte sul tavolo.
170! e il tetto della virgola mobile
I fattoriali crescono a una velocità che l'intuito non tiene. 10! = 3.628.800, ancora un numero da quaderno. 20! ≈ 2,43 × 1018, già oltre i secondi di vita dell'universo. 70! ha cento cifre. 170! vale circa 7,26 × 10306 e sfiora il tetto di un double IEEE 754 (circa 1,8 × 10308). 171! quel tetto lo supera: per il calcolatore è «infinito».
Al di sotto di 170! i risultati grandi escono in notazione scientifica. Non è un arrotondamento estetico: è l'unico modo di scrivere 1040 senza occupare tre righe. Figurarsi 90!: non ci sta in un double, e per questo C(90, 6) non si calcola come 90! / (6! 84!), si calcola come prodotto di sei frazioni, una alla volta, tenendo il risultato piccolo fino alla fine.
Oltre n = 170 il fattoriale di questa pagina non esiste, per il computer. Non è che 171! «non si possa pensare»: è che la virgola mobile a 64 bit ha esaurito gli esponenti. Per n enormi servono librerie a precisione arbitraria, non un double. Per combinazioni e disposizioni il prodotto corto va molto più lontano di n! nudo: D e C restano calcolabili quando il fattoriale intermedio, lui, è già esploso.
Se vi serve un ordine di grandezza e non il numero esatto, il logaritmo salva: ln(n!) ≈ n ln n − n (Stirling). Non sostituisce questa pagina. Vi dice se il risultato ha 10 cifre o 200, prima di chiederlo a una macchina che fa overflow.