Permutação

Em matemática, especialmente na álgebra abstrata e áreas relacionadas, uma permutação é uma bijeção, de um conjunto finito X nele mesmo.

Em combinatória, o termo permutação tem um significado tradicional, que é usado para incluir listas ordenadas sem repetição, mas não exaustiva (portanto com menos elementos do que o máximo possível).

O conceito de permutação expressa a ideia de que objetos distintos podem ser arranjados em inúmeras ordens diferentes.

Por exemplo, com os números de um a seis, cada ordem possível produz uma lista dos números, sem repetições. Uma de tais permutações é: (3, 4, 6, 1, 2, 5).

Por exemplo, quando se dá dois passos, um após o outro, podemos ter duas permutações: "pé esquerdo-pé direito" ou "pé direito-pé esquerdo", dependendo apenas do pé que dá o primeiro passo. Um exemplo mais complexo seria o do "change ringing", que é a arte de badalar sinos de afinação distinta em uma série de padrões. Há muitas ordens diferentes na qual um conjunto de seis sinos, cujas afinações diferem entre si, ou seja, cada um com um tom diferente, pode soar. Se os sinos forem numerados de um a seis, cada possível ordem terá uma lista com os números referente a ela e não haverá repetição alguma.

Há inúmeras formas de se definir formalmente o conceito de permutação. Uma permutação é uma sequência ordenada contendo cada símbolo de um conjunto uma única vez; tanto (1, 2, 2, 3, 4, 5, 6) quanto (1, 2, 4, 5, 6) não são permutações do conjunto dos números de 1 a 6. Pode-se assim apontar a diferença essencial entre uma permutação e um conjunto: em uma permutação, a ordem é relevante, já que os elementos são arranjados em uma ordem específica.

Arranjos e substituições

Um arranjo é uma disposição dos elementos de um conjunto em posições definidas (isto é, primeira, segunda, etc...), tal qual {1, 2, 3, 4, 5, 6} arranjado como (2, 1, 6, 5, 4, 3). Uma substituição é um conjunto de substituições de um elemento por outro, mas com nenhum elemento eliminado no resultado; por exemplo, tomando-se {1, 2, 3, 4, 5, 6} e substituindo-se 1 por 3, 3 por 4, e 4 por 1, nenhum elemento seria eliminado e o resultado seria uma substituição.

Tanto os arranjos como as substituições são comumente chamadas de permutações. Na Matemática, porém, a frase permutação de um conjunto sempre se refere a uma substituição.

Contando Permutações

Somente nessa seção, a definição tradicional é usada: uma permutação é uma lista ordenada sem repetições. É fácil contar os números de permutações do lado r quando escolhido de um ponto do lado n (obviamente com r≤n).

Por exemplo, se temos um total de 10 elementos, os inteiros {1, 2, …, 10}, uma permutação de três elementos desse conjunto é (2,3,1). Nesse caso, n = 10 e r = 3. Então de quantas maneiras isso pode ser completamente feito?

Para o primeiro membro de todas as permutações possíveis se escolhe um elemento de todos os n possíveis.
Uma vez já utilizado um dos n elementos , para o segundo membro da permutação há (n − 1) elementos para escolher desse conjunto.
O terceiro membro pode ser preenchido de (n − 2) maneiras, devido ao uso dos que o antecederam.
Esse padrão continua até que tenham sido utilizados os r membros na permutação. Isso significa que o último membro pode ser preenchido de (n − r + 1) maneiras.

Em síntese, se encontra um total de

n(n − 1)(n − 2) … (n − r + 1)

permutações diferentes dos r objetos, retirados do grupo dos n objetos. Se denotarmos esse número por P(n, r) e utilizar a notação factorial, pode-se escrever

P(n,r)={\frac {n!}{(n-r)!}}.

No exemplo acima, temos n = 10 e r = 3, então para encontrar quantos conjuntos únicos podem ser formados, como o anteriormente mencionado, calcula-se P(10,3) = 720.

Outras notações incluem ⁿP_r, P_n,r, ou _nP_r.

Dedução

Um arranjo $A_{n}^{d}$ só é possível quando $0\leq {d}\leq {n}$ e $0<n.$

Como provado pela combinatória, uma arranjo $A_{n}^{d}$ é o produto de $d$ números antecessores de $n.$

$A_{n}^{d}=n\left(n-1\right)\left(n-2\right)\left(n-3\right)\cdots \left(n-d+1\right)$

Isso pode ser escrito como representado a seguir:

$A_{n}^{d}=n\left(n-1\right)\cdots \left(n-d+1\right)\left({\frac {\left(n-d\right)\left(n-d-1\right)\cdots 1}{\left(n-d\right)\left(n-d-1\right)\cdots 1}}\right)$

Simplificando essa expressão para se visualizar melhor o processo seguinte, tem-se:

$A_{n}^{d}={\frac {n\left(n-1\right)\cdots 1}{\left(n-d\right)\left(n-d-1\right)\cdots 1}}$

Como o numerador é o produto de todos os números antecessores de $n,$ e o denominador é o produto de todos os números antecessores de $\left(n-d\right),$ é possível simplificar essa expressão, obtendo-se a fórmula do arranjo.

$A_{n}^{d}={\frac {n!}{\left(n-d\right)!}}$

Álgebra abstrata

