Quantos anagramas tem a palavra MAMBEMBE? Um simples \(8!\) superestima — trocar as duas letras B entre si produz o mesmo anagrama, não um novo. Quando há elementos repetidos, precisamos dividir para compensar.
No artigo sobre combinações simples, encerramos a tríade clássica dos agrupamentos com elementos distintos. Agora damos o passo seguinte: e quando os elementos se repetem?
Por que permutações com repetição? #
Contar ordenações com elementos repetidos aparece com frequência em computação e ciência de dados:
- Processamento de linguagem natural: a contagem de anagramas distintos de uma palavra com letras repetidas — como MISSISSIPPI — é o problema-tipo desta fórmula. A mesma lógica estima o número de sequências de tokens distintas geradas por modelos de linguagem com vocabulário restrito.
- Bioinformática: sequências de DNA são compostas por quatro bases (A, T, C, G) que se repetem. O número de sequências distintas de comprimento \(n\) com composição fixada é uma permutação com repetição — base de métricas de diversidade genômica.
- Caminhos em redes: o número de caminhos mínimos entre dois pontos de uma grade é uma permutação com repetição de movimentos horizontais e verticais — útil em roteamento de pacotes e planejamento de trajetórias em robótica.
- Análise combinatória de protocolos: em redes de comutação, sequências de operações com tipos repetidos (leitura, escrita, espera) são contadas com esta fórmula para estimar espaços de estado em verificação formal.
- Estatística: o coeficiente multinomial \(\dfrac{n!}{n_1!,n_2!,\cdots,n_r!}\) — que é exatamente esta fórmula — aparece na distribuição multinomial, que generaliza a distribuição binomial para mais de dois resultados possíveis.
Da combinação à permutação com repetição #
O diagrama abaixo expande a árvore de decisão do artigo anterior, acrescentando o ramo que cobre elementos repetidos:
flowchart TD
A["n elementos"] --> B{"Todos distintos?"}
B -->|"Sim"| C{"Usar todos?"}
C -->|"Sim"| D["Permutação Simples
P_n = n!"]
C -->|"Não — escolher r"| E{"Ordem importa?"}
E -->|"Sim"| F["Arranjo Simples
A(n,r) = n!/(n-r)!"]
E -->|"Não"| G["Combinação Simples
C(n,r) = n!/(r!(n-r)!)"]
B -->|"Não — há repetidos"| H["Permutação com Repetição
n! / (n₁! · n₂! · … · nᵣ!)"]
A Ideia Central: Remover a Supercontagem #
Imagine 5 lapiseiras: 2 brancas (B¹ e B²), 1 azul, 1 preta, 1 verde. Se tratarmos as duas brancas como distintas, obtemos \(5!\) distribuições. Mas B¹=branca e B²=branca são a mesma coisa para quem recebe — cada distribuição real foi contada \(2!\) vezes.
Número correto: \(\dfrac{5!}{2!} = 60\).
Permutação com Repetição #
Dado um conjunto de \(n\) elementos, dos quais \(n_1\) são iguais ao tipo 1, \(n_2\) ao tipo 2, …, \(n_r\) ao tipo \(r\), com \(n_1 + n_2 + \cdots + n_r = n\), o número de arranjos (permutações) distintos é:
$$P_n^{(n_1, n_2, \ldots, n_r)} = \frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}$$Intuição: começamos com \(n!\) ordenações de todos os elementos como se fossem distintos. Dividimos por \(n_i!\) para cada grupo de elementos iguais, que permutam entre si sem criar novidade.
Exemplos Resolvidos #
Números formados com 1,1,1,3,3,9 #
Enunciado: Quantos números de 6 algarismos distintos podem ser formados com os dígitos 1, 1, 1, 3, 3, 9?
Solução:
Via fórmula:
$$\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$$Via escolha de posições: escolher 3 posições (de 6) para os 1s: \(C(6,3) = 20\). Depois 2 posições (de 3 restantes) para os 3s: \(C(3,2) = 3\). O 9 ocupa o último: \(C(1,1) = 1\). Total: \(20 \times 3 \times 1 = 60\) ✓
Anagramas de MAMBEMBE #
Letras: M(3×), B(2×), E(2×), A(1×) — total 8 letras.
$$P_8^{(3,2,2,1)} = \frac{8!}{3!\,2!\,2!\,1!} = \frac{40{.}320}{24} = \mathbf{1{.}680}$$
Python: math.factorial e collections.Counter
math.factorial e collections.Counter
Python permite calcular a fórmula diretamente com math.factorial, ou usar
sympy.factorial para trabalhar simbolicamente. O padrão mais idiomático
combina collections.Counter para contar as frequências com math.prod para
calcular o denominador:
from math import factorial
from collections import Counter
from math import prod
def permutacoes_repeticao(palavra: str) -> int:
n = len(palavra)
frequencias = Counter(palavra).values()
return factorial(n) // prod(factorial(k) for k in frequencias)
print(permutacoes_repeticao("MAMBEMBE")) # 1680
print(permutacoes_repeticao("MISSISSIPPI")) # 34650Counter retorna um dicionário {letra: quantidade} — exatamente os \(n_i\)
da fórmula. prod(factorial(k) for k in ...) calcula o denominador sem
precisar nomear cada frequência individualmente.
Campeonato com 15 partidas: 7 vitórias, 5 derrotas, 3 empates #
Quantas sequências de resultados possíveis?
$$\frac{15!}{7!\,5!\,3!} = \mathbf{360{.}360}$$Sequências binárias com três 1s e cinco 0s #
Quantas sequências de 8 bits têm exatamente três 1s e cinco 0s?
$$P_8^{(3,5)} = \frac{8!}{3!\,5!} = \binom{8}{3} = \mathbf{56}$$Esse resultado revela uma equivalência importante:
Qualquer sequência com \(k\) símbolos de um tipo e \(m\) símbolos de outro tipo — independentemente de quais sejam esses símbolos — tem exatamente
$$P_{k+m}^{(k,\,m)} = \frac{(k+m)!}{k!\,m!} = \binom{k+m}{k}$$arranjos distintos. No exemplo acima, \(k = 3\) (uns) e \(m = 5\) (zeros), dando \(\binom{8}{3} = 56\). Essa fórmula reaparece sempre que um problema se reduz a alocar dois tipos de símbolos em sequência — como o método das estrelas e barras, que será visto no artigo sobre combinações com repetição.
Python: itertools.combinations para sequências binárias
itertools.combinations para sequências binárias
Gerar todas as sequências binárias de comprimento 8 com exatamente três 1s é
equivalente a escolher quais 3 posições (entre as 8) recebem o valor 1 — uma
combinação. itertools.combinations faz exatamente isso:
from itertools import combinations
from math import comb
n, k = 8, 3
# Conta diretamente pela equivalência com C(n, k)
print(comb(n, k)) # 56
# Gera todas as sequências: cada tupla indica as posições dos 1s
posicoes = list(combinations(range(n), k))
print(len(posicoes)) # 56
# Converte para strings binárias
def to_binaria(pos, n):
seq = ['0'] * n
for i in pos: seq[i] = '1'
return ''.join(seq)
sequencias = [to_binaria(p, n) for p in posicoes]
print(sequencias[:4]) # ['11100000', '11010000', '11001000', '11000100']Caminhos mínimos em malha: de (0,0) a (4,3) #
Mover-se apenas para cima (C) ou para a direita (D), em 7 passos (4D e 3C). A figura abaixo mostra dois dos 35 caminhos possíveis: o caminho azul sobe primeiro e depois vai à direita; o amarelo faz o inverso.
Anagramas de MAMBEMBE começando com vogal #
Enunciado: Quantos anagramas de MAMBEMBE têm uma vogal na primeira posição?
Solução: As vogais disponíveis são A, E, E. Os casos são disjuntos conforme a vogal inicial.
Caso 1 — começa com A: as restantes são M,M,M,B,B,E,E (7 letras):
$$N_1 = \frac{7!}{3!\,2!\,2!} = \mathbf{210}$$Caso 2 — começa com E: as restantes são M,M,M,A,B,B,E (7 letras):
$$N_2 = \frac{7!}{3!\,1!\,2!\,1!} = \mathbf{420}$$Total (Princípio Aditivo — casos disjuntos): \(210 + 420 = \mathbf{630}\)
Anagramas de MAMBEMBE com todos os M separados #
Enunciado: Quantos anagramas de MAMBEMBE têm os três M’s em posições não adjacentes entre si?
Solução:
Etapa 1: ordenar as 5 letras não-M: A, B, B, E, E.
$$\frac{5!}{2!\,2!\,1!} = 30 \text{ ordens}$$Etapa 2: em cada ordem surgem 6 lacunas (antes, entre e após as letras). Inserir 3 M’s em 3 lacunas distintas (para que não fiquem adjacentes):
$$C(6, 3) = 20$$Total: \(30 \times 20 = \mathbf{600}\)
Tabela-Resumo #
| Tipo | Elementos iguais? | Fórmula |
|---|---|---|
| Permutação simples | Não | \(P_n = n!\) |
| Permutação com repetição | Sim | \(\dfrac{n!}{n_1!, n_2!, \cdots, n_r!}\) |
| Caso especial: dois tipos | Sim (dois grupos) | \(\dfrac{n!}{k!,(n-k)!} = \dbinom{n}{k}\) |
Exercícios #
Os exercícios a seguir cobrem as principais técnicas do artigo: aplicação direta da fórmula, casos com restrição de posição e caminhos em grade. Estão ordenados do mais simples ao mais complexo.
Exercício 1 — Números com dígitos repetidos
Quantos números de 7 dígitos podem ser formados com \(1, 3, 6, 6, 6, 8, 8\)? (a) Sem restrições. (b) Maiores que 6.000.000.
(a) \(\dfrac{7!}{3!,2!,1!,1!} = \dfrac{5040}{12} = \mathbf{420}\)
(b) 1º dígito ∈ {6, 8}.
- Começa com 6: restam \(6,6,8,8,1,3\) → \(\dfrac{6!}{2!,2!,1!,1!} = 180\)
- Começa com 8: restam \(6,6,6,8,1,3\) → \(\dfrac{6!}{3!,1!,1!,1!} = 120\)
Total: \(180 + 120 = \mathbf{300}\)
Exercício 2 — Subconjuntos de 5 dígitos de \(\{1,1,1,1,2,3\}\)
Quantos números de 5 algarismos podem ser formados escolhendo 5 dos 6 dígitos \(1,1,1,1,2,3\)?
Grupos disjuntos (quais 5 dos 6 usamos):
- \(\{1,1,1,1,2\}\): \(\dfrac{5!}{4!} = 5\)
- \(\{1,1,1,1,3\}\): \(\dfrac{5!}{4!} = 5\)
- \(\{1,1,1,2,3\}\): \(\dfrac{5!}{3!} = 20\)
Total: \(5 + 5 + 20 = \mathbf{30}\)
Os dois exercícios a seguir usam o mesmo mapa. A figura abaixo mostra a malha com os pontos A, B e C marcados — e, antecipando o Exercício 4, destaca um caminho possível de A até C (em azul) e um de C até B (em amarelo):
Exercício 3 — Caminhos mínimos em malha
Num mapa com 7 avenidas N-S (Norte-Sul, ou seja, verticais) e 6 avenidas L-O (Leste-Oeste, ou seja, horizontais), quantos trajetos mínimos existem do canto inferior-esquerdo (A) ao canto superior-direito (B)?
Com 7 avenidas N-S há 6 blocos horizontais a cruzar (6 movimentos à direita); com 6 avenidas L-O há 5 blocos verticais a cruzar (5 movimentos para cima). Qualquer caminho que só avance — nunca retroceda — usa exatamente esses 11 passos, portanto 11 é o comprimento mínimo:
$$\frac{11!}{6!\,5!} = C(11,6) = \mathbf{462}$$
Exercício 4 — Caminhos mínimos passando por C
No mesmo mapa, quantos trajetos A→B passam pelo ponto C localizado 4 blocos à direita e 4 acima de A?
- A→C: 4D + 4C = \(\dfrac{8!}{4!,4!} = 70\)
- C→B: 2D + 1C = \(\dfrac{3!}{2!,1!} = 3\)
Total: \(70 \times 3 = \mathbf{210}\)
Próximos passos #
A permutação com repetição resolve o caso em que usamos todos os \(n\) elementos — inclusive os repetidos. A limitação que permanece é essa exigência de usar todos: e se quisermos escolher apenas \(r < n\) elementos de um conjunto com repetições permitidas, e a ordem ainda importar?
Esse cenário — selecionar \(r\) elementos com reposição entre \(n\) tipos disponíveis — leva aos arranjos com repetição, tema do próximo artigo da série.
