Arranjos Simples: Ordenar sem Usar Tudo

Em uma corrida com 10 participantes, de quantas formas o pódio (1º, 2º, 3º lugar) pode ser preenchido? Aqui usamos apenas 3 dos 10 atletas, e a ordem importa (1º ≠ 2º). Isso é um arranjo simples.

Por que arranjos simples?

#

Selecionar e ordenar um subconjunto de elementos, sem necessariamente usar todos, é uma operação central em computação e matemática:

• Segurança: senhas de comprimento \(r\) sem repetição, tiradas de um alfabeto de \(n\) símbolos, totalizam \(A(n, r)\) possibilidades, e o arranjo dimensiona o espaço que um atacante de força bruta precisa percorrer.
• Placas e identificadores únicos: sistemas alfanuméricos sem repetição de caracteres usam o arranjo para calcular quantos identificadores distintos podem ser emitidos, exatamente o exemplo resolvido a seguir.
• Escalonamento: a ordenação de \(r\) processos entre \(n\) disponíveis numa fila de prioridade corresponde a \(A(n, r)\) sequências possíveis.
• Rotas e grafos: o número de caminhos simples que passam por \(r\) vértices distintos, em ordem, num grafo completo de \(n\) vértices é \(A(n, r)\), base de algoritmos de busca em espaço de estados.
• Rankings: pódios, listas de recomendação ordenada e resultados de torneios são arranjos, porque importa quem foi escolhido e em qual posição.

Da permutação ao arranjo

#

A permutação simples, abordada no artigo anterior, ordena todos os \(n\) elementos. O arranjo simples relaxa essa exigência: ordenamos apenas \(r < n\) deles. O diagrama abaixo situa o arranjo na família dos agrupamentos:

flowchart TD
    A["n elementos distintos"] --> B{"Usar todos?"}
    B -->|"Sim"| C["Permutação Simples
P_n = n!"]
    B -->|"Não — escolher r < n"| D{"Ordem importa?"}
    D -->|"Sim"| E["Arranjo Simples
A(n,r) = n!/(n-r)!"]
    D -->|"Não"| F["Combinação Simples
(próximo artigo)"]

Arranjo Simples

#

Na literatura internacional, o mesmo número costuma aparecer como \(P(n, r)\) ou \({}_{n}P_{r}\), de permutation, e é a tecla nPr das calculadoras científicas.

Casos notáveis:

• \(A(n, n) = n!\), o mesmo que a permutação simples \(P_n\)
• \(A(n, 1) = n\)

Voltando ao exemplo da abertura: o pódio de uma corrida com 10 atletas tem \(A(10, 3) = 10 \times 9 \times 8 = 720\) configurações distintas.

A figura abaixo mostra de onde vem esse produto. Cada lugar do pódio é uma caixinha com o número de atletas ainda disponíveis para ela, e cada lugar preenchido deixa um atleta a menos para os seguintes; no caso geral, as \(r\) caixinhas levam \(n, n-1, \ldots, n-r+1\):

Exemplos Resolvidos

#

Prédio com 8 andares: par (entrada, saída) distinto

#

Enunciado: Um prédio tem 8 andares. Uma pessoa entra no elevador em um andar e sai em outro diferente. De quantas maneiras distintas pode ocorrer esse par ordenado (entrada, saída)?

Solução: Queremos escolher 2 andares distintos entre 8, onde a ordem importa, já que entrar no 3º e sair no 7º é diferente de entrar no 7º e sair no 3º. Trata-se de um arranjo simples de 8 elementos tomados 2 a 2.

Preenchemos as duas posições sequencialmente:

CREATE TABLE andares (andar INT);
INSERT INTO andares VALUES (1),(2),(3),(4),(5),(6),(7),(8);

SELECT a.andar AS entrada, b.andar AS saida
FROM   andares a
CROSS JOIN andares b
WHERE  a.andar <> b.andar
ORDER BY entrada, saida;
-- 56 linhas = A(8, 2)

SELECT COUNT(*)
FROM   andares a
CROSS JOIN andares b
WHERE  a.andar <> b.andar;
-- 56

Programa de 3 atividades entre 4

#

Enunciado: Um estudante tem 4 atividades disponíveis: leitura (L), exercício (E), desenho (D) e culinária (C). Ele quer montar um programa diário com 3 dessas atividades em sequência definida: a ordem importa, pois determina o que fará pela manhã, tarde e noite. De quantas formas distintas pode montar esse programa?

Solução: Queremos selecionar e ordenar 3 atividades distintas entre 4. Preenchemos as três posições sequencialmente, sem repetição:

Rotas entre 5 cidades: rota ordenada de 3 cidades

#

Enunciado: Um viajante precisa traçar uma rota que passe por exatamente 3 cidades entre São Paulo, Rio de Janeiro, Belo Horizonte, Porto Alegre e Curitiba. A ordem das cidades visitadas determina a rota: SP → RJ → BH é diferente de RJ → SP → BH. Quantas rotas distintas ele pode planejar?

Solução: Queremos uma sequência ordenada de 3 cidades distintas escolhidas entre 5. Preenchemos as três etapas da rota sequencialmente:

import itertools, math

# A(5, 3) — rotas de 3 cidades entre 5
cidades = ["SP", "RJ", "BH", "POA", "CWB"]
rotas = list(itertools.permutations(cidades, 3))
print(len(rotas))                          # 60

# Confirma com a fórmula
def arranjo(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(arranjo(5, 3))                       # 60

CREATE TABLE cidades (cidade TEXT);
INSERT INTO cidades VALUES ('SP'),('RJ'),('BH'),('POA'),('CWB');

SELECT a.cidade AS origem,
       b.cidade AS escala,
       c.cidade AS destino
FROM   cidades a
CROSS JOIN cidades b
CROSS JOIN cidades c
WHERE  a.cidade <> b.cidade
  AND  b.cidade <> c.cidade
  AND  a.cidade <> c.cidade
ORDER BY origem, escala, destino;

SELECT COUNT(*)
FROM   cidades a
CROSS JOIN cidades b
CROSS JOIN cidades c
WHERE  a.cidade <> b.cidade
  AND  b.cidade <> c.cidade
  AND  a.cidade <> c.cidade;
-- 60 = A(5, 3)

Placas de veículos: 3 letras e 4 dígitos distintos

#

Enunciado: Um sistema de placas usa o formato AAA-NNNN, com 3 letras do alfabeto (26 letras) seguidas de 4 dígitos (de 0 a 9). Nenhuma letra pode se repetir nas 3 posições de letras, e nenhum dígito pode se repetir nas 4 posições de dígitos. Quantas placas distintas podem ser emitidas?

Solução: A escolha das letras e a escolha dos dígitos são etapas independentes entre si, portanto aplicamos o Princípio Multiplicativo entre os dois blocos.

Bloco de letras, \(A(26, 3)\): selecionamos e ordenamos 3 letras distintas entre 26.

Bloco de dígitos, \(A(10, 4)\): selecionamos e ordenamos 4 dígitos distintos entre 10.

Total, pelo Princípio Multiplicativo entre os dois blocos:

Números de 3 algarismos distintos com \(\{0, 1, \ldots, 9\}\)

#

Enunciado: Quantos números de 3 algarismos (entre 100 e 999), com todos os algarismos distintos, podem ser formados com os dígitos \(\{0, 1, \ldots, 9\}\)?

Solução: A dificuldade é a restrição: o 1º algarismo não pode ser 0, caso contrário o número teria apenas 2 algarismos na prática (ex.: 053 = 53). Apresentamos duas abordagens.

Abordagem direta (preencher a posição restrita primeiro):

A estratégia é sempre começar pela posição com restrição, depois preencher as demais.

Verificação por complemento:

Contamos todos os arranjos de 3 dígitos distintos (inclusive os que começam com 0) e subtraímos os inválidos:

• Total sem restrição: \(A(10, 3) = 10 \times 9 \times 8 = 720\)
• Começam com 0: 0 fixado na 1ª posição, 2 dígitos escolhidos entre os 9 restantes → \(A(9, 2) = 9 \times 8 = 72\)

from itertools import permutations

digitos = range(10)  # {0, 1, ..., 9}

# Todos os arranjos de 3 dígitos distintos (inclusive os que começam com 0)
todos = list(permutations(digitos, 3))
print(len(todos))     # 720 = A(10, 3)

# Apenas os válidos como número de 3 algarismos (sem 0 na 1ª posição)
validos = [p for p in todos if p[0] != 0]
print(len(validos))   # 648

# Casos inválidos: começam com 0 → A(9, 2) arranjos dos 9 dígitos restantes
invalidos = [p for p in todos if p[0] == 0]
print(len(invalidos)) # 72 = A(9, 2)

# Confirma o complemento
assert len(validos) + len(invalidos) == len(todos)  # 648 + 72 = 720 ✓

Números pares de 4 algarismos distintos com \(\{0,1,\ldots,9\}\)

#

Enunciado: Quantos números de 4 algarismos (entre 1000 e 9999), com todos os algarismos distintos, são pares, usando os dígitos \(\{0, 1, \ldots, 9\}\)?

Solução: Um número é par quando seu último algarismo (unidades) pertence a \(\{0, 2, 4, 6, 8\}\). Separamos em dois casos conforme o dígito final, pois a restrição do 1º algarismo (≠ 0) muda dependendo de qual dígito par ocupa a última posição.

Caso I (último algarismo = 0):

Com 0 fixado na última posição, ele não pode aparecer na 1ª, então a restrição do 1º algarismo já está satisfeita.

Caso II (último algarismo \(\in \{2, 4, 6, 8\}\)):

Agora 0 não foi usado na última posição, portanto continua proibido na 1ª posição.

Total, pelo Princípio Aditivo entre os dois casos:

Tabela-Resumo: Permutação vs. Arranjo

#

Exercícios

#

Próximos passos

#

O arranjo simples resolve o caso em que a ordem importa e usamos apenas \(r < n\) elementos. Sua limitação é exatamente essa exigência de ordem: em muitas situações práticas (montar uma comissão, escolher ingredientes de uma receita, selecionar filmes para assistir) só interessa quais elementos foram escolhidos, não em que sequência.

Quando a ordem não importa, chegamos às combinações simples, o próximo tema da série. Com permutações, arranjos e combinações teremos a tríade fundamental da combinatória, suficiente para resolver a grande maioria dos problemas de contagem.