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 maximo possivel).

O conceito de permutação expressa a idéia de que objetos distintos podem ser arranjados em inúmeras ordens diferentes. 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 mais formalmente o conceito de permutação. Uma permutação de um alfabeto de 26 letras, por exemplo, é uma cadeia de letras com 26 delas, aparecendo, cada uma, uma única vez; esta definição funciona para qualquer alfabeto com N letras formando cadeias com comprimento de N letras. Ou seja, uma permutação é simplesmente uma sequência ordenada sem duas ou mais repetições de cada elemento retirado de um conjunto fixo de símbolos, e com comprimento máximo. 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

Consideremos mais de perto o exemplo do badalar de sinos. Vamos assumir que temos seis posições fixas nas quais um sino pode badalar (primeira, segunda, …, sexta); e que temos seis sinos (sejam A, B, …, F as notas da escala). Assim, o que chama-se arranjo é algo parecido com

B-A-F-E-D-C,

com cada sino posto em sua posição ordenada. O que se chama substituição é uma ordem do tipo 'mudar a ordem na qual A e F são tocadas e a ordem na qual E e D são tocadas'. Esta substituição nos daria um novo arranjo,

B-F-A-D-E-C.

A distinção entre arranjo e substituição é importante. Por exemplo, no badalar de sinos, nem todas as substituições são possíveis, por questões práticas. As instruções para os badaladores de sinos tomam a forma de uma lista de arranjos, na qual apenas sinos vizinhos são intercambiados de uma 'rodada' a outra.

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?

1. Para o primeiro membro de todas as permutações possíveis se escolhe um elemento de todos os n possíveis.
2. Uma vez já utilizado um dos n elementos , para o segundo membro da permutação há (n − 1) elementos para escolher desse conjunto.
3. O terceiro membro pode ser preenchido de (n − 2) maneiras, devido ao uso dos que o antecederam.
4. 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.

Outra 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 é novamento colocado na terceira posição, mas se aplicássemos novamente, veriamos 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

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.

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.

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.

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.

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. Mais eu ainda acho que o soneca gosta de dá o lolo

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.

Ver também

• Permutação Circular
• Permutação e Combinação
• Permutação Par e Ímpar
• Combinação
• Desarranjo ou permutação caótica
• Permutação de Josephus
• Grupo Simétrico
• Grupo de Permutação
• Ordem Circular
• Ordem fraca de Permutações
• Cifra de substituição
• Rede de Escolha
• Permutação Aleatória