Permutações Simples e Circulares

Quantos anagramas tem a palavra VIRUS? Quantas formas 5 amigos podem se sentar ao redor de uma mesa redonda? Essas perguntas têm estrutura diferente das que vimos no artigo sobre Princípios Aditivo e Multiplicativo: aqui queremos ordenar todos os elementos de um conjunto, não apenas escolher alguns deles.

Por que permutações?

#

Ordenar elementos é uma operação fundamental em computação e matemática:

• Análise de algoritmos: para ordenar \(n\) elementos, existem \(n!\) arranjos possíveis. O contraste entre um algoritmo O(n!) — que testaria todas as ordens — e um O(n log n) como o mergesort ilustra por que a escolha do algoritmo certo pode significar a diferença entre milissegundos e tempo astronômico.
• Criptografia: cifras de transposição reordenam os caracteres de um texto como operação de codificação. A segurança depende de quantas permutações existem — exatamente \(n!\) para um texto de \(n\) caracteres distintos.
• Escalonamento de tarefas: \(n\) processos independentes podem ser executados em \(n!\) ordens. Encontrar a sequência de menor custo é um problema de permutação — para \(n\) grande, a força bruta é impraticável.
• Testes de integração: cobrir todas as ordens de execução de \(n\) operações concorrentes exige testar \(n!\) sequências. Ferramentas de verificação formal (model checking) usam esse raciocínio para detectar condições de corrida em sistemas distribuídos.
• Roteamento: o número de rotas distintas que visitam \(n\) cidades exatamente uma vez é \((n-1)!\) — base do clássico Problema do Caixeiro-Viajante (TSP, do inglês Travelling Salesman Problem).

Este artigo formaliza a permutação simples (ordenação em fila) e a permutação circular (ordenação em círculo), com exemplos de anagramas, mesas redondas e restrições de adjacência.

Fatorial

#

Antes da permutação em si, precisamos do fatorial:

Intuição: se temos 4 canetas de cores distintas para distribuir entre 4 amigos, o primeiro recebe qualquer das 4, o segundo qualquer das 3 restantes, e assim por diante: \(4 \times 3 \times 2 \times 1 = 4! = 24\) distribuições.

Permutação Simples

#

Justificativa: \(n\) escolhas para o 1º elemento, \(n-1\) para o 2º, …, 1 para o último: \(n \cdot (n-1) \cdots 1 = n!\)

Exemplos

#

Exemplo 1 — Anagramas de VIRUS

Enunciado: De quantas formas distintas podem ser arranjadas as 5 letras da palavra VIRUS?

Solução: As 5 letras são todas distintas e queremos ordená-las todas em fila — trata-se de uma permutação simples. Contamos as escolhas posição a posição:

Exemplo 2 — Anagramas de VIRUS começando e terminando com consoante

Enunciado: Quantos anagramas de VIRUS começam e terminam com consoante?

Solução: Identificamos os tipos de letra em VIRUS: consoantes — V, R, S (3 letras); vogais — I, U (2 letras).

A estratégia é preencher primeiro as posições com restrição (1ª e 5ª), depois as demais:

Preencher as posições restritas primeiro evita o erro de calcular o total e depois tentar “remover” casos inválidos — aqui o Princípio Multiplicativo já garante que cada arranjo contado é válido.

import itertools
import math

letras = "VIRUS"

# Contar: P_5 = 5! = 120
print(math.factorial(len(letras)))           # 120

# Enumerar e filtrar: começando e terminando com consoante
consoantes = set("VRS")
anagramas = itertools.permutations(letras)
filtrados = [a for a in anagramas
             if a[0] in consoantes and a[-1] in consoantes]
print(len(filtrados))                         # 36

Exemplo 3 — Números de 5 algarismos com \(\{0, 5, 7, 8, 9\}\)

Enunciado: Usando cada algarismo do conjunto \(\{0, 5, 7, 8, 9\}\) exatamente uma vez, quantos números de 5 algarismos é possível formar?

Solução: O conjunto tem 5 algarismos distintos — sem restrição haveria \(P_5 = 120\) arranjos. A restrição é que o algarismo 0 não pode ocupar a 1ª posição: um número com 0 à frente teria, na prática, apenas 4 algarismos.

Raciocínio direto — preenche a posição restrita primeiro:

Verificação por complemento — subtrai os casos inválidos do total:

Os \(4!\) casos removidos correspondem a todos os arranjos em que o 0 ocupa a 1ª posição e os 4 algarismos restantes preenchem as demais posições livremente.

Exemplo 4 — Show: 4 mulheres e 5 homens em lugares consecutivos, grupos separados

Enunciado: Nove amigos assistem a um show com lugares marcados consecutivos. As 4 mulheres devem sentar todas juntas e os 5 homens também. De quantas formas podem se sentar?

Solução: Como os lugares são marcados e consecutivos (fila linear), há duas possibilidades para a ordem dos blocos: [M M M M | H H H H H] ou [H H H H H | M M M M]. Dentro de cada bloco, os membros se ordenam livremente.

Permutação Circular

#

Ao organizar pessoas ao redor de uma mesa redonda, o que importa é a posição relativa — não existe uma “primeira cadeira”. Rotações da mesma disposição contam como a mesma permutação.

Intuição: cada permutação circular equivale a \(n\) permutações lineares (cada rotação gera uma nova ordenação em fila, mas a mesma disposição em círculo). Portanto, dividimos por \(n\).

Exemplos

#

Exemplo 1 — 5 amigos ao redor de uma mesa redonda

