Il calcolo combinatorio è quella branca della matematica che si occupa di contare in quanti modi diversi possiamo organizzare, scegliere o disporre un insieme di oggetti. Imparare a contare con precisione è una competenza preziosa: serve in probabilità, in informatica, nella crittografia e perfino quando si pianifica un torneo sportivo o si decide la password di un account.
Introduzione: contare senza enumerare
Immagina di voler stabilire quante targhe automobilistiche diverse si possono creare con due lettere seguite da tre cifre e altre due lettere: scrivere tutte le possibilità una per una sarebbe un'impresa titanica e soggetta a errori. Il calcolo combinatorio nasce proprio per rispondere a domande di questo tipo senza dover elencare materialmente ogni caso. Con poche regole eleganti riusciamo a determinare numeri enormi, spesso superiori a milioni o miliardi, in pochi secondi. Le situazioni concrete in cui questo strumento è utile sono moltissime: pensa al numero di possibili estrazioni del Lotto, al numero di anagrammi di una parola o al numero di squadre da quattro persone formabili da una classe di venti studenti. In tutti questi casi, dietro a una domanda apparentemente semplice si nasconde una struttura matematica precisa che possiamo analizzare. Lo studio del calcolo combinatorio richiede attenzione, perché spesso piccole differenze nel testo del problema cambiano radicalmente la formula da applicare. Per questo motivo dedicheremo molto spazio a distinguere i casi e a riconoscere gli indizi linguistici che ci guidano nella scelta corretta.
Il principio fondamentale del conteggio
Il punto di partenza di tutto il calcolo combinatorio è il principio moltiplicativo del conteggio, che afferma quanto segue: se una scelta può essere effettuata in m modi e indipendentemente da essa una seconda scelta può essere effettuata in n modi, allora le due scelte insieme possono essere fatte in m · n modi. Questo principio si estende a un numero qualsiasi di scelte successive e indipendenti, semplicemente moltiplicando il numero di possibilità per ciascuna di esse. Un esempio classico è la composizione di un menù: se in pizzeria abbiamo 4 antipasti, 6 primi e 3 dolci, il numero di pasti completi diversi che possiamo ordinare è 4 · 6 · 3 = 72. Un secondo esempio riguarda il codice di un lucchetto a combinazione con tre rotelle, ciascuna numerata da 0 a 9: poiché ogni rotella offre 10 possibilità indipendenti, i codici possibili sono 10 · 10 · 10 = 1000. Il principio funziona anche quando le scelte non sono indipendenti, purché il numero di alternative della seconda scelta non dipenda da quale opzione abbiamo selezionato nella prima. Tieni sempre presente che il segreto è suddividere il problema in passi successivi e contare con attenzione le opzioni di ciascuno.
Il fattoriale
Prima di affrontare permutazioni e combinazioni dobbiamo introdurre uno strumento essenziale: il fattoriale di un numero naturale n, indicato con n!, definito come il prodotto di tutti i numeri interi positivi da 1 a n. Quindi n! = n · (n − 1) · (n − 2) · … · 2 · 1, con la convenzione importante che 0! = 1, scelta apparentemente strana ma indispensabile per la coerenza delle formule. I primi valori sono 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720 e crescono molto rapidamente, tanto che 10! supera già i tre milioni. Per fare un esempio concreto, se vogliamo sapere in quanti modi diversi possiamo ordinare i 5 libri di una mensola, la risposta è 5! = 120, perché il primo posto offre 5 scelte, il secondo 4, e così via fino a 1. Un altro esempio quotidiano: se sette amici si mettono in fila per una foto, le possibili disposizioni sono 7! = 5040. Nei calcoli con il fattoriale è molto utile semplificare frazioni come 8!/6! senza calcolare i fattoriali per intero, scrivendo 8!/6! = 8 · 7 = 56. Questa abitudine fa risparmiare tempo ed evita errori con numeri grandi.
Disposizioni semplici e con ripetizione
Le disposizioni si occupano di scelte ordinate in cui conta la posizione degli oggetti. Si chiamano disposizioni semplici di n oggetti presi k alla volta quando gli oggetti scelti devono essere tutti diversi: la formula è D(n,k) = n · (n−1) · (n−2) · … · (n−k+1) = n!/(n−k)!. Per esempio, se in una gara con 8 atleti vogliamo sapere quanti diversi podi (primo, secondo e terzo posto) sono possibili, calcoliamo D(8,3) = 8 · 7 · 6 = 336. Si parla invece di disposizioni con ripetizione quando lo stesso oggetto può essere scelto più volte, e la formula diventa D'(n,k) = n^k. L'esempio del lucchetto visto prima è proprio un caso di disposizioni con ripetizione di 10 cifre prese 3 alla volta: 10³ = 1000. Un secondo esempio illuminante riguarda le colonne del Totocalcio: con 3 segni possibili (1, X, 2) per ognuna delle 13 partite, le colonne diverse sono 3¹³ = 1.594.323. La differenza chiave tra le due tipologie è semplice ma fondamentale: nelle semplici un oggetto, una volta usato, esce di scena, mentre nelle disposizioni con ripetizione rimane sempre disponibile. Riconoscere quale dei due casi si applica è il primo passo verso la soluzione corretta di ogni problema.
Permutazioni semplici e con ripetizione
Le permutazioni sono un caso particolare delle disposizioni: si hanno quando si considerano tutti gli n oggetti disponibili, cioè quando k = n. Il numero di permutazioni semplici di n oggetti distinti è quindi P(n) = n!, perché tutti gli oggetti devono essere disposti in fila senza ripetizioni. Per esempio, gli anagrammi (anche privi di senso) della parola ROMA sono 4! = 24, e si possono effettivamente elencare con un po' di pazienza. Quando però alcuni oggetti sono indistinguibili tra loro la formula cambia: parliamo di permutazioni con ripetizione di n oggetti con gruppi di cardinalità k₁, k₂, …, kᵣ, e la formula è P(n; k₁, k₂, …, kᵣ) = n!/(k₁! · k₂! · … · kᵣ!). Per esempio, gli anagrammi della parola MAMMA sono 5!/(3! · 2!) = 120/12 = 10, perché ci sono tre M indistinguibili e due A indistinguibili. Un secondo esempio: gli anagrammi della parola MATEMATICA contano 10 lettere con A che compare 3 volte, M che compare 2 volte e T che compare 2 volte, quindi 10!/(3! · 2! · 2!) = 151.200. La logica sottostante è chiara: dividiamo per i fattoriali dei gruppi ripetuti perché tutti gli ordini interni di lettere uguali producono la stessa parola e vanno contati una sola volta.
Combinazioni semplici e coefficienti binomiali
Quando l'ordine non conta entriamo nel regno delle combinazioni. Si chiamano combinazioni semplici di n oggetti presi k alla volta i sottoinsiemi di k elementi che si possono formare da un insieme di n elementi distinti, e si calcolano con la formula C(n,k) = n!/[k!(n−k)!]. Questo numero si indica anche con il simbolo del coefficiente binomiale, scritto come (n su k), e gode di proprietà eleganti, come C(n,k) = C(n,n−k) e C(n,k) = C(n−1,k−1) + C(n−1,k), che è la relazione fondamentale del triangolo di Tartaglia. Un esempio pratico: in una classe di 25 studenti vogliamo formare una commissione di 4 ragazzi; poiché l'ordine in cui scegliamo i membri è irrilevante, le commissioni possibili sono C(25,4) = 25!/(4! · 21!) = 12.650. Un altro esempio celebre è il Superenalotto: si scelgono 6 numeri da un insieme di 90, e l'ordine non conta, quindi le possibili combinazioni vincenti sono C(90,6) = 622.614.630. Esistono anche le combinazioni con ripetizione, calcolate come C'(n,k) = C(n+k−1,k), utili quando si sceglie con possibilità di ripetere, come accade comprando 5 gusti di gelato (anche uguali) da una gelateria che ne offre 12.
Quando ordine, quando no: la bussola per scegliere la formula
La maggiore difficoltà del calcolo combinatorio non è applicare le formule, ma scegliere quella giusta. Il primo criterio da considerare è sempre se l'ordine degli elementi conta o non conta: se conta useremo disposizioni o permutazioni, se non conta useremo combinazioni. Il secondo criterio è se gli oggetti possono essere ripetuti o devono essere tutti diversi: questo distingue le formule semplici da quelle con ripetizione. Per esempio, formare un numero di telefono richiede di considerare l'ordine (321 è diverso da 123) e ammette ripetizioni, quindi siamo nelle disposizioni con ripetizione. Pescare 5 carte da un mazzo per ricevere una mano da poker invece non considera l'ordine (le stesse 5 carte formano sempre la stessa mano) e non ammette ripetizioni, quindi si tratta di combinazioni semplici: C(52,5) = 2.598.960. Per allenare l'intuizione conviene riformulare ogni problema con la domanda: "Se scambio due elementi, ottengo qualcosa di diverso?" Se la risposta è sì conta l'ordine, se è no non conta. Un'altra domanda chiave è: "Posso usare lo stesso elemento due volte?"; in base alla risposta scegli la formula con o senza ripetizione.
Ricorda
- Il principio moltiplicativo è il fondamento: m scelte indipendenti seguite da n scelte producono m · n esiti.
- Il fattoriale n! è il prodotto degli interi da 1 a n, con la convenzione 0! = 1.
- Disposizioni semplici D(n,k) = n!/(n−k)! contano scelte ordinate senza ripetizione.
- Disposizioni con ripetizione D'(n,k) = n^k contano scelte ordinate con ripetizione.
- Permutazioni semplici P(n) = n! contano gli ordinamenti di n oggetti distinti.
- Permutazioni con ripetizione P(n; k₁,...,kᵣ) = n!/(k₁!·...·kᵣ!) gestiscono gli oggetti indistinguibili.
- Combinazioni semplici C(n,k) = n!/[k!(n−k)!] contano sottoinsiemi senza considerare l'ordine.
- Prima di scegliere la formula, chiediti sempre: l'ordine conta? gli elementi possono ripetersi?
Esercizio di verifica da svolgere subito sul quaderno: in una pasticceria ci sono 9 gusti diversi di pasticcini. Calcola (a) in quanti modi puoi scegliere una scatola da 4 pasticcini tutti di gusti diversi senza che l'ordine conti, (b) in quanti modi puoi disporli in una vetrina lineare considerando l'ordine, (c) quanti vassoi diversi da 4 pasticcini puoi comporre se ammetti gusti ripetuti senza che conti l'ordine, (d) quante codifiche colorate diverse ottieni se associ a ogni pasticcino uno dei 9 gusti con possibilità di ripetizione e l'ordine conta. Confronta i quattro risultati e spiega a parole quale tipo di calcolo combinatorio hai usato in ogni caso.