Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Una permutación, también llamada “número de orden” u “orden”, es un reordenamiento de los elementos de una lista ordenada S en una correspondencia uno a uno con la propia S. El número de permutaciones en un conjunto de n elementos viene dado 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 una lista pueden ser encontradas en el lenguaje Wolfram usando el comando Permutaciones[lista]. Una lista de longitud n puede ser probada para ver si es una permutación de 1, …, n en el lenguaje Wolfram usando el comando PermutationListQ[list].

Sedgewick (1977) resume una serie 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ág. 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 formas de obtener un subconjunto ordenado de k elementos a partir de un conjunto de n elementos viene dado por

(Uspensky 1937, p. 18), donde n! es 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 conocen como subconjuntos k de un conjunto determinado.

La representación de un cambio como resultado de los ciclos de las etapas es novedosa (hasta la solicitud de los ciclos). Un caso de decadencia cíclica es la etapa {4,2,1,3} de {1,2,3,4}. Esto significa (2)(143), en relación con los ciclos de cambio desarticulado (2) y (143). Hay muchas oportunidades de elegir el retrato de una desintegración cíclica ya que (1) los ciclos son desarticulados y por lo tanto pueden ser determinados en cualquier solicitud, y (2) cualquier pivote de un ciclo dado indica un ciclo similar (Skiena 1990, p. 20). De esta manera, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), y (2)(143) todos retratan un cambio similar.

Otra documentación que reconoce expresamente las posiciones que ocupan los componentes cuando se utiliza un cambio en n componentes utiliza un marco de 2×n, donde la línea primaria es (123…n) y la línea posterior es el nuevo curso de acción. Por ejemplo, el cambio que conmuta los componentes 1 y 2 y fija el 3 estaría compuesto como

Cualquier permutación es también un 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 conocidos como la correspondencia de Schensted.

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

Usando

 (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 formas de elegir 0, 1, …, o n a la vez es 2^n.

El conjunto de todas las permutaciones de un conjunto de elementos 1, …, n puede obtenerse mediante el siguiente procedimiento 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 las permutaciones en las que 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).

Dejemos que el conjunto de números enteros 1, 2, …, N se permute y la secuencia resultante se divida en carreras crecientes. Denota la longitud media de la carrera n-ésimo a medida que N se acerca al infinito, L_n. Los primeros valores se resumen en el siguiente cuadro, donde e es la base del logaritmo natural (Le Lionnais 1983, págs. 41 y 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…