permutação

Permutação é a organização de elementos de um conjunto em uma ordem específica. Em matemática, a permutação differe da combinação porque a ordem das escolhas importa. Quando todos os n objetos distintos são usados, o número de permutações é n!, o fatorial de n.

Se apenas r objetos são escolhidos de um conjunto de n e a ordem importa, o número de permutações é P(n, r) = n! / (n − r)!. Este valor representa sequências de comprimento r formadas por elementos distintos, em que não há repetição de itens.

Existem variantes relevantes: permutações com repetição permitida, em que cada posição pode ser ocupada por qualquer dos n objetos. Nesse caso há n^r sequências. Também há permutações de um multiconjunto, em que alguns objetos se repetem, calculadas por n! / (n1! n2! ... nk!), onde n1, n2, ..., nk são as contagens dos objetos distintos.

Permutações circulares tratam de arranjos ao redor de uma mesa onde apenas posições relativas importam; para n itens distintos, o número de arranjos é (n − 1)!. Também há noções como derangements, que contam permutações sem itens na posição original.

Exemplos simples ajudam a ilustrar: com três letras A, B e C, há 3! = 6 permutações distintas: ABC, ACB, BAC, BCA, CAB, CBA. Para n = 5 e r = 3, P(5, 3) = 5 × 4 × 3 = 60. Em um multiconjunto com A, A e B, há 3! / 2! = 3 permutações: AAB, ABA, BAA.

As permutações são fundamentais em combinatória, probabilidade, teoria dos códigos, planejamento de experimentos e teoria de grafos.