Uma permutação, também chamada de “número do arranjo” ou “ordem”, é um rearranjo dos elementos de uma lista ordenada S em uma correspondência um-para-um com o próprio S. O número de permutações em um conjunto de n elementos é dado por n! (n factorial; Uspensky 1937, p. 18). Por exemplo, existem 2!=2-1=2 permutações de {1,2}, nomeadamente {1,2} e {2,1}, e 3!=3-2-1=6 permutações de {1,2,3}, nomeadamente {1,2,3,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, e {3,2,1}. As permutações de uma lista podem ser encontradas na Wolfram Language usando o comando Permutations[list]. Uma lista de comprimento n pode ser testada para ver se é uma permutação de 1, …, n na Wolfram Language usando o comando PermutationListQ[list].

Sedgewick (1977) resume uma série de algoritmos para gerar permutações, e identifica o algoritmo de permutação mínima de mudança de Heap (1963) para ser geralmente o mais rápido (Skiena 1990, p. 10). Outro método de enumeração de permutações foi dado por Johnson (1963; Séroul 2000, pp. 213-218).

O número de formas de obter um subconjunto ordenado de k elementos a partir de um conjunto de n elementos é dado por

(Uspensky 1937, p. 18), onde n! é um fatorial. Por exemplo, existem 4!/2!=12 2-subsets de {1,2,3,4}, nomeadamente {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}, e {4,3}. Os subconjuntos não ordenados contendo elementos k são conhecidos como os subconjuntos k de um determinado conjunto.

Um retrato de uma mudança como resultado de ciclos de estágio é novidade (até a solicitação dos ciclos). Um caso de decadência cíclica é o estágio {4,2,1,3} de {1,2,3,4}. Isto significa (2)(143), relacionado com os ciclos de mudança de junta (2) e (143). Há muitas oportunidades na escolha do retrato de uma desintegração cíclica, uma vez que (1) os ciclos são desarticulados e podem assim ser determinados em qualquer solicitação, e (2) qualquer pivô de um dado ciclo indica um ciclo semelhante (Skiena 1990, p. 20). Desta forma, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), e (2)(143) retratam todos uma mudança semelhante.

Outra documentação que reconhece expressamente as posições envolvidas pelos componentes quando a utilização de uma mudança em n componentes utiliza uma estrutura 2×n, onde a linha primária é (123…n) e a linha subseqüente é a nova linha de ação. Por exemplo, a alteração que muda os componentes 1 e 2 e fixa 3 seria composta como

Qualquer permutação é também um produto de transposições. As permutações são comumente denominadas em ordem lexicográfica ou de transposição. Existe uma correspondência entre uma permutação e um par de Tableaux Young, conhecida como a correspondência Schensted.

O número de permutações erradas de n objetos é [n!/e] onde [x] é a função inteira mais próxima. Uma permutação de n objetos ordenados em que nenhum objeto está em seu lugar natural é chamada de desarranjo (ou às vezes, uma permutação completa) e o número de tais permutações é dado pelo subfator !n.

Usando

 (x+y)^n=sum_(r=0)^n(n; r)x^(n-r)y^r         

(3)

com x=y=1 dá

 2^n=sum_(r=0)^n(n; r),                   

(4)

portanto o número de formas de escolher 0, 1, …, ou n de cada vez é 2^n.

O conjunto de todas as permutações de um conjunto de elementos 1, …, n pode ser obtido utilizando o seguinte procedimento recursivo

 1 2; / ; 2 1            

(5)

 1  2 3;     / ; 1 3 2 ; /    ; 3 1 2 ; |     ; 3 2 1 ; \    ; 2 3 1 ; \     ; 2  1 3            

(6)

Considere permutações nas quais não ocorra nenhum par de elementos consecutivos (isto é, sucessões ascendentes ou descendentes). Para n=1, 2, … elementos, os números de tais permutações são 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Que o conjunto de inteiros 1, 2, …, N seja permutado e a sequência resultante seja dividida em séries crescentes. Denotar a duração média da enésima corrida à medida que N se aproxima do infinito, L_n. Os primeiros valores estão resumidos na tabela seguinte, onde e é a base do logaritmo natural (Le Lionnais 1983, pp. 41-42; Knuth 1998).

nL_nOEISapproximate

1e-1A0911311  .7182818…

2e^2-2eA0911321           .9524…

3e^3-3e^2+3/2eA0911331          .9957…