Calcolo combinatorio: le formule per contare le possibilità

Secondo l’Enciclopedia della Matematica Treccani, il calcolo combinatorio si occupa di contare le possibilità: quante disposizioni, quante scelte, quanti ordinamenti nascono da un insieme di elementi, senza bisogno di elencarli a uno a uno. Alla base c’è il principio di moltiplicazione: se una prima scelta ha un certo numero di esiti e una seconda, indipendente dalla prima, ne ha un altro, gli esiti complessivi delle due scelte insieme si ottengono moltiplicando i due numeri. È la stessa logica che regge ogni formula qui sotto, dalle permutazioni alle combinazioni con ripetizione.

Permutazioni: ordinare tutti gli elementi

Una permutazione semplice è un ordinamento che usa tutti gli n oggetti a disposizione, come spiegano le dispense di Statistica e analisi dei dati con Python dell’Università degli Studi di Milano. Il loro numero è n!, il fattoriale di n: si moltiplicano tutti i numeri interi da 1 a n, perché la prima posizione ha n scelte possibili, la seconda ne ha una di meno e così via, fino all’ultima posizione che resta obbligata. Il fattoriale è una delle poche operazioni del calcolo letterale che cresce più in fretta di qualsiasi potenza, e per questo i numeri delle permutazioni diventano enormi già con pochi elementi.

Quando tra gli n oggetti ce ne sono alcuni indistinguibili tra loro, per esempio due gruppi di elementi uguali di n1 e n2 pezzi, le dispense milanesi indicano di dividere n! per il prodotto dei fattoriali delle dimensioni di ogni gruppo, altrimenti si conterebbero più volte ordinamenti che, scambiando gli elementi uguali, restano identici.

Disposizioni: l’ordine conta, ma non si usano tutti gli elementi

Le disposizioni scelgono solo k elementi tra gli n disponibili, mantenendo l’ordine come fattore distintivo. Nella versione senza ripetizione, un elemento già scelto non può tornare a disposizione per la scelta successiva: le dispense di Milano calcolano il totale come n!/(n-k)!, perché equivale a una permutazione fermata dopo k passi invece di arrivare in fondo a n.

Esempio pratico: per contare i numeri di telefono di 7 cifre tutte diverse, scelte tra le 10 cifre da 0 a 9, si applica proprio questa formula; il risultato, secondo le dispense milanesi, è 604.800 numeri possibili.

Nelle disposizioni con ripetizione, invece, uno stesso elemento può comparire più di una volta nello stesso gruppo ordinato, come indica anche l’Enciclopedia della Matematica Treccani. Il conteggio allora si fa applicando il principio di moltiplicazione k volte di seguito, cioè n moltiplicato per sé stesso k volte, n elevato a k. Math Is Fun lo illustra con un lucchetto a combinazione che usa 3 cifre scelte tra le 10 disponibili: ogni cifra può ripetersi, quindi i codici possibili sono 10 per 10 per 10, mille in tutto. Nelle disposizioni senza ripetizione, invece, ogni scelta successiva parte da un’opzione in meno rispetto alla precedente: Math Is Fun calcola così i modi di ordinare 3 palle da biliardo scelte tra 16 disponibili, arrivando a 3.360 possibilità, un numero molto più alto delle combinazioni corrispondenti, perché qui ogni ordine diverso delle stesse tre palle conta come un caso separato. La differenza tra numeri ordinali e numeri cardinali aiuta a ricordarla: le disposizioni rispondono a una domanda che dipende dalla posizione, primo, secondo, terzo, le combinazioni solo dalla quantità.

Combinazioni: l’ordine non conta

Treccani usa l’esempio di un gruppo di cinque carte per mostrare la differenza: in una combinazione importa quali carte si hanno in mano, non in quale sequenza sono state pescate, a differenza di una disposizione. Quando un elemento non può tornare una seconda volta, il loro numero si ottiene dividendo per k! le disposizioni che seguono la stessa regola, il numero di ordini possibili di k elementi; il risultato corrisponde al coefficiente binomiale «n su k».

Una proprietà di questo coefficiente, mostrata da Math Is Fun, è la simmetria: scegliere 3 palle su 16 porta allo stesso numero di combinazioni possibili, 560, che scegliere le restanti 13 su 16.

Le combinazioni con ripetizione aggiungono la possibilità di ripetere un elemento: si contano come il coefficiente binomiale di n+k-1 su k. Math Is Fun lo mostra scegliendo 3 palline di gelato tra 5 gusti, potendo ripetere un gusto: il risultato è 35 combinazioni possibili. Le dispense milanesi arrivano allo stesso tipo di formula lanciando 3 dadi indistinguibili a 6 facce, dove una faccia può ripetersi: il risultato è 56 combinazioni. Se invece si chiede che le tre facce escano tutte diverse, il conteggio cambia del tutto: 120 esiti se i dadi sono distinguibili e contati come disposizione, 20 se sono indistinguibili e contati come combinazione. La domanda che si pone — ripetizione ammessa o facce tutte diverse, dadi distinguibili o no — decide quale delle tre formule usare.

Le formule in uno schema

Tipo	L’ordine conta?	Un elemento si può ripetere?	Formula
Permutazioni semplici	Sì, si usano tutti gli n elementi	No	n!
Permutazioni con elementi ripetuti	Sì	elementi uguali già contati nel gruppo	n! diviso il prodotto dei fattoriali di ogni gruppo uguale
Disposizioni senza ripetizione	Sì	No	n!/(n-k)!
Disposizioni con ripetizione	Sì	Sì	n elevato a k
Combinazioni senza ripetizione	No	No	coefficiente binomiale n su k
Combinazioni con ripetizione	No	Sì	coefficiente binomiale di n+k-1 su k

Una storia tra Seicento e Settecento

Secondo la voce «Analisi combinatoria» dell’Enciclopedia Italiana Treccani, i primi studi organici sull’argomento compaiono nel Traité du triangle arithmétique di Blaise Pascal, del 1654. Gottfried Wilhelm Leibniz vi dedica la Dissertatio de arte combinatoria nel 1666, John Wallis lo tratta nel suo Treatise of Algebra del 1685, Bernard Frénicle de Bessy scrive l’Abrégé des combinaisons nel 1693. Jakob Bernoulli lo riprende nell’Ars coniectandi del 1713 e Abraham de Moivre nella Doctrine of chances del 1718: sei opere in meno di settant’anni, nel Seicento e nel primo Settecento.

Il calcolo combinatorio torna ogni volta che serve contare gli esiti possibili di un esperimento, ed è uno dei mattoni su cui poggia la probabilità e la statistica: sapere quanti sono i casi favorevoli e quanti i casi totali è il primo passo per calcolare una probabilità, anche quella condizionata che sta alla base del teorema di Bayes. Chi lavora con i numeri naturali e gli altri insiemi numerici incontra il fattoriale e il coefficiente binomiale proprio a partire da queste formule, prima ancora di vederli applicati alla probabilità.