Permutazioni con ripetizione

Le permutazioni con ripetizione rispondono a una semplice domanda di conteggio: se Lei dispone di n simboli distinti e forma sequenze ordinate di lunghezza r in cui lo stesso simbolo può comparire più di una volta, quante sequenze esistono? La regola del prodotto moltiplica n scelte in ciascuna delle r posizioni, così il totale è esattamente n elevato alla potenza r. Quella formula compare negli spazi delle password, nei codici PIN, nelle colorazioni di stringhe a lunghezza fissa, nel campionamento con reinserimento e in innumerevoli problemi di matematica discreta in cui la risposta deve essere un intero esatto e non un'approssimazione in virgola mobile. Questa capacità accetta un intero positivo n (la dimensione dell'alphabet) e un intero non negativo r (la lunghezza della sequenza) e restituisce il conteggio esatto come stringa decimale calcolata con aritmetica BigInt, così valori ben oltre i limiti abituali degli interi sicuri restano corretti cifra per cifra. Gli input con n inferiore a uno o con r negativo vengono rifiutati con un chiaro errore di validazione invece di una risposta sbagliata silenziosa.

Come si definiscono le permutazioni con ripetizione

Una selezione ordinata di r posizioni da n simboli con ripetizione consentita è qualsiasi sequenza s1, s2, …, sr in cui ogni si appartiene a un insieme fisso di dimensione n. Poiché l'ordine conta e i simboli possono ripetersi, la prima posizione ha n opzioni, la seconda di nuovo n opzioni, e così per ogni posizione fino a r. Il principio fondamentale del conteggio moltiplica quelle scelte indipendenti in n × n × … × n, cioè n alla potenza r.

Quando r vale zero esiste esattamente una sequenza vuota, in accordo con la convenzione algebrica per cui ogni n positivo elevato alla potenza zero è uguale a uno. Ciò differisce dalle permutazioni senza ripetizione, che vietano il riuso e producono il fattoriale decrescente n × (n − 1) × … × (n − r + 1), e dalle combinazioni, che ignorano l'ordine.

Controlli classici da manuale includono due simboli di lunghezza tre che danno otto sequenze, cinque simboli di lunghezza due che danno venticinque, e dieci simboli di lunghezza zero che danno uno. Questa implementazione non usa mai potenze in virgola mobile, logaritmi approssimati o campionamento: calcola la potenza intera esatta con esponenziazione binaria BigInt affinché ogni cifra sia corretta. Il percorso è pienamente deterministico — senza semi casuali, senza orologi, senza rete e senza deriva di modello —, così lo stesso n e r producono sempre la stessa stringa.

Dove il conteggio n alla r compare nel lavoro reale

I team di sicurezza e di prodotto stimano gli spazi di password o PIN trattando ogni posizione di carattere come una scelta da un alphabet di dimensione n per lunghezza r, che è esattamente il conteggio delle permutazioni con ripetizione n alla r; gli interi esatti aiutano a confrontare la forza degli schemi senza approssimazioni logaritmiche.

Le gare di programmazione e i corsi di matematica discreta chiedono di continuo il numero di parole di lunghezza r su un alphabet di n lettere, le colorazioni di r perline con n colori quando l'ordine conta e i colori possono ripetersi, o le funzioni da un insieme di dimensione r in un insieme di dimensione n — tutte uguali a n elevato a r.

Le pipeline di dati e campionamento che modellano estrazioni ordinate con reinserimento necessitano dello stesso prodotto nel dimensionare spazi campionari o validare assetti Monte Carlo contro un totale analitico. Docenti e preparazione ai colloqui mostrano spesso una breve tabella di piccoli valori di n e r; calcolare il conteggio in una sola chiamata mantiene le demo interattive allineate a manuali e chiavi di risposta.

Se in seguito le servono permutazioni senza ripetizione, combinazioni con o senza ripetizione, o l'elenco delle tuple reali anziché il conteggio, le tratti come intenti di ricerca separati invece di sovraccaricare questa pagina.