Calcolatrice di Permutazioni e Combinazioni

Usa le permutazioni quando l'ordine o la disposizione degli elementi selezionati è importante:

• assegnazione di posizioni in classifica (1°, 2°, 3° posto)
• disposizione di libri su uno scaffale
• creazione di password o codici PIN
• disposizione dei posti a sedere
• numeri di telefono

Usa le combinazioni quando stai semplicemente scegliendo un sottoinsieme e l'ordine è irrilevante:

• selezione dei membri della squadra
• scelta dei numeri della lotteria
• scelta di elementi del menu
• formazione di comitati

Un test utile: se scambiando due elementi selezionati si ottiene un risultato diverso, usa le permutazioni; se lo scambio non cambia nulla, usa le combinazioni.

I numeri della lotteria lo illustrano perfettamente: l'estrazione del Mega Millions seleziona 5 numeri su 70 più 1 su 25: C(70,5) × 25 = 302.575.350 biglietti possibili. Se l'ordine contasse, ci sarebbero P(70,5) × 25 = 36.309.042.000 possibilità, ovvero 120 volte in più.

Permutazioni di base: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Combinazioni di base: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

Con ripetizione consentita: permutazioni = n^r (ad esempio, un PIN a 4 cifre con cifre da 0 a 9 ha 10⁴ = 10.000 possibilità).

Combinazioni con ripetizione: C(n+r-1, r) — la scelta di 3 gusti da 5 gusti di gelato con ripetizioni consentite dà C(7,3) = 35.

Per valori grandi, usa la formula moltiplicativa per evitare di calcolare fattoriali enormi: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2.598.960 — il numero di mani di poker a 5 carte possibili.

Sicurezza delle password: una password di 8 caratteri che utilizza maiuscole, minuscole, cifre e 10 simboli (72 caratteri) ha 72⁸ = 722 mila miliardi di permutazioni con ripetizione, il che richiede un attacco a forza bruta di circa 22.800 anni a 1 miliardo di tentativi al secondo. Aggiungendo solo altri 2 caratteri (password di 10 caratteri) si arriva a 3,7 quadrilioni, 5.140 volte più difficile da violare.

• In genetica, il numero di modi per scegliere 23 coppie di cromosomi dai 46 cromosomi di un genitore è C(46,23) ≈ 8,2 miliardi, spiegando la diversità genetica.
• Nel controllo qualità, la selezione di 5 articoli da un lotto di 100 per i test comporta C(100,5) = 75.287.520 campioni possibili.
• Nelle fasi dei tornei, il numero di tabelloni possibili per il torneo NCAA March Madness è 2⁶³ ≈ 9,2 quintilioni, motivo per cui nessuno ha mai previsto correttamente un tabellone perfetto.

Una permutazione è una disposizione ordinata di elementi, mentre una combinazione è una selezione non ordinata; quell'unica distinzione, l'ordine, è tutto qui.

Se scegli le lettere A, B e C, le disposizioni ABC e CAB sono due permutazioni diverse ma la stessa combinazione, perché una combinazione si preoccupa solo di quali elementi sono stati scelti, non della loro sequenza. Come spiega l'Encyclopaedia Britannica, la combinatoria è il ramo della matematica dedicato al conteggio di tali disposizioni e selezioni.

Un test rapido: chiediti se lo scambio di due elementi scelti cambia il risultato. La classificazione dei medagliati d'oro, d'argento e di bronzo cambia se scambi due corridori, quindi l'ordine conta e usi le permutazioni. La scelta di tre ingredienti per la pizza non cambia se li scambi, quindi usi le combinazioni.

La formula delle permutazioni è nPr = n! / (n − r)! e la formula delle combinazioni è nCr = n! / [r! × (n − r)!], dove n! (n fattoriale) è il prodotto di ogni intero da 1 fino a n.

Per trovare P(10,3), calcola 10! / 7!, che si semplifica in 10 × 9 × 8 = 720. Per trovare C(10,3), dividi tale risultato per 3! = 6, ottenendo 120. Il fattoriale stesso cresce rapidamente: 5! = 120 e 10! = 3.628.800.

Wolfram MathWorld definisce il coefficiente binomiale C(n,r) esattamente in questo modo. Poiché nCr divide le r! ordinazioni che le permutazioni contano separatamente, nCr è sempre minore o uguale a nPr per gli stessi n e r.

Per calcolare C(52,5) — il numero di mani di poker a cinque carte — inizia con la forma moltiplicativa anziché con i fattoriali completi per mantenere i numeri gestibili. Scrivi il numeratore come i primi cinque fattori discendenti, 52 × 51 × 50 × 49 × 48, e il denominatore come 5! = 120. Il numeratore è uguale a 311.875.200; dividendo per 120 si ottengono esattamente 2.598.960 mani possibili.

