Permutações com repetição

As permutações com repetição respondem a uma pergunta simples de contagem: se você tem n símbolos distintos e forma sequências ordenadas de comprimento r em que o mesmo símbolo pode aparecer mais de uma vez, quantas sequências existem? A regra do produto multiplica n escolhas em cada uma das r posições, de modo que o total é exatamente n elevado à potência r. Essa fórmula aparece em espaços de senhas, códigos PIN, colorações de cadeias de comprimento fixo, amostragem com reposição e inúmeros problemas de matemática discreta em que a resposta deve ser um inteiro exato e não uma aproximação de ponto flutuante. Esta capacidade aceita um inteiro positivo n (o tamanho do alphabet) e um inteiro não negativo r (o comprimento da sequência) e devolve a contagem exata como string decimal calculada com aritmética BigInt, de forma que valores muito além dos limites habituais de inteiros seguros permanecem corretos dígito a dígito. Entradas com n abaixo de um ou com r negativo são rejeitadas com um erro de validação claro em vez de uma resposta errada silenciosa.

Como as permutações com repetição são definidas

Uma seleção ordenada de r posições a partir de n símbolos com repetição permitida é qualquer sequência s1, s2, …, sr em que cada si pertence a um conjunto fixo de tamanho n. Como a ordem importa e os símbolos podem se repetir, a primeira posição tem n opções, a segunda novamente tem n opções, e assim por diante em cada posição até r. O princípio fundamental da contagem multiplica essas escolhas independentes em n × n × … × n, que é n elevado à potência r.

Quando r é igual a zero existe exatamente uma sequência vazia, em conformidade com a convenção algébrica de que qualquer n positivo elevado à potência zero é igual a um. Isso difere das permutações sem repetição, que proíbem o reuso e produzem o fatorial decrescente n × (n − 1) × … × (n − r + 1), e das combinações, que ignoram a ordem.

Verificações clássicas de livro incluem dois símbolos de comprimento três gerando oito sequências, cinco símbolos de comprimento dois gerando vinte e cinco, e dez símbolos de comprimento zero gerando um. Esta implementação nunca usa potência de ponto flutuante, logaritmos aproximados nem amostragem: calcula a potência inteira exata com exponenciação binária BigInt para que cada dígito fique correto. O caminho é plenamente determinístico — sem sementes aleatórias, sem relógios, sem rede e sem deriva de modelo —, de modo que o mesmo n e r sempre produzem a mesma string.

Onde a contagem n elevado a r aparece no trabalho real

Equipes de segurança e de produto estimam espaços de senha ou PIN tratando cada posição de caractere como uma escolha em um alphabet de tamanho n e comprimento r, que é exatamente a contagem de permutações com repetição n elevado a r; inteiros exatos ajudam a comparar a força dos esquemas sem aproximações logarítmicas.

Competições de programação e cursos de matemática discreta pedem com frequência o número de palavras de comprimento r sobre um alphabet de n letras, colorações de r contas com n cores quando a ordem importa e as cores podem se repetir, ou funções de um conjunto de tamanho r em um conjunto de tamanho n — todas iguais a n elevado a r.

Pipelines de dados e amostragem que modelam sorteios ordenados com reposição precisam do mesmo produto ao dimensionar espaços amostrais ou validar montagens de Monte Carlo contra um total analítico. Educadores e preparação para entrevistas costumam mostrar uma tabela curta de valores pequenos de n e r; calcular a contagem em uma única chamada mantém demos interativas alinhadas a livros-texto e gabaritos.

Se mais adiante você precisar de permutações sem repetição, combinações com ou sem repetição, ou a listagem das tuplas reais em vez da contagem, trate-as como intenções de busca separadas em vez de sobrecarregar esta página.