Una permutación, también llamada “número de arreglo” u “orden”, puede ser un reordenamiento del tiempo de una lista ordenada S en una correspondencia uno a uno con la propia S. La cantidad de permutaciones en un grupo de n elementos está dada por n! (n factorial; Uspensky 1937, p. 18). Por ejemplo, hay 2!=2-1=2 permutaciones de {1,2}, a saber {1,2} y {2,1}, y 3!=3-2-1=6 permutaciones de {1,2,3}, a saber {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, y {3,2,1}. Las permutaciones de un inventario a menudo se encuentran dentro de la Lengua Wolfram usando el comando Permutaciones[lista]. Un inventario de longitud n a menudo se prueba para determinar si es una permutación de 1, …, n dentro de la Lengua Wolfram usando el comando PermutaciónListaQ[lista].

Sedgewick (1977) resume la variedad de algoritmos para generar permutaciones, e identifica el algoritmo de permutación de cambio mínimo de Heap (1963) como el más rápido en general (Skiena 1990, p. 10). Otro método de enumeración de las permutaciones fue dado por Johnson (1963; Séroul 2000, págs. 213 a 218).

El número de la forma de obtener un subconjunto ordenado de k elementos de un grupo de n elementos viene dado por

¡nP_k=(n!)/((n-k)!)

(1)

(Uspensky 1937, p. 18), donde n! puede ser un factorial. por ejemplo , hay 4!/2!=12 subconjuntos de 2 de {1,2,3,4}, a saber {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}, y {4,3}. Los subconjuntos no ordenados que contienen elementos k se denominan subconjuntos k de un conjunto dado.

La representación de una permutación como producto de los ciclos de permutación es exclusiva (hasta el ordenamiento de los ciclos). Un ejemplo de una descomposición cíclica es que la permutación {4,2,1,3} de {1,2,3,4}. esto se denota a menudo (2)(143), como los ciclos de permutación desarticulados (2) y (143). hay una excelente libertad para elegir la representación de una descomposición cíclica ya que (1) los ciclos son desarticulados y por lo tanto pueden ser dispuestos en cualquier orden, y (2) cualquier rotación de un ciclo dado especifica un ciclo equivalente (Skiena 1990, p. 20). Por lo tanto, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), y (2)(143) todos describen una permutación equivalente.

Otra notación que identifica explícitamente las posiciones ocupadas por los elementos antes y después de la aplicación de una permutación sobre n elementos utiliza una matriz de 2×n, donde la fila primaria es (123…n) y por lo tanto la segunda fila es que la nueva disposición. Por ejemplo, la permutación que cambia los elementos 1 y un par de y fija 3 se escribiría como

[1 2 3; 2 1 3].

(2)

Cualquier permutación es además producto de transposiciones. Las permutaciones se denotan comúnmente en orden lexicográfico o de transposición. Hay una correspondencia entre una permutación y un par de cuadros de Young llamados la correspondencia de Schensted.

El número de permutaciones erróneas de n objetos es [n!/e] donde [x] es que la función entera más cercana. Una permutación de n objetos ordenados durante la cual ningún objeto está en su lugar natural se denomina un desorden (o a veces, una permutación entera) y por lo tanto el número de tales permutaciones está dado por el subfactorial !n.

Utilizando

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

(3)

con x=y=1 da

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

(4)

así que el número de la forma de seleccionar 0, 1, …, o n a la vez es 2^n.

El conjunto de todas las permutaciones de un grupo de elementos 1, …, n se obtienen a menudo utilizando el procedimiento recursivo posterior

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 las permutaciones durante las cuales no se producen pares de elementos consecutivos (es decir, sucesiones ascendentes o descendentes). Para n=1, 2, … elementos, los números de tales permutaciones son 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Permutemos el conjunto de números enteros 1, 2, …, N y, por lo tanto, la secuencia resultante se dividirá en series crecientes. Denota la longitud típica de la n-ésima corrida a medida que N se aproxima al infinito, L_n. los pocos valores primarios se resumen en la siguiente tabla, donde e es la base del logaritmo napieriano (Le Lionnais 1983, págs. 41-42; Knuth 1998).

n L_n OEIS aproximado

1 e-1 A091131 1.7182818…

2 e^2-2e A091132 1.9524…

3 e^3-3e^2+3/2e A091133 1.9957…