Il calcolo combinatorio studia in quanti modi diversi possiamo scegliere, ordinare o raggruppare oggetti di un insieme finito, rispettando regole precise.
Quando affrontiamo problemi reali, capita spesso di dover contare configurazioni senza poterle elencare una per una. Pensa a quante password di sei caratteri esistono o a quante squadre da cinque giocatori si possono formare in una classe. Il calcolo combinatorio fornisce strumenti per arrivare al risultato corretto senza scriverle tutte. La parola chiave è organizzare il conteggio in modo sistematico, evitando dimenticanze e ripetizioni. In questa scheda distingueremo tre famiglie fondamentali: disposizioni, permutazioni e combinazioni. Ogni famiglia risponde a una domanda diversa sull'ordine e sulla possibilità di ripetere gli elementi.
Principio fondamentale, disposizioni e permutazioni
Alla base di tutto c'è il principio fondamentale del conteggio: se un'azione si compie in due passi successivi, indipendenti tra loro, con m esiti possibili al primo passo e n al secondo, allora gli esiti complessivi sono m · n. Questa regola si generalizza a un numero qualsiasi di passi moltiplicando le possibilità di ciascuno. Da questo principio nascono le disposizioni semplici di n elementi presi k alla volta, indicate con D(n,k), che contano le sequenze ordinate senza ripetizioni: la formula è D(n,k) = n · (n−1) · ... · (n−k+1), cioè n!/(n−k)!. Se invece gli elementi si possono ripetere, parliamo di disposizioni con ripetizione e la formula diventa semplicemente n^k, perché ogni posto ha sempre n scelte disponibili.
Un caso particolare delle disposizioni si ha quando k = n, cioè quando usiamo tutti gli elementi a disposizione: otteniamo le permutazioni semplici, il cui numero è P(n) = n!. Le permutazioni rispondono alla domanda: in quanti modi posso ordinare in fila n oggetti tutti distinti? Quando però alcuni oggetti sono uguali tra loro, occorre dividere n! per i fattoriali delle ripetizioni, ottenendo le permutazioni con ripetizione: la formula è n!/(n1! · n2! · ... · nh!), dove n1, n2, ..., nh sono le molteplicità dei gruppi di elementi identici. Per esempio, gli anagrammi della parola MAMMA si calcolano come 5!/(3!·2!) = 10, perché ci sono tre M e due A.
Combinazioni e coefficienti binomiali
Nelle disposizioni l'ordine conta, mentre nelle combinazioni l'ordine è irrilevante: ciò che interessa è soltanto quali elementi compaiono nel gruppo, non come sono disposti. Le combinazioni semplici di n elementi presi k alla volta, indicate con C(n,k), si calcolano dividendo le disposizioni per il numero di ordinamenti possibili, cioè C(n,k) = n!/(k!·(n−k)!). Questo numero coincide con il coefficiente binomiale scritto come (n su k) e gode di proprietà eleganti: C(n,k) = C(n,n−k) per simmetria, e C(n,k) = C(n−1,k−1) + C(n−1,k), regola che genera il triangolo di Tartaglia. I coefficienti binomiali compaiono anche nello sviluppo della potenza (a+b)^n, dove ogni termine ha la forma C(n,k)·a^(n−k)·b^k.
Esistono infine le combinazioni con ripetizione, utili quando si scelgono k oggetti da n tipi disponibili senza badare all'ordine ma potendo ripetere lo stesso tipo: la loro formula è C(n+k−1, k). Per scegliere correttamente la formula giusta è decisiva una doppia domanda: conta l'ordine degli elementi scelti? gli elementi si possono ripetere? Se la risposta è sì-sì abbiamo disposizioni con ripetizione, sì-no disposizioni semplici, no-no combinazioni semplici, no-sì combinazioni con ripetizione. Questo schema mentale evita gli errori più comuni nei problemi di esame e di olimpiade.
Ricorda
- Il principio fondamentale del conteggio si applica quando le scelte sono indipendenti e si moltiplicano i casi di ogni passo.
- Disposizioni e permutazioni tengono conto dell'ordine; le combinazioni no: prima di scegliere la formula chiediti sempre se l'ordine è rilevante e se si ammettono ripetizioni.
- I coefficienti binomiali C(n,k) si leggono nel triangolo di Tartaglia e descrivono lo sviluppo di (a+b)^n.
- Esercizio di verifica sul quaderno: in una classe di 20 studenti si deve eleggere un presidente, un vicepresidente e un segretario (cariche distinte, una persona per carica). Quanti esiti diversi sono possibili? Poi, sempre nella stessa classe, in quanti modi si può formare una delegazione di 3 studenti per un convegno (senza distinzione di ruoli)? Confronta i due risultati e spiega per iscritto perché il primo è maggiore del secondo.