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.
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.
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? 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 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 nPr, Pn,r, ou nPr.
Dedução
Um arranjo A n d {\displaystyle A_{n}^{d}} só é possível quando 0 ≤ d ≤ n {\displaystyle 0\leq {d}\leq {n}} e 0 < n . {\displaystyle 0<n.} Como provado pela combinatória, uma arranjo A n d {\displaystyle A_{n}^{d}} é o produto de d {\displaystyle d} números antecessores de n . {\displaystyle n.} A n d = n ( n − 1 ) ( n − 2 ) ( n − 3 ) ⋯ ( n − d + 1 ) {\displaystyle 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 ( n − 1 ) ⋯ ( n − d + 1 ) ( ( n − d ) ( n − d − 1 ) ⋯ 1 ( n − d ) ( n − d − 1 ) ⋯ 1 ) {\displaystyle 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)}
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: 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(1) to element ν−1(2), element ν−1(2) to element ν−1(5), e assim em diante.
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 {\displaystyle P^{-1}} que desfaz as trocas feitas por P. Aplicar P e, em seguida, aplicar P − 1 {\displaystyle 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.
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. 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.
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.
