Calcolo combinatorio: permutazioni, disposizioni e combinazioni

Come funziona il calcolo

Il calcolo combinatorio risponde alla domanda «in quanti modi?»: quante scelte, quanti ordinamenti e quanti gruppi si possono formare con gli elementi di un insieme finito. Il punto di partenza è il principio fondamentale: se una scelta si può fare in p modi e, indipendentemente, un’altra in q modi, le due scelte insieme si possono fare in p · q modi. Con 3 primi e 4 secondi si compongono 3 · 4 = 12 menù diversi; con tre scelte indipendenti si moltiplicano tre numeri, e così via.

Lo schema per scegliere la formula è questo. Se i gruppi si formano senza contare l’ordine sono combinazioni; se l’ordine conta sono disposizioni; se si mettono in fila tutti gli n elementi sono permutazioni. In ogni caso si distingue poi se gli elementi si possono ripetere oppure no. Il menu in cima al calcolatore offre le sei possibilità e, sotto il calcolatore, trovi i passaggi e la formula applicati ai tuoi numeri.

Senza ripetizione le formule sono tre. Le permutazioni di n elementi sono n!, il fattoriale, cioè il prodotto dei numeri da 1 a n: 5! = 120. Le disposizioni di n elementi presi k alla volta sono n! / (n − k)!, che equivale a moltiplicare k numeri decrescenti a partire da n: con n = 10 e k = 3 si ha 10 · 9 · 8 = 720. Le combinazioni si ottengono dividendo le disposizioni per le k! permutazioni degli elementi scelti, perché l’ordine non conta: n! / (k! · (n − k)!), che per 10 elementi presi 3 alla volta dà 720 / 6 = 120.

Con ripetizione lo stesso elemento si può usare più volte. Le disposizioni con ripetizione sono n elevato a k: un PIN di 4 cifre ha 10 · 10 · 10 · 10 = 10.000 possibilità. Le combinazioni con ripetizione sono (n + k − 1)! / (k! · (n − 1)!): prendere 3 gusti di gelato tra 5, anche ripetuti, dà 35 possibilità. Le permutazioni con ripetizione servono quando alcuni elementi sono uguali tra loro: si divide n! per il fattoriale della dimensione di ogni gruppo di elementi uguali. Gli anagrammi di MATEMATICA, con M due volte, A tre e T due, sono 10! / (2! · 3! · 2!) = 151.200.

I risultati crescono in fretta: i modi di ordinare un mazzo da 52 carte sono 52!, un numero di 68 cifre. Il calcolatore usa numeri interi esatti e mostra tutte le cifre, senza arrotondare. Un esempio italiano è il SuperEnalotto: si scelgono 6 numeri tra 90 e l’ordine non conta, quindi le combinazioni sono 622.614.630 e la probabilità di indovinare la sestina vincente con una sola giocata è 1 su 622.614.630. Per trasformare in percentuale un rapporto tra casi favorevoli e casi possibili, come 3 su 120, cioè il 2,5%, c’è il calcolo percentuale; per ridurlo ai minimi termini, il calcolo delle frazioni.

La formula

Le disposizioni contano le sequenze, perciò (A, B) e (B, A) sono diverse; le combinazioni contano i gruppi, perciò il gruppo formato da A e B è lo stesso comunque lo si scriva. Ogni gruppo di k elementi distinti si può ordinare in k! modi, quindi le disposizioni sono k! volte le combinazioni: da qui C = D / k!.

Il fattoriale cresce molto in fretta: 10! = 3.628.800, 20! supera i due miliardi di miliardi e 52! ha 68 cifre. Per n grandi esiste l’approssimazione di Stirling, n! ≈ √(2πn) · (n / e) elevato a n, in cui compare una radice quadrata (per quella c’è il calcolo della radice quadrata); il calcolatore però non approssima, usa interi esatti.

Per convenzione 0! = 1 e anche con k = 0 ogni formula dà 1: c’è un solo modo di non scegliere nulla. Qui n va da 2 a 100 e k da 0 a 100; senza ripetizione k non può superare n, e nelle permutazioni con ripetizione i gruppi di elementi uguali non possono contenere più elementi del totale.