Il calcolo combinatorio è l'arte di contare in modo sistematico tutte le possibilità di un evento, senza doverle elencare a una a una. Studieremo disposizioni, permutazioni e combinazioni, distinguendo i casi con e senza ripetizione.
Perché contare è difficile (e affascinante)
Immagina di organizzare un torneo di scacchi tra dodici amici e di voler sapere quante partite si dovranno disputare se ognuno gioca contro tutti gli altri. Oppure pensa a quante password di otto caratteri possono esistere usando lettere e cifre: i numeri esplodono e diventa impossibile elencarli a mano. Il combinatorio nasce proprio per rispondere a queste domande con formule precise, evitando errori di conteggio. La differenza tra un problema e l'altro sta in tre aspetti fondamentali: l'ordine conta o no, gli elementi possono ripetersi o no, e quanti elementi scelgo. Padroneggiare queste tre domande è la chiave per scegliere la formula giusta. Vedremo che, dietro a situazioni apparentemente diverse, si nascondono pochi schemi ricorrenti.
Il principio fondamentale del conteggio
Il principio fondamentale, detto anche principio moltiplicativo, afferma che se una scelta può avvenire in m modi e, indipendentemente, una seconda scelta può avvenire in n modi, allora le coppie di scelte possibili sono m · n. Questo principio si estende naturalmente a più scelte successive: basta moltiplicare tutti i numeri di possibilità. Per esempio, se al bar puoi scegliere tra 4 panini, 3 bevande e 2 dolci, i menù completi possibili sono 4 · 3 · 2 = 24. Il ragionamento funziona perché ogni combinazione di scelte produce un esito distinto e nessuno viene contato due volte. Si rappresenta spesso con un diagramma ad albero, utile per visualizzare i rami delle decisioni. Tutte le formule che vedremo derivano, in fondo, da questo principio elementare.
Disposizioni: quando l'ordine conta
Le disposizioni si usano quando scegliamo k elementi da un insieme di n e l'ordine in cui li disponiamo è rilevante. Nelle disposizioni semplici gli elementi non si ripetono e la formula è D(n,k) = n · (n−1) · (n−2) · … · (n−k+1), ossia il prodotto di k fattori decrescenti a partire da n. Pensa al podio di una gara con 10 atleti: il primo posto può essere occupato da 10 persone, il secondo dai 9 rimanenti, il terzo dagli 8 restanti, per un totale di 10 · 9 · 8 = 720 podi diversi. Le disposizioni con ripetizione invece ammettono che lo stesso elemento compaia più volte, e la formula diventa semplicemente n^k. Un classico esempio è il numero di possibili targhe di tre lettere scelte tra 21: il risultato è 21^3 = 9261. La differenza tra i due casi va sempre verificata leggendo bene il testo del problema.
Permutazioni: tutti gli elementi, ordine diverso
Una permutazione è il caso particolare delle disposizioni semplici in cui k coincide con n: stiamo riordinando tutti gli elementi disponibili. Il numero di permutazioni di n oggetti distinti è il fattoriale n! = n · (n−1) · (n−2) · … · 2 · 1, e per convenzione 0! vale 1. Se cinque amici si siedono in fila al cinema, gli ordinamenti possibili sono 5! = 120, perché il primo posto può essere occupato da 5 persone, il secondo da 4, e così via. Quando alcuni elementi sono identici tra loro, però, dobbiamo correggere il conto dividendo per i fattoriali delle ripetizioni: la formula generale è n! / (k1! · k2! · … · kr!). Per esempio, gli anagrammi della parola MAMMA sono 5! / (3! · 2!) = 120 / 12 = 10, perché la M compare tre volte e la A due. Questa correzione evita di contare più volte ordinamenti che, a occhio nudo, appaiono identici.
Combinazioni e coefficiente binomiale
Le combinazioni si usano quando scegliamo k elementi da un insieme di n e l'ordine non ha alcuna importanza, come quando estraiamo carte da un mazzo o formiamo una squadra. Il numero di combinazioni semplici è C(n,k) = n! / (k! · (n−k)!), espressione che si indica anche col simbolo binomiale e si legge "n su k". Tornando al torneo di scacchi tra dodici amici, le partite da disputare sono C(12,2) = 12! / (2! · 10!) = 66. Il coefficiente binomiale gode di proprietà eleganti come la simmetria C(n,k) = C(n,n−k) e la regola di Stifel C(n,k) = C(n−1,k−1) + C(n−1,k), che genera il triangolo di Tartaglia. Esistono anche combinazioni con ripetizione, date dalla formula C(n+k−1, k), utili per esempio quando in pasticceria scegliamo k paste da n gusti potendone prendere più di uno uguale. Riconoscere se l'ordine conta è il discrimine principale tra combinazioni e disposizioni.
Ricorda
- Il principio moltiplicativo è la base di tutto: se le scelte sono indipendenti, si moltiplicano i modi.
- Disposizioni: ordine sì; semplici n·(n−1)·…·(n−k+1), con ripetizione n^k.
- Permutazioni: ordino tutti gli n elementi; n! oppure n!/(k1!·k2!·…) se ci sono ripetizioni.
- Combinazioni: ordine no; C(n,k) = n!/(k!·(n−k)!); proprietà di simmetria e regola di Stifel.
- Domande guida: l'ordine conta? Posso ripetere? Quanti elementi scelgo?
Piccolo esercizio di verifica sul quaderno: in una classe di 20 studenti si devono eleggere un rappresentante e un vice. Calcola in quanti modi diversi può essere formata la coppia carica + persona, poi calcola in quanti modi si possono scegliere semplicemente 2 delegati senza distinguere i ruoli. Confronta i due risultati e spiega con parole tue perché il primo numero è il doppio del secondo, collegando la risposta alla differenza tra disposizioni e combinazioni.