Contare senza elencare
La combinatoria risponde a « quanti? » quando elencare ogni disposizione sarebbe impossibile. Tre domande classiche dominano il conteggio introduttivo: permutazioni (l’ordine conta), combinazioni (l’ordine non conta) e disposizioni / permutazioni parziali (l’ordine conta ma si riempiono solo k posti su n). Ogni domanda ha una variante con ripetizione e una senza ripetizione.
Un punto di partenza concreto è combinazioni senza ripetizioni—il coefficiente binomiale « n su k »—poi diramarsi verso le varianti ordinate o con ripetizione in base al problema.
Guida decisionale
Chiedete in ordine:
- L’ordine conta? Se sì → permutazioni / disposizioni. Se no → combinazioni.
- Lo stesso elemento può comparire più volte? Se sì → formule « con ripetizioni ». Se no → « senza ripetizioni ».
- State disporre tutti gli n elementi o solo k di essi? Le permutazioni complete usano n!; le selezioni parziali usano fattoriali decrescenti o n^k.
Interpretare male uno di questi tre assi è la fonte usuale di errori per un fattore nei compiti e nelle interviste.
Famiglia di calcolatori
- Permutazioni senza ripetizioni — n! disposizioni ordinate di n elementi distinti.
- Permutazioni con ripetizioni — permutazioni di multiset n! / (r₁! r₂! …) quando esistono copie identiche.
- Combinazioni senza ripetizioni — C(n, k) = n! / (k! (n − k)!) sottoinsiemi k non ordinati.
- Combinazioni con ripetizioni — C(n + k − 1, k) multiset di dimensione k da n tipi.
- Disposizioni senza ripetizioni — P(n, k) = n! / (n − k)! k-uple ordinate senza riutilizzo.
- Disposizioni con ripetizioni — n^k k-uple ordinate con riutilizzo consentito.
Gli input sono interi non negativi con i consueti vincoli di dominio (k ≤ n quando la ripetizione è vietata, ecc.). I fattoriali che traboccano compaiono come errori di calcolo, non come infinito silenzioso.
Fattoriali come motore comune
Le formule senza ripetizione si appoggiano a n!—il prodotto 1 × 2 × … × n, con 0! = 1 per convenzione. Le combinazioni eliminano gli ordini interni di ogni sottoinsieme (k!) e talvolta la coda inutilizzata ((n − k)!). Le permutazioni parziali mantengono l’ordine, quindi dividono solo per (n − k)!.
Le combinazioni con ripetizione usano l’identità « stars and bars » C(n + k − 1, k). Le disposizioni con ripetizione sono ancora più semplici: ciascuna delle k posizioni sceglie indipendentemente uno dei n simboli → n^k.
Micro-esempi svolti
Mazzo da 52, mano da 5 (ordine irrilevante, senza riutilizzo): C(52, 5).
Gara con 8 corridori distinti, oro/argento/bronzo: P(8, 3) = 8 × 7 × 6.
PIN a 4 cifre, cifre ripetibili: 10^4 = 10000.
Disposizioni delle lettere di « BOOK »: 4! / 2! per le due O—permutazione di multiset.
Comprare 3 palline da 5 gusti, ripetizioni consentite, ordine ignorato: C(5 + 3 − 1, 3).
Associare un problema verbale al calcolatore corretto è l’abilità; l’aritmetica è secondaria.
Relazioni che prevengono errori
- P(n, k) = C(n, k) × k! — scegliere l’insieme, poi ordinarlo.
- n! = P(n, n) — le permutazioni complete sono permutazioni parziali con k = n.
- C(n, k) = C(n, n − k) — simmetria dei coefficienti binomiali.
- Vietare la ripetizione quando il testo la consente sottostima; consentirla quando la vieta sovrastima.
Dove compaiono questi conteggi
- Denominatori di probabilità (giochi equi, campionamento)
- Schizzi sulla robustezza di password e identificatori (con chiare avvertenze sul modello di minaccia)
- Analisi degli algoritmi (spazi di ricerca, enumerazione degli stati)
- Progettazione sperimentale (combinazioni di trattamenti)
- « Modi di arrivare » nello sport e enigmi di classifica simili—come matematica, non consigli sulle scommesse
Un n grande cresce più velocemente dell’intuizione. C(60, 6) è già nell’ordine dei milioni; i fattoriali oltre un n modesto traboccano i float a precisione fissa—da qui helper dedicati e librerie per interi grandi nei sistemi di produzione.
Sequenza didattica
- Contare permutazioni di n piccolo elencando, poi introdurre n!.
- Introdurre P(n, k) con esempi da podio.
- Mostrare C(n, k) dividendo l’ordine.
- Aggiungere la ripetizione: prima n^k (posizioni indipendenti), poi stars and bars.
- Solo allora permutazioni di multiset con lettere ripetute.
Passare direttamente a sei formule simili senza la guida decisionale produce sostituzione meccanica senza comprensione.
Note implementative
Calcolare C(n, k) con tre fattoriali completi è semplice ma trabocca presto. Gli algoritmi moltiplicativi riducono la dimensione intermedia. Gli helper di questo hub usano divisione fattoriale con controlli di finitezza adatti all’educazione interattiva—non per n a scala crittografica. Rifiutare non interi e coppie (n, k) impossibili con motivi di errore stabili.
Errori comuni
- Trattare « comitato di 5 » come permutazione
- Usare n^k per estrazioni senza reinserimento quando l’ordine non conta
- Dimenticare di dividere per i fattoriali delle lettere identiche nei problemi di parole
- Confondere combinazioni con ripetizione e senza ripetizione acquistando « fino a k articoli »
Riepilogo
Questo hub riunisce sei strumenti elementari di conteggio: permutazioni complete e di multiset, combinazioni con e senza ripetizione, e disposizioni parziali con e senza ripetizione. Decidete se valgono ordine e riutilizzo, scegliete la formula corrispondente e verificate con un piccolo elenco. I calcolatori automatizzano l’aritmetica così potete concentrarvi sulla modellazione corretta del problema.