Permutação com repetição
Todos os n elementos são usados, mas elementos do mesmo tipo são indistinguíveis. Trocar dois símbolos iguais não cria uma nova ordenação; trocar símbolos de tipos diferentes pode criar.
n₁+n₂+···+nᵣ=n
As multiplicidades n₁,…,nᵣ são inteiros não negativos e descrevem todas as categorias presentes.
Por que dividimos pelos fatoriais?
Se os n objetos fossem distintos, haveria n! ordens. Porém, permutar entre si os n₁ objetos iguais reproduz cada sequência n₁! vezes. O mesmo ocorre com cada tipo. Dividir por n₁!n₂!···nᵣ! remove exatamente essas contagens repetidas.
Relação com combinações
Com apenas dois tipos, de multiplicidades k e n−k:
Escolher as k posições do primeiro tipo determina automaticamente as posições do segundo. Essa equivalência também explica caminhos mínimos com passos horizontais e verticais.
Não confunda os métodos
| Situação | Método |
|---|---|
| Usar todos, todos distintos | Permutação simples |
| Usar todos, alguns indistinguíveis | Permutação com repetição |
| Escolher parte e ordenar | Arranjo |
| Escolher parte sem ordenar | Combinação |
| Preencher posições reutilizando símbolos | Princípio Fundamental da Contagem |
| Disposição circular com rotações equivalentes | Permutação circular |
Uma senha com reutilização livre não possui multiplicidades previamente fixadas e, em geral, não é uma permutação com repetição.
Roteiro de resolução
- Conte o total de posições.
- Liste cada tipo de símbolo.
- Conte suas multiplicidades.
- Confirme que a soma das multiplicidades é n.
- Aplique a fórmula sem restrições.
- Atualize multiplicidades quando uma posição for fixada.
- Separe casos incompatíveis.
- Use o complementar quando o conjunto proibido for mais simples.
- Não reconte ordens que diferem apenas pela troca de iguais.
Aplicações
- Anagramas: qualquer reorganização das letras, ainda que não forme palavra do dicionário.
- Sequências: símbolos repetidos com quantidades fixadas.
- Objetos iguais: distribuições lineares por tipos.
- Malhas: um caminho mínimo com d passos à direita e c para cima possui (d+c)!/(d!c!) caminhos.
- Posições: escolha as posições de um tipo e complete com os demais.
Restrições em anagramas
Começo ou fim fixo: retire uma ocorrência da letra fixada e atualize sua multiplicidade. Letras juntas: trate-as como bloco e conte também as ordens internas distintas. Para “começar com vogal”, separe uma vez cada vogal diferente possível.
Consoantes juntas seguem o mesmo princípio de bloco. Duas letras específicas distintas juntas formam um bloco com duas ordens internas possíveis. Para impedir símbolos iguais consecutivos, use complemento quando houver apenas um par ou organize primeiro os outros símbolos e distribua os repetidos nos espaços disponíveis. “Não começar com L” é total menos sequências começadas por L.
Números, senhas e último algarismo
- Zero não pode iniciar um número, mas pode iniciar uma senha.
- Ao fixar zero, uma letra ou um algarismo, retire essa ocorrência das multiplicidades.
- Número par: último algarismo deve ser par.
- Divisibilidade por 5: último algarismo deve ser 0 ou 5.
- Casos de finais diferentes são incompatíveis e devem ser somados.
Correção de 11220: há um único zero. O total é 5!/(2!·2!)=30. Fixando esse zero na primeira posição, restam 1,1,2,2, em 4!/(2!·2!)=6 ordens. Portanto, 30−6=24 números válidos.
Pegadinhas
- Tratar iguais como distintos ou usar n! diretamente.
- Dividir por fatoriais que não correspondem a multiplicidades.
- Esquecer um tipo ou aceitar multiplicidades cuja soma não é n.
- Proibir zero no começo de senha ou permiti-lo no começo de número.
- Manter no denominador uma ocorrência que já foi fixada.
- Multiplicar casos incompatíveis ou contar o mesmo caso duas vezes.
- Confundir quantidades fixadas com reutilização livre de símbolos.
- Confundir permutação com repetição com combinação.
Questões resolvidas
1. Anagrama direto
Quantos anagramas tem BANANA?
São 6 letras: A três vezes, N duas e B uma.
Resposta: 6!/(3!·2!)=60.
2. Várias repetições
Quantos anagramas tem MATEMATICA?
Há 10 letras, com A³, M² e T².
Resposta: 10!/(3!·2!·2!)=151 200.
3. Começo fixo
Quantos anagramas de ARARA começam com A?
Fixe um A; restam A,A,R,R.
Resposta: 4!/(2!·2!)=6.
4. Vogais juntas
Em BANANA, quantos anagramas mantêm as três vogais juntas?
O bloco AAA e B,N,N formam quatro objetos, com N repetido.
Resposta: 4!/2!=12.
5. Zero inicial
Quantos números usam todos os algarismos de 11220 sem começar por zero?
Total: 5!/(2!·2!)=30. Começando pelo único zero: 4!/(2!·2!)=6.
Resposta: 30−6=24.
6. Número par
Quantos números pares usam todos os algarismos de 11220 sem zero inicial?
Final 0: 4!/(2!·2!)=6. Final 2: 4!/2!=12, menos 3!/2!=3 com zero inicial; restam 9.
Resposta: 6+9=15.
7. Complementar
Quantos anagramas de AABC não têm os dois A juntos?
Total 4!/2!=12. Com bloco AA: 3!=6.
Resposta: 12−6=6.
Exercícios
1. Quantos anagramas distintos tem OVO?
2. Sequências formadas por exatamente três A e dois B:
3. Quantos anagramas de CASA começam com C?
4. Quantos anagramas de BANANA têm todas as vogais juntas?
5. Quantos números usam todos os algarismos de 11220 sem começar por zero?
6. Caminhos mínimos com quatro passos à direita e três para cima:
7. Números divisíveis por 5 usando todos os algarismos de 11225:
8. Números pares usando todos os algarismos de 11220, sem zero inicial:
9. Anagramas de MATEMATICA que começam com M e mantêm todas as vogais juntas:
10. Sequências com A,A,A,B,B,C,C em que não há dois A consecutivos:
Gabarito comentado:
1-D: 3!/2!=3.
2-C: 5!/(3!·2!)=10=C₅,₃.
3-B: fixado C, restam A,A,S: 3!/2!=3.
4-A: bloco AAA mais B,N,N: 4!/2!=12.
5-B: 30 totais menos 6 iniciados pelo único zero: 24.
6-C: 7!/(4!·3!)=35.
7-D: o último algarismo deve ser 5; restam 1,1,2,2: 4!/(2!·2!)=6.
8-A: final 0 produz 6; final 2 produz 9 sem zero inicial; total 15.
9-C: fixe M; o bloco A,A,A,E,I tem 5!/3!=20 ordens. Externamente, bloco, M, T,T,C dão 5!/2!=60: 20·60=1 200.
10-B: ordene B,B,C,C em 4!/(2!·2!)=6 maneiras e escolha 3 dos 5 espaços para os A: 6·C₅,₃=60.
Resumo final
- Todos os elementos são usados; iguais são indistinguíveis.
- Divida n! pelos fatoriais das multiplicidades, cuja soma deve ser n.
- Posição fixa altera a multiplicidade restante.
- Em números, trate zero inicial e último algarismo antes da contagem.