Permutações com Repetição: Contagens com Elementos Indistinguíveis

Quando a ordem importa, mas alguns elementos são indistinguíveis

Em muitas contagens, queremos formar sequências (ou “palavras”) usando todos os elementos disponíveis, então a ordem importa. O detalhe que muda tudo é quando existem elementos repetidos e indistinguíveis (por exemplo, duas letras A idênticas). Se tratarmos essas cópias como se fossem diferentes, contamos arranjos “a mais” (supercontagem). A correção padrão é dividir por fatoriais associados às repetições.

Ideia central: por que aparece a divisão por fatoriais

Imagine um multiconjunto com n elementos no total, onde há n1 cópias de um tipo, n2 cópias de outro tipo, ..., nk cópias do k-ésimo tipo, com n1 + n2 + ... + nk = n. Se você rotular temporariamente as cópias repetidas (por exemplo, A1, A2, A3), então existem n! permutações desses n itens rotulados.

Mas, ao “desrotular” (tornar as cópias indistinguíveis), várias permutações rotuladas viram a mesma palavra final. Em particular:

• As n1 cópias do tipo 1 podem ser trocadas entre si de n1! maneiras sem mudar a palavra.
• As n2 cópias do tipo 2 podem ser trocadas de n2! maneiras sem mudar a palavra.
• ...
• As nk cópias do tipo k podem ser trocadas de nk! maneiras sem mudar a palavra.

Logo, cada palavra distinta foi contada n1! n2! ... nk! vezes dentro das n! permutações rotuladas. Portanto, o número de permutações distintas (com repetição) é:

n! / (n1! n2! ... nk!)

Continue em nosso aplicativo e ...

• Ouça o áudio com a tela desligada
• Ganhe Certificado após a conclusão
• + de 5000 cursos para você explorar!

ou continue lendo abaixo...

Baixar o aplicativo

Como identificar indistinguibilidade no enunciado

• Elementos idênticos: letras repetidas (A, A), bolas idênticas, fichas iguais, resultados iguais.
• O que importa é a sequência final: se trocar duas cópias iguais não muda o resultado observado, então elas são indistinguíveis.
• Reescrita útil: em vez de “permute objetos”, pense em “escolha posições para cada tipo”.

Reescrevendo em termos de posições (método das posições)

Uma forma prática de evitar a supercontagem é escolher diretamente as posições de cada tipo na sequência.

Passo a passo (posições)

• Passo 1: conte o total de posições: n.
• Passo 2: escolha as posições do primeiro tipo (por exemplo, as letras A): C(n, n1).
• Passo 3: das posições restantes, escolha as do segundo tipo: C(n - n1, n2).
• Continue até alocar todos os tipos.

O produto fica:

C(n, n1) * C(n - n1, n2) * ... * C(n - n1 - ... - n(k-1), nk)

Esse produto simplifica exatamente para n! / (n1! n2! ... nk!).

Exemplo 1 (anagrama com repetição): “BANANA”

A palavra BANANA tem 6 letras, com repetições: A aparece 3 vezes, N aparece 2 vezes, B aparece 1 vez. Então:

n = 6, nA = 3, nN = 2, nB = 1

Número de anagramas distintos:

6! / (3! 2! 1!) = 720 / (6 * 2) = 60

Pelo método das posições:

• Escolha as 3 posições dos A: C(6,3)=20
• Das 3 restantes, escolha 2 posições dos N: C(3,2)=3
• Sobra 1 posição para B: C(1,1)=1

Total: 20 * 3 * 1 = 60.

Reescrevendo em termos de blocos (quando há restrições de adjacência)

Em problemas com “juntos que devem ficar juntos” ou “não podem ficar juntos”, é comum agrupar elementos em blocos e depois permutar blocos e itens internos. Com repetição, o cuidado é o mesmo: blocos ou itens iguais podem gerar supercontagem.

Passo a passo (blocos)

• Passo 1: identifique o que deve ser tratado como uma unidade (bloco).
• Passo 2: conte quantas unidades totais serão permutadas.
• Passo 3: aplique permutação com repetição se houver unidades indistinguíveis.
• Passo 4: multiplique pelas permutações internas dos blocos (se fizer sentido e se houver distinção interna).

Exemplo 2 (bloco): anagramas de “ARARA” com as duas letras R juntas

“ARARA” tem 5 letras: A aparece 3 vezes, R aparece 2 vezes. Queremos contar anagramas em que os dois R ficam adjacentes.

Trate “RR” como um bloco. Então temos as unidades: [RR], A, A, A. São 4 unidades no total, com repetição de A (3 iguais).

