La domanda chiave: l'ordine conta?
Permutazioni e combinazioni contano entrambe il numero di modi in cui si possono scegliere r elementi da un gruppo di n elementi distinti, ma rispondono a due domande diverse. Una permutazione conta il numero di modi in cui si possono scegliere e disporre r elementi, quindi due selezioni contenenti gli stessi identici elementi in ordine diverso sono conteggiate come due risultati distinti. Una combinazione conta solo il numero di modi in cui si possono scegliere r elementi, quindi due selezioni contenenti gli stessi identici elementi sono conteggiate come un unico risultato, indipendentemente dall'ordine in cui sono stati scelti.
Un modo semplice per decidere quale delle due si applica: immagina due selezioni che usano esattamente gli stessi elementi ma li elencano o li dispongono in modo diverso. Se quelle due selezioni rappresentano risultati concreti realmente diversi — classifiche diverse, password diverse, ordini di arrivo diversi in una gara — allora l'ordine conta e la permutazione è il conteggio corretto. Se quelle due selezioni rappresentano lo stesso risultato concreto — la stessa commissione, la stessa mano di carte, lo stesso insieme di numeri della lotteria — allora l'ordine non conta e la combinazione è il conteggio corretto.
Le formule: nPr e nCr, con un esempio verificato
Il numero di permutazioni di r elementi scelti tra n elementi distinti è nPr = n! / (n − r)!, e il numero di combinazioni è nCr = n! / [r! (n − r)!] — la formula delle combinazioni è la formula delle permutazioni divisa per r!, perché dividere per r! elimina i r! diversi ordinamenti di ogni gruppo di elementi identici che il conteggio delle permutazioni tratta come distinti.
Esempio svolto: scegliere 3 elementi da un gruppo di 7. Permutazioni: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Combinazioni: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. Il conteggio delle combinazioni è esattamente il conteggio delle permutazioni diviso per 3! = 6, il che conferma la relazione nCr = nPr / r!.
| Quantità | Formula | Valore per n=7, r=3 |
|---|---|---|
| Permutazioni (l'ordine conta) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Combinazioni (l'ordine non conta) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
Con ripetizione e senza ripetizione
Entrambe le formule sopra presuppongono che ciascuno degli n elementi possa essere selezionato al massimo una volta — campionamento senza ripetizione. Quando gli elementi possono essere riutilizzati (campionamento con ripetizione, detto anche campionamento con reimmissione), le formule di conteggio cambiano. Le permutazioni con ripetizione consentita elevano semplicemente n alla potenza r, poiché ciascuna delle r posizioni dispone in modo indipendente di tutte le n scelte, a prescindere da ciò che è stato scelto prima: n^r.
Le combinazioni con ripetizione consentita usano una formula diversa, C(n + r − 1, r), che conta in quanti modi si possono scegliere r elementi tra n tipi quando le ripetizioni sono ammesse e l'ordine continua a non contare — è un caso di cui si ha bisogno meno spesso, ma che si presenta, per esempio, quando si scelgono palline di gelato tra n gusti potendo prendere più volte lo stesso gusto.
| Caso | Formula | Esempio tipico |
|---|---|---|
| Permutazioni, senza ripetizione | n! / (n − r)! | Stilare la classifica dei 3 vincitori tra 7 finalisti |
| Permutazioni, con ripetizione | n^r | Un PIN di 4 cifre in cui le cifre possono ripetersi |
| Combinazioni, senza ripetizione | n! / [r!(n − r)!] | Scegliere 6 numeri per una schedina della lotteria |
| Combinazioni, con ripetizione | (n + r − 1)! / [r!(n − 1)!] | Scegliere 3 palline tra 5 gusti di gelato, ripetizioni ammesse |
Esempi svolti: un codice PIN e una schedina della lotteria
Un PIN di 4 cifre, in cui ciascuna delle 4 posizioni può essere una cifra qualsiasi da 0 a 9 e le cifre possono ripetersi (la regola tipica dei PIN bancari), è un esempio di permutazioni con ripetizione: l'ordine conta (1234 e 4321 sono PIN diversi) e la ripetizione è consentita, il che dà 10^4 = 10.000 PIN possibili. Se invece le cifre ripetute non fossero ammesse, il conteggio scenderebbe al valore delle permutazioni senza ripetizione, 10P4 = 10 × 9 × 8 × 7 = 5.040 — meno possibilità, perché ogni cifra usata toglie un'opzione alle posizioni rimanenti.
Un formato classico di lotteria che estrae 6 numeri da un insieme di 49, senza numeri ripetuti e in cui l'ordine di estrazione è irrilevante ai fini della vincita, è un esempio di combinazioni senza ripetizione: C(49, 6) = 49! / (6! × 43!) = 13.983.816. Questa cifra enorme è esattamente il motivo per cui tali formati di lotteria sono descritti come giochi a probabilità remota — un conteggio combinatorio cresce moltissimo e molto in fretta quando n cresce rispetto a r, perché conta gruppi non ordinati estratti da un insieme ampio anziché un piccolo numero fisso di disposizioni.
Un modo rapido per ricordare quale formula usare
«Permutazione» e «posizione» condividono l'idea di collocazione, e un utile aiuto mnemonico è che le permutazioni si interessano alla posizione — cioè a dove finisce ciascun elemento nella sequenza. «Combinazione» descrive invece un gruppo combinato, come il contenuto di un sacchetto o una commissione, in cui conta solo l'appartenenza, non la sequenza in cui i membri sono stati aggiunti.
Password, PIN, classifiche di gara e qualsiasi disposizione di posti o di orari sono problemi di permutazione, perché scambiare l'ordine cambia il risultato. Mani di carte, insiemi di numeri della lotteria, composizioni di commissioni e qualsiasi selezione di un gruppo non ordinato sono problemi di combinazione, perché l'unica cosa che conta sono i membri, non la sequenza in cui sono stati scelti.
Domande frequenti
Qual è la differenza tra una permutazione e una combinazione?
Una permutazione conta le disposizioni in cui l'ordine conta, quindi scegliere gli stessi elementi in ordine diverso conta come un risultato diverso. Una combinazione conta le selezioni in cui l'ordine non conta, quindi gli stessi elementi in qualsiasi ordine contano come un unico risultato. Entrambe partono dallo stesso gruppo di n elementi e prevedono di sceglierne r, ma il conteggio delle permutazioni è sempre maggiore o uguale al corrispondente conteggio delle combinazioni per gli stessi n e r.
Quanto vale 7P3 e come si calcola?
7P3 è uguale a 210, il numero di modi in cui si possono scegliere e disporre 3 elementi da un gruppo di 7 elementi distinti quando l'ordine conta. Si calcola come 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, moltiplicando tra loro i tre fattori maggiori di 7! poiché i fattori minori si semplificano con (7−3)! al denominatore.
Quanto vale 7C3 e come si calcola?
7C3 è uguale a 35, il numero di modi in cui si possono scegliere 3 elementi da un gruppo di 7 elementi distinti quando l'ordine non conta. Si calcola come 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 — esattamente il conteggio delle permutazioni, 7P3 = 210, diviso per 3! (il numero di modi di riordinare ogni gruppo di 3), poiché le combinazioni riducono tutti gli ordinamenti dello stesso gruppo a un unico risultato.
Perché i PIN usano le permutazioni e le lotterie le combinazioni?
Un PIN tratta 1234 e 4321 come codici diversi, quindi l'ordine delle cifre cambia il risultato: si tratta di uno scenario di permutazione — con ripetizione consentita per un tipico PIN di 4 cifre, il che dà 10^4 = 10.000 possibilità. Una schedina della lotteria vince solo in base a quali numeri sono stati estratti, non all'ordine di uscita, quindi due estrazioni con gli stessi numeri in ordine diverso sono lo stesso risultato vincente: si tratta di uno scenario di combinazione — per un formato 6 su 49, C(49,6) = 13.983.816 insiemi di numeri possibili.
Che cosa significa «con ripetizione» in una formula di permutazione o combinazione?
Significa che un elemento può essere selezionato più di una volta all'interno dello stesso risultato. Le permutazioni con ripetizione consentita usano n^r (ciascuna delle r posizioni dispone in modo indipendente di tutte le n scelte), mentre le combinazioni con ripetizione consentita usano (n + r − 1)! / [r!(n − 1)!]. Senza ripetizione, ogni elemento può essere usato al massimo una volta, che è ciò che presuppongono le formule standard nPr e nCr.
Fonti
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.