Per una verifica più piccola, C(5,2) = (5 × 4) / (2 × 1) = 10, e C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Khan Academy insegna questa scorciatoia di cancellazione perché evita di calcolare direttamente fattoriali enormi. La NIST Digital Library of Mathematical Functions (DLMF) fornisce la stessa definizione di coefficiente binomiale qui utilizzata.

Quando la ripetizione è consentita, le formule cambiano perché gli elementi possono essere riutilizzati.

• Per le permutazioni con ripetizione, il conteggio è semplicemente n^r: un PIN a 4 cifre estratto dalle cifre 0–9 ha 10^4 = 10.000 possibilità, poiché ciascuna delle quattro posizioni ha indipendentemente dieci scelte.
• Per le combinazioni con ripetizione, il conteggio è C(n + r − 1, r). La scelta di 3 palline da 5 gusti di gelato quando sono ammesse le ripetizioni dà C(5 + 3 − 1, 3) = C(7,3) = 35.

Contrasta questo con la selezione senza ripetizione, in cui ogni scelta riduce il pool di uno. La ripetizione aumenta notevolmente i totali, ed è per questo che la forza delle password e la sicurezza del PIN si basano su di essa: ogni carattere aggiunto moltiplica le possibilità.

Permutazioni e combinazioni compaiono ovunque si contino disposizioni o selezioni.

• Le lotterie usano le combinazioni: la scelta di 6 numeri su 49 dà C(49,6) = 13.983.816 biglietti possibili, che stabilisce le probabilità del jackpot.
• I giochi di carte si affidano ad essi: ci sono 2.598.960 mani di poker a cinque carte possibili da un mazzo di 52 carte.
• La cybersecurity utilizza le permutazioni con ripetizione per misurare quante password o chiavi sono possibili, guidando direttamente la resistenza alla forza bruta.
• La statistica e la probabilità usano il coefficiente binomiale C(n,r) all'interno della distribuzione binomiale e del triangolo di Pascal.
• La programmazione, la creazione di tabelloni per tornei, l'analisi di sequenze di DNA e il campionamento per il controllo qualità dipendono tutti da questi conteggi.

L'Encyclopaedia Britannica osserva che il conteggio combinatorio è alla base della teoria della probabilità, motivo per cui questa calcolatrice si abbina naturalmente agli strumenti di probabilità e statistica.

Ogni voce nel triangolo di Pascal è un coefficiente binomiale nCr, quindi l'output di combinazione della calcolatrice sta letteralmente leggendo un valore da quel triangolo. La riga 6 del triangolo di Pascal è 1, 6, 15, 20, 15, 6, 1, esattamente da C(6,0) a C(6,6).

Questi numeri sono i coefficienti nello sviluppo binomiale (a + b)^n, motivo per cui C(n,r) è chiamato coefficiente binomiale.

Due identità seguono direttamente:

• la regola di simmetria C(n,r) = C(n, n−r), quindi C(15,4) = C(15,11) = 1.365
• la regola della somma per cui tutti i coefficienti nella riga n si sommano a 2^n, poiché C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4) = 1+4+6+4+1 = 16 = 2^4

Wolfram MathWorld e l'OEIS catalogano il triangolo di Pascal come sequenza A007318.

• L'errore più frequente è scegliere lo strumento sbagliato: usare una permutazione quando l'ordine non conta gonfia la risposta di un fattore pari a r!, perché nPr conta ogni gruppo non ordinato r! volte separatamente. Ad esempio, trattare un comitato di 3 persone scelto tra 10 persone come ordinato dà P(10,3) = 720 anziché il corretto C(10,3) = 120.
• Un secondo errore è dimenticare se la ripetizione è consentita: un PIN riutilizza le cifre (n^r), ma una lotteria no.
• Un terzo è confondere n e r, poiché le formule non sono simmetriche rispetto a essi.
• Infine, evita di calcolare interamente fattoriali giganti per poi dividerli; usa il metodo di cancellazione in modo che i valori intermedi rimangano piccoli e tu possa evitare il trabocco (overflow) o gli errori di arrotondamento.

Per qualsiasi n e r fissati, le permutazioni eguagliano o superano sempre le combinazioni poiché nPr = nCr × r!, dove il fattore extra tiene conto di ogni ordinamento degli elementi scelti.

Quando r = 1 sono uguali, poiché un singolo elemento ha una sola disposizione: P(20,1) = C(20,1) = 20. Man mano che r cresce, il divario si amplia rapidamente. Con n = 10 e r = 3, P(10,3) = 720 ma C(10,3) = 120 — il conteggio delle permutazioni è esattamente 3! = 6 volte maggiore. Scegliendo tutti gli elementi, P(5,5) = 5! = 120 mentre C(5,5) = 1.

Ecco perché i risultati ordinati esplodono di numero più velocemente delle selezioni non ordinate, e perché le lotterie (combinazioni) hanno probabilità di vincita molto migliori rispetto al caso in cui contasse l'ordine di estrazione. Comprendere questo rapporto aiuta a verificare la correttezza di qualsiasi risultato restituito dalla calcolatrice online.