Scegliere la formula giusta: ordine e ripetizione
Le formule di conteggio applicabili sono quattro e dipendono da due domande indipendenti: l'ordine conta? La ripetizione è ammessa?
| L'ordine conta? | Ripetizione ammessa? | Formula | Situazione di esempio |
|---|---|---|---|
| Sì | No | nPr = n! ÷ (n − r)! | Assegnare primo, secondo e terzo posto fra 7 corridori |
| Sì | Sì | nʳ | Creare un PIN di 3 cifre con le cifre da 0 a 6, ripetizioni ammesse |
| No | No | nCr = n! ÷ (r!(n−r)!) | Scegliere una commissione di 3 persone fra 7 candidati |
| No | Sì | C(n+r−1, r) | Scegliere 3 palline fra 7 gusti di gelato, ripetizioni ammesse |
- A parità di n e r, nCr è sempre minore o uguale a nPr, precisamente nCr = nPr ÷ r!, poiché le combinazioni riducono a un unico conteggio tutti gli r! ordinamenti degli stessi elementi.
- Quando r = 0, sia nPr sia nCr valgono 1 per convenzione: esiste esattamente un modo di non selezionare alcun elemento, cioè la selezione vuota.
- Quando r = n e non è ammessa la ripetizione, si ha nPr = n! e nCr = 1: esiste un solo modo di «scegliere» tutti gli n elementi come insieme non ordinato, mentre i modi di disporli tutti in ordine sono n!.
Che cosa sono permutazioni e combinazioni?
Una permutazione è una disposizione di elementi in cui l'ordine conta. Il numero di permutazioni di r elementi scelti da un insieme di n elementi distinti, senza ripetizione, si scrive nPr e conta disposizioni del tipo «primo posto, secondo posto, terzo posto», in cui scambiare due elementi selezionati dà un esito diverso e ben distinto.
Una combinazione è invece una selezione di elementi in cui l'ordine non conta. Il numero di combinazioni di r elementi scelti fra n distinti si scrive nCr, si legge «n su r» e coincide con il coefficiente binomiale: conta raggruppamenti come una commissione o una mano di carte, dove gli stessi elementi disposti in ordine diverso valgono come un unico esito.
La domanda che discrimina è dunque questa: riordinare gli stessi elementi scelti cambia il risultato? Se sì, come nell'assegnare medaglie d'oro, d'argento e di bronzo o nel disporre libri su uno scaffale, servono le permutazioni. Se no, come nello scegliere una commissione di tre persone o nel ricevere una mano di carte, servono le combinazioni. Il calcolatore riporta anche le varianti «con ripetizione», valide quando uno stesso elemento può essere scelto più volte: per esempio le cifre di un PIN oppure le palline di gelato quando si può ripetere lo stesso gusto.
Come usare questo calcolatore di permutazioni e combinazioni
- Inserisci n, cioè il numero totale di elementi distinti fra cui scegliere.
- Inserisci r, cioè il numero di elementi da selezionare o disporre. r deve essere minore o uguale a n: se r supera n, il calcolatore non restituisce alcun risultato, nemmeno quelli con ripetizione.
- Leggi le permutazioni (nPr) se l'ordine di selezione conta e la ripetizione non è ammessa, oppure le combinazioni (nCr) se l'ordine è irrilevante e la ripetizione non è ammessa.
- Nelle situazioni in cui uno stesso elemento può essere scelto più volte, usa i risultati «con ripetizione» anziché i valori standard di nPr e nCr.
Le formule di permutazioni e combinazioni
Il numero di permutazioni di r elementi scelti fra n, senza ripetizione, è nPr = n! ÷ (n − r)!, equivalente al prodotto di r interi consecutivi decrescenti a partire da n. Esempio svolto con n = 7 e r = 3: 7P3 = 7 × 6 × 5 = 210, ossia in quanti modi si possono assegnare un primo, un secondo e un terzo premio distinti fra 7 concorrenti.
Il numero di combinazioni di r elementi scelti fra n, senza ripetizione, è nCr = n! ÷ (r! × (n − r)!) = nPr ÷ r!. La divisione elimina gli r! modi di ordinare ciascun gruppo selezionato, poiché le combinazioni non distinguono l'ordine. Esempio svolto con n = 7 e r = 3: 7C3 = 210 ÷ 3! = 210 ÷ 6 = 35, cioè quante commissioni distinte da 3 persone si possono formare fra 7 candidati.
Le permutazioni con ripetizione, in cui ciascuna delle r posizioni può accogliere indipendentemente uno qualsiasi degli n elementi, valgono semplicemente nʳ. Per n = 7 e r = 3: 7³ = 343, per esempio il numero di codici distinti di 3 cifre formati con le cifre da 0 a 6 se le ripetizioni sono ammesse. Le combinazioni con ripetizione si ottengono invece con la formula «stelle e barre», C(n + r − 1, r). Per n = 7 e r = 3: C(9, 3) = 84, per esempio in quanti modi si possono scegliere 3 palline di gelato fra 7 gusti quando i gusti ripetuti sono ammessi e l'ordine non conta.
Errori comuni
- Usare la formula delle permutazioni quando in realtà l'ordine non conta, o viceversa: prima di scegliere la formula, verifica se scambiare due elementi selezionati cambia l'esito.
- Trascurare di controllare se la ripetizione sia ammessa: «scegliere un PIN», dove le cifre possono ripetersi, richiede una formula diversa da «distribuire carte da un mazzo», dove le carte non tornano nel mazzo.
- Applicare nPr o nCr con r maggiore di n in assenza di ripetizione: l'espressione è indefinita, poiché non si possono selezionare più elementi distinti di quanti l'insieme ne contenga senza ripeterne almeno uno.
- Confondere le combinazioni con ripetizione, cioè la formula «stelle e barre», con il semplice nCr: i due conteggi danno risultati molto diversi e valgono per situazioni diverse, con o senza ripetizioni.
Domande frequenti
Che differenza c'è fra una permutazione e una combinazione?
Una permutazione conta le disposizioni in cui l'ordine conta, con nPr = n! ÷ (n−r)!, come nell'assegnare primo, secondo e terzo posto. Una combinazione conta invece le selezioni in cui l'ordine è irrilevante, con nCr = n! ÷ (r!(n−r)!), come nello scegliere una commissione. Per n = 7 e r = 3: 7P3 = 210 con l'ordine, ma 7C3 = 35 senza, poiché ogni gruppo di 3 persone si può disporre in 3! = 6 ordini diversi e 210 ÷ 6 = 35.
Come si calcola nCr, cioè «n su r»?
Si usa la formula nCr = n! ÷ (r! × (n − r)!). Per n = 7 e r = 3: 7C3 = 7! ÷ (3! × 4!) = 5.040 ÷ (6 × 24) = 5.040 ÷ 144 = 35. In alternativa si calcola prima nPr, cioè 7 × 6 × 5 = 210, e si divide per r!, cioè 3! = 6: 210 ÷ 6 = 35.
Come si calcola nPr?
Si usa la formula nPr = n! ÷ (n − r)!, che si semplifica nel prodotto di r interi consecutivi decrescenti a partire da n. Per n = 7 e r = 3: 7P3 = 7 × 6 × 5 = 210.
Quando conviene ammettere la ripetizione in un problema di conteggio?
La ripetizione va ammessa quando uno stesso elemento può comparire più volte in un singolo esito: per esempio le cifre di un codice PIN, oppure i gusti di gelato se il cliente può ripetere lo stesso gusto su più palline. Non va ammessa quando ciascun elemento si può usare una volta sola, come nel distribuire carte da gioco distinte o nell'assegnare persone diverse a ruoli diversi.
Quanto vale nPr quando r è uguale a n?
Quando r = n, cioè disponendo tutti gli n elementi senza ripetizione, nPr si semplifica in n! ÷ (n − n)! = n! ÷ 0! = n! ÷ 1 = n!. Il valore rappresenta il numero totale di modi di allineare tutti gli n elementi distinti: per esempio, 5 elementi si possono disporre in 5! = 120 modi.
Che cosa significa «stelle e barre» per le combinazioni con ripetizione?
«Stelle e barre» è la tecnica combinatoria standard per contare le combinazioni con ripetizione e porta alla formula C(n + r − 1, r). Il metodo rappresenta gli r elementi scelti come «stelle» separate da «barre» che segnano i confini fra le n categorie, e conta poi le disposizioni di stelle e barre. Per n = 7 e r = 3: C(9, 3) = 84.
Fonti
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018. (Permutations, combinations, and the stars-and-bars method.)
- NIST Digital Library of Mathematical Functions (DLMF), §26.1–26.3 Combinatorial Analysis. dlmf.nist.gov.
- Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed. Wiley, 1968. (Classic treatment of permutations and combinations.)