Como explicado na seção anterior, em álgebra abstrata e outros ramos da matemática, o termo permutação (de um conjunto) é reservado para funções bijetivas de um conjunto finito nele mesmo. O exemplo anterior, das permutações dos números de 1 a 10, seria interpretado como funções do conjunto {1, …, 10} nele mesmo.

Existem duas principais notações para representar tais permutações. Em relação a notação,pode-se arranjar a ordem "natural" dos elementos a serem permutados numa fileira, e a nova ordem em outra fileira:

{\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}

Isto significa que, na primeira posição o segundo elemento do conjunto deve ser posto, na segunda posição o quinto elemento no conjunto deve ser colocado, e assim em diante. Alternadamente, se tivermos um conjunto finito de elementos (que não precisam ser inteiros), nós podemos primeiramente criar uma associação entre cada elemento e um inteiro - mais precisamente, nós podemos criar um mapeamento ν(s) : S → Z onde V é bijetora e S é a nossa piscina de elementos. Pode-se ler a notação acima como um mapeamento do elemento ν⁻¹(1) to element ν⁻¹(2), element ν⁻¹(2) to element ν⁻¹(5), e assim em diante.

De forma alternativa, podemos representar a permutação em termos de como os elementos mudam quando a permutação é aplicada. Se olharmos no exemplo de permutação anterior, se pegarmos um elemento na primeira posição, o resultado da permutação é então colocado na segunda posição, e o resultado após aplicada a permutação é novamente colocado na terceira posição. Mas se aplicássemos novamente, veríamos que o elemento voltaria à primeira permutação. Esse comportamento é chamado de "Ciclo", e podemos representar esse ciclo como (1 2 5), ou (2 5 1) ou ainda (5 1 2), mas não como (1 5 2), por exemplo. O próximo ciclo começa com qualquer outro elemento não considerado até agora, até que cada elemento apareça no ciclo.

Podemos então representar a permutação como uma série de ciclos. A permutação anterior tinha uma forma de ciclo (1 2 5)(3 4). A ordem dos ciclos não é relevante (mas, como dito anteriormente, a ordem dos elementos "dentro" dos ciclos é).

Portanto, uma mesma permutação pode ser escrita como (4 3)(2 5 1). A forma canônica de permutação posiciona os elementos em ordem crescente.

Essa notação geralmente omite pontos fixos, isto é, elementos mapeados a si mesmos. Sendo assim, (1 3)(2)(4 5) pode ser representado simplesmente por (1 3)(4 5), já que o ciclo de apenas um elemento não tem efeito.

Uma permutação que consiste apenas de um ciclo é em si chamada de ciclo. O número de entradas de um ciclo é chamada "tamanho". Por exemplo, o tamanho de (1 2 5) é três.

Uma terminologia especial é usada para descrever ciclos de dois elementos consecutivos - Esses são "transposições", já que em um ciclo de tamanho dois, os elementos são meramente transpostos.

Permutações especiais

Permutação identidade

Se imaginarmos uma permutação que troca o primeiro elemento com ele mesmo, o segundo com ele mesmo, e assim por diante, nós não mudamos a posição de nenhum elemento. Por causa disso, essa permutação é chamada de permutação identidade, porque ela age como elemento neutro na composição de permutações.

Permutação inversa

Dada uma permutação P e a permutação identidade I, pode-se descrever uma permutação $P^{-1}$ que desfaz as trocas feitas por P. Aplicar P e, em seguida, aplicar $P^{-1}$ é o mesmo que aplicar a permutação identidade I. Sempre existe esta permutação inversa, porque as permutações são bijetivas.

Permutação produto

Pode-se definir o produto de duas permutações: sejam P e Q permutações, então executar P e, em seguida, Q é o mesmo que executar uma permutação R, que é definida como o produto de P por Q. Para mais detalhes, ver grupo de simetrias e grupo de permutações.

Permutação par e ímpar

Uma permutação par é uma permutação que pode ser expressa como o produto de um número par de transposições. A identidade é uma permutação par, porque ela pode ser expressa como (1 2)(1 2).

Uma permutação ímpar é aquela que pode ser expressa por um número ímpar de transposições. Pode-se mostrar que uma permutação não pode ser par e ímpar ao mesmo tempo.

Matriz de permutação

Pode-se também representar a permutação em forma de matriz, a matriz resultante é uma matriz de permutação.

Permutações na computação

Alguns dos livros mais velhos vêem as permutações como associações, como mencionado acima. Para a ciência da computação, essas são operações de associação com valores.

1, 2, …, n

associado a variáveis

x₁, x₂, …, x_n.

Cada valor deve ser associado apenas uma vez.

A diferença entre associação e substituição então é ilustrativa de um ponto no qual programação funcional e programação imperativa diferem — programação funcional pura não tem mecanismo de associação. A convenção matemática atual caracteriza permutações apenas como funções e a operação nelas é a composição de função; programadores funcionais seguem isso. Na linguagem de associação uma substituição é uma instrução para trocar os valores associados simultaneamente, um problema notável.

Permutações numéricas

Números fatorádicos podem ser usados para associar números a permutações, de modo que dado um fatorádico n, pode-se rapidamente encontrar a permutação correspondente.

Referências

Weisstein, Eric W. «Permutação». MathWorld (em inglês)

Ver também

Wikcionário

O Wikcionário tem o verbete permutação.