Enunciado: De quantas formas 5 amigos podem se sentar ao redor de uma mesa redonda?

Solução: Em uma fila, a posição de cada pessoa é absoluta. Em uma mesa redonda, o que importa é a posição relativa entre os presentes — deslocar todos uma cadeira para a direita não cria uma nova disposição, apenas uma rotação da mesma.

Para eliminar rotações equivalentes, fixamos uma pessoa em qualquer cadeira e permutamos as outras 4:

Exemplos 2 e 3 — Dois elementos não adjacentes: complemento vs. inserção sequencial

Os próximos dois exemplos resolvem o mesmo tipo de problema — dois elementos específicos não podem ser adjacentes em uma disposição circular — com estratégias diferentes. O objetivo é mostrar quando cada abordagem é mais natural.

O diagrama abaixo resume a escolha: a pergunta-chave é se os casos proibidos são fáceis de contar diretamente.

flowchart TD
    A["Dois elementos não podem ser adjacentes
em uma disposição circular"] --> B{"Os casos proibidos
são fáceis de contar
como um bloco?"}
    B -->|Sim| C["**Complemento**
Total − Proibidos"]
    B -->|Não| D["**Inserção sequencial**
Construir evitando
a restrição desde o início"]
    C --> E["Ex. 2 — 5 crianças
24 − 12 = **12**"]
    D --> F["Ex. 3 — 6 crianças
6 × 4 × 3 = **72**"]

Exemplo 2 — Ciranda de 5 crianças: estratégia do complemento

Enunciado: Cinco crianças (\(c_1, c_2, c_3, c_4, c_5\)) formam uma roda de ciranda. De quantas formas podem se arranjar de modo que \(c_1\) e \(c_2\) não fiquem lado a lado?

Estratégia — complemento: em vez de contar diretamente os casos válidos (difícil), contamos o total e subtraímos os casos proibidos (mais fácil).

Total sem restrição:

Casos proibidos — \(c_1\) e \(c_2\) juntas: tratamos \(\{c_1, c_2\}\) como um bloco único. O problema vira arranjar 4 entidades em círculo e ordenar o bloco internamente:

Casos proibidos: \(6 \times 2 = 12\)

Quando usar complemento: quando os casos proibidos formam um conjunto compacto e fácil de descrever — aqui, basta tratar o par como um bloco.

Exemplo 3 — Roda de 6 crianças: estratégia da inserção sequencial

Enunciado: Seis crianças (\(c_1\) a \(c_6\)) formam uma roda de ciranda. De quantas formas podem se arranjar de modo que \(c_1\) e \(c_2\) não fiquem lado a lado?

Estratégia — inserção sequencial: posicionamos primeiro os elementos sem restrição, criando uma estrutura de lacunas, e inserimos os elementos problemáticos por último — escolhendo apenas posições válidas desde o início.

O diagrama a seguir ilustra as três etapas da construção — cada seta representa uma multiplicação pelo número de escolhas disponíveis naquele passo:

flowchart LR
    A["**1ª etapa**
c₃ c₄ c₅ c₆
em círculo
(PC)₄ = **6**"] -->|"× 4 posições
para c₁"| B["**2ª etapa**
Inserir c₁
**24** arranjos"] -->|"× 3 posições
não adjacentes
para c₂"| C["**3ª etapa**
Inserir c₂
**72** disposições"]

Quando usar inserção sequencial: quando o complemento seria difícil de calcular — por exemplo, se houvesse múltiplos pares proibidos, a contagem por complemento exigiria inclusão-exclusão. A inserção sequencial incorpora a restrição diretamente na construção, sem precisar subtrair nada.

Exemplo 4 — Show revisitado: e se o palco fosse circular?

Enunciado: Os mesmos 9 amigos do Exemplo 4 da seção anterior — 4 mulheres e 5 homens — agora se posicionam ao redor de um palco circular, mantendo a restrição de que todas as mulheres fiquem juntas e todos os homens juntos. De quantas formas podem se arranjar?

Solução: A estrutura de blocos é a mesma, mas o contexto mudou de linear para circular. O que muda?

No caso linear, os 2 blocos podiam ocupar duas ordens distintas na fila: [M|H] ou [H|M]. No círculo, girar todos uma posição transforma [M|H] em [H|M] — as duas ordens são rotações uma da outra e contam como a mesma disposição. Com apenas 2 blocos em círculo, há \((2-1)! = 1\) arranjo circular.

O fator 2 que existia no caso linear desaparece no circular: em uma roda, “mulheres à esquerda dos homens” e “homens à esquerda das mulheres” descrevem a mesma disposição relativa, apenas rotacionada.

import itertools
import math

pessoas = ["Ana", "Luís", "Fernando", "Clara", "Bruno"]

# Fixar "Ana" e permutar os outros 4: (5-1)! = 4! = 24
fixo    = pessoas[0]
demais  = pessoas[1:]

circulares = list(itertools.permutations(demais))
print(len(circulares))                    # 24
print(math.factorial(len(pessoas) - 1))   # 24

Comparando Permutações Lineares e Circulares

#

Para 3 pessoas (Ana, Luís, Fernando):

Tabela-Resumo

#

Exercícios

#

Próximos passos

#

A permutação ordena todos os \(n\) elementos. Quando queremos selecionar e ordenar apenas \(r \leq n\) deles — sem necessariamente usar todos —, entramos no domínio dos arranjos simples (ou permutações parciais), tema do próximo artigo da série.

Mais adiante, veremos como contar agrupamentos em que a ordem não importa — as combinações — completando a tríade fundamental da combinatória: permutações, arranjos e combinações.