Permutação com elementos repetidos

A permutação com repetição, quando se parte de um total e das frequências de itens idênticos, conta quantos arranjos ordenados distintos uma coleção mista admite. Se você tem n objetos e alguns são cópias indistinguíveis, o número de sequências diferentes é o fatorial de n dividido pelo produto do fatorial de cada frequência listada. Esta calculadora aceita esse par — o total n e a lista de frequências —, avalia a identidade com aritmética BigInt exata e devolve a contagem de permutações como uma cadeia decimal. Não há amostragem, nem chamada de rede, nem arredondamento dependente do relógio: cada par válido produz o mesmo inteiro todas as vezes.

O que uma permutação com itens idênticos repetidos conta

Uma permutação com repetição de itens idênticos é o número de arranjos ordenados distintos de uma coleção finita em que alguns membros não podem ser distinguidos. Escreva n para o número total de posições (ou objetos) e n1, n2, até nk para quantas vezes cada tipo indistinguível aparece. Como trocar duas cópias do mesmo tipo não cria um arranjo novo, as n fatorial ordenações de uma coleção totalmente rotulada supercontam em n1 fatorial para o primeiro tipo, n2 fatorial para o segundo, e assim por diante.

A identidade exata é, portanto, o fatorial de n dividido pelo produto desses fatoriais. As verificações clássicas de sala incluem as letras de BANANA: seis letras, três A, dois N e um B, o que dá o fatorial de seis sobre o fatorial de três vezes o fatorial de dois vezes o fatorial de um, igual a sessenta palavras distintas, e MISSISSIPPI: onze letras com frequências um, quatro, quatro e dois, que dá o fatorial de onze sobre esses fatoriais, igual a trinta e quatro mil seiscentos e cinquenta.

Isto não é o produto n elevado a r que alguns manuais também chamam de permutações com repetição: aquela outra contagem preenche r casas independentes a partir de um alfabeto de n símbolos e vale n elevado a r. Aqui o comprimento já é n, e a entrada é a frequência de cada grupo idêntico. Se uma frequência listada for maior que n, a coleção é impossível e esta calculadora rejeita o pedido em vez de devolver zero ou uma extensão com sinal.

Frequências que somam menos que n deixam itens únicos restantes; cada restante contribui com um fatorial de um no denominador e não altera o inteiro, de modo que a mesma fórmula continua a valer. A implementação nunca amostra, nunca depende do relógio e nunca arredonda: avalia o fatorial de n sobre o produto dos fatoriais listados com aritmética BigInt exata para que contagens grandes permaneçam inteiros precisos em vez de transbordar a mantissa de um número em ponto flutuante.

Anagramas, assentos e oráculos de competição

Professores de língua e autores de quebra-cabeças usam esta contagem quando perguntam quantas palavras distintas podem ser formadas reordenando uma cadeia dada: as letras são os itens, o histograma de cada letra é a lista de contagens de repetição, e a resposta é exatamente o fatorial de n sobre o produto desses fatoriais. Problemas de química e genética que arranjam contas, bases ou assentos coloridos com cópias indistinguíveis seguem o mesmo inteiro.

Instrutores de estatística o apresentam ao contrastar amostragem com resultados idênticos frente ao produto n elevado a r que preenche casas independentes, e programadores de competição precisam de um oráculo exato para não reimplementar a divisão fatorial de multiprecisão em cada harness de linguagem. Geradores de prova podem fixar o caminho de sucesso com n igual a seis e repeats iguais a três, dois e um, que produz sessenta, e o caminho de rejeição com qualquer frequência maior que n, que deve falhar em vez de devolver zero.

Páginas irmãs podem tratar o produto n elevado a r de seleções ordenadas com reposição, o coeficiente multinomial genérico ou permutações sem repetição; este destino é especificamente o enunciado permutação com repetição quando as entradas são um total e as contagens de repetição de itens idênticos. Combine a contagem com seu próprio código de listagem se precisar das cadeias distintas concretas; esta capacidade devolve apenas o inteiro.