Número de arranjos:

4! / 3! = 4

Listando mentalmente as posições do bloco entre os A’s: RRAAA, ARRAA, AARRA, AAARR. Não há permutação interna do bloco (RR é idêntico).

Distribuição de objetos idênticos em uma sequência (contagem de sequências com símbolos repetidos)

Um caso muito comum em probabilidade é contar sequências de comprimento n com quantidades fixas de símbolos. Isso é exatamente permutação com repetição: você está contando quantas sequências diferentes existem com aquelas frequências.

Exemplo 3: sequências binárias com número fixo de 1s

Quantas sequências de 10 posições têm exatamente 4 uns (1) e 6 zeros (0)?

Os 1s são indistinguíveis entre si, e os 0s também. Logo:

10! / (4! 6!) = C(10,4) = 210

Interpretação por posições: basta escolher quais 4 posições serão 1; o resto vira 0 automaticamente.

Exemplo 4: sequência com três tipos de objetos idênticos

Uma linha de 8 posições deve ser preenchida com 3 bolas vermelhas idênticas (V), 3 azuis idênticas (A) e 2 verdes idênticas (G). Quantas sequências distintas?

8! / (3! 3! 2!) = 40320 / (6 * 6 * 2) = 560

Probabilidade envolvendo rearranjos com repetições

Em problemas de probabilidade, um modelo frequente é: “escolha uma permutação aleatória das letras disponíveis, considerando como resultados possíveis apenas as palavras distintas”. Nesse caso, se todas as palavras distintas são igualmente prováveis, a probabilidade de obter uma palavra específica é:

1 / (n! / (n1! n2! ... nk!))

Exemplo 5: probabilidade de formar uma palavra específica ao permutar letras repetidas

Com as letras de “BANANA”, há 60 anagramas distintos. Se você embaralha as letras e considera que cada anagrama distinto é um resultado possível equiprovável, então a probabilidade de obter exatamente “BANANA” é:

1/60

Outra forma de ver: como existem 60 resultados distintos possíveis e apenas 1 é o desejado, a chance é 1/60.

Exemplo 6: probabilidade de a palavra começar com uma letra específica

Com as letras de “BANANA”, qual a probabilidade de um anagrama distinto começar com B?

Total de anagramas: 60.

Para começar com B, fixe B na primeira posição e permute o restante: sobram 5 letras com A(3) e N(2). Número de anagramas com B no início:

5! / (3! 2!) = 10

Probabilidade:

10/60 = 1/6

Checklist rápido: quando usar permutação com repetição

• Você usa todos os elementos (tamanho fixo igual ao total disponível).
• A ordem na sequência final importa.
• Existem repetições indistinguíveis (trocar cópias iguais não muda o resultado).
• Você consegue descrever o resultado final apenas pelas frequências de cada tipo e pelas posições ocupadas.

Validação da fórmula com casos extremos (sanity check)

Uma boa prática é testar a expressão n! / (n1! n2! ... nk!) em limites onde a resposta é óbvia.

Caso extremo 1: todas as letras iguais

Exemplo: “AAAAA”. Aqui n=5 e há apenas um tipo com n1=5.

5! / 5! = 1

Faz sentido: só existe uma “palavra” possível, porque qualquer rearranjo é igual.

Caso extremo 2: todas as letras distintas

Exemplo: 5 letras todas diferentes. Então n=5 e cada repetição é 1: n1=n2=n3=n4=n5=1.

5! / (1! 1! 1! 1! 1!) = 5!

Faz sentido: recuperamos a contagem padrão de permutações quando não há indistinguibilidade.

Caso extremo 3: apenas uma repetição pequena

Exemplo: 4 letras com duas iguais (A, A, B, C). Aqui n=4, repetições: 2,1,1.

4! / 2! = 12

Interpretação: se você tratasse as duas letras A como diferentes (A1 e A2), teria 4!=24 arranjos, mas cada palavra final aparece duas vezes (troca A1↔A2), então divide por 2 e obtém 12.

Erros comuns e como evitar

• Dividir pelo fatorial errado: divida por ni! para cada grupo de itens indistinguíveis (cada letra repetida, cada cor idêntica etc.).
• Confundir “repetição” com “pode repetir”: aqui a repetição é “já existem cópias iguais no conjunto”. Não é o caso de escolher com reposição; é rearranjar um multiconjunto fixo.
• Esquecer que restrições mudam o modelo: se houver “juntos”, “separados”, “começa com”, “termina com”, use posições fixas e/ou blocos antes de aplicar a fórmula.