Permutações P(n,k)

Permutações

Uma permutação de n elementos distintos é uma ordenação de todos eles. A contagem é simplesmente P(n) = n!. Quando há elementos repetidos, divide-se pelos fatoriais de cada grupo de repetição — a permutação com repetição: P(n; r₁, r₂, …, rₖ) = n! / (r₁!·r₂!·…·rₖ!). Exemplo: anagramas de "MATEMATICA" (10 letras: M×2, A×3, T×2, E, I, C) = 10! / (2!·3!·2!) = 3628800 / 24 = 151200. A permutação circular (objetos em volta de uma mesa redonda) é (n−1)!, porque rotações são consideradas idênticas.

Aplicações e contexto

Enumeração de senhas e PINs (tamanho do espaço de busca), embaralhamento Fisher–Yates (permutação aleatória uniforme em O(n)), criptografia clássica (cifras de transposição), problemas escolares de anagramas (ENEM, vestibular) e problema do caixeiro viajante (n! rotas possíveis).

Perguntas frequentes

Qual a diferença entre permutação e arranjo? A permutação usa todos os n elementos; o arranjo A(n,k) escolhe e ordena apenas k deles.

E da combinação? A combinação C(n,k) não considera a ordem. Permutações e arranjos sim.

Por que dividir por r! quando há repetições? As r! ordenações de um grupo repetido são indistinguíveis (mesma letra), então removemos a contagem em excesso.