Permutación

Mathematical version of an order change

Según el primer significado de permutación, cada una de las seis filas es una permutación diferente de tres bolas distintas.

En matemáticas , una permutación de un conjunto puede significar una de dos cosas diferentes:

• una disposición de sus miembros en una secuencia u orden lineal , o
• el acto o proceso de cambiar el orden lineal de un conjunto ordenado. ^[1]

Un ejemplo del primer significado son las seis permutaciones (ordenaciones) del conjunto {1, 2, 3}: escritas como tuplas , son (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) y (3, 2, 1). Los anagramas de una palabra cuyas letras son todas diferentes también son permutaciones: las letras ya están ordenadas en la palabra original, y el anagrama las reordena. El estudio de las permutaciones de conjuntos finitos es un tema importante en combinatoria y teoría de grupos .

Las permutaciones se utilizan en casi todas las ramas de las matemáticas y en muchos otros campos de la ciencia. En informática , se utilizan para analizar algoritmos de ordenación ; en física cuántica , para describir estados de partículas; y en biología , para describir secuencias de ARN .

El número de permutaciones de n objetos distintos es n  factorial , usualmente escrito como n !, lo que significa el producto de todos los números enteros positivos menores o iguales a n .

Según el segundo significado, una permutación de un conjunto S se define como una biyección de S a sí mismo. ^{[2] [3]} Es decir, es una función de S a S para la cual cada elemento aparece exactamente una vez como valor de imagen . Una función de este tipo es equivalente a la reorganización de los elementos de S en la que cada elemento i se reemplaza por el correspondiente . Por ejemplo, la permutación (3, 1, 2) se describe mediante la función definida como ${\displaystyle \sigma :S\to S}$ ${\displaystyle \sigma (i)}$ ${\displaystyle \sigma }$

${\displaystyle \sigma (1)=3,\quad \sigma (2)=1,\quad \sigma (3)=2}$.

El conjunto de todas las permutaciones de un conjunto forma un grupo llamado grupo simétrico del conjunto. La operación de grupo es la composición de funciones (realizar un reordenamiento tras otro), lo que da como resultado otra función (reordenamiento). Las propiedades de las permutaciones no dependen de la naturaleza de los elementos que se permutan, sino solo de su número, por lo que a menudo se considera el conjunto estándar . ${\displaystyle S=\{1,2,\ldots ,n\}}$

En combinatoria elemental, las k -permutaciones , o permutaciones parciales , son las disposiciones ordenadas de k elementos distintos seleccionados de un conjunto. Cuando k es igual al tamaño del conjunto, se trata de permutaciones en el sentido anterior.

En el popular cubo de Rubik, inventado en 1974 por Ernő Rubik , cada giro de las caras del rompecabezas crea una permutación de los colores de la superficie.

Historia

Las permutaciones llamadas hexagramas se utilizaron en China en el I Ching ( Pinyin : Yi Jing) ya en el año 1000 a. C.

En Grecia, Plutarco escribió que Jenócrates de Calcedonia (396–314 a. C.) descubrió el número de sílabas diferentes posibles en la lengua griega. Este habría sido el primer intento registrado de resolver un problema difícil de permutaciones y combinaciones. ^[4]

Al-Khalil (717–786), matemático y criptógrafo árabe , escribió el Libro de los mensajes criptográficos , que contiene el primer uso de permutaciones y combinaciones para enumerar todas las posibles palabras árabes con y sin vocales. ^[5]

La regla para determinar el número de permutaciones de n objetos era conocida en la cultura india alrededor del año 1150 d. C. El Lilavati del matemático indio Bhāskara II contiene un pasaje que se traduce de la siguiente manera:

El producto de la multiplicación de la serie aritmética que comienza y aumenta en la unidad y continúa hasta el número de lugares, será la variación del número con cifras específicas. ^[6]

En 1677, Fabian Stedman describió los factoriales al explicar el número de permutaciones de campanas en el cambio de sonido . Empezando con dos campanas: "primero, se debe admitir que dos pueden variar de dos maneras", lo que ilustra mostrando 1 2 y 2 1. ^[7] Luego explica que con tres campanas hay "tres veces dos cifras que se deben producir a partir de tres", lo que nuevamente se ilustra. Su explicación implica "descarta 3 y quedará 1,2; descarta 2 y quedará 1,3; descarta 1 y quedará 2,3". ^[8] Luego pasa a cuatro campanas y repite el argumento de descarte mostrando que habrá cuatro conjuntos diferentes de tres. Efectivamente, este es un proceso recursivo. Continúa con cinco campanas utilizando el método de "descarte" y tabula las 120 combinaciones resultantes. ^[9] En este punto se da por vencido y comenta:

Ahora bien, la naturaleza de estos métodos es tal que los cambios en un número comprenden los cambios en todos los números menores, ... de tal manera que un conjunto completo de cambios en un número parece formarse mediante la unión de los conjuntos completos de todos los números menores en un cuerpo entero; ^[10]

Stedman amplía la consideración de las permutaciones; pasa a considerar el número de permutaciones de las letras del alfabeto y de caballos de un establo de 20. ^[11]

Un primer caso en el que se estudiaron cuestiones matemáticas aparentemente no relacionadas con la ayuda de permutaciones se produjo alrededor de 1770, cuando Joseph Louis Lagrange , en el estudio de las ecuaciones polinómicas, observó que las propiedades de las permutaciones de las raíces de una ecuación están relacionadas con las posibilidades de resolverla. Esta línea de trabajo desembocó finalmente, a través de los trabajos de Évariste Galois , en la teoría de Galois , que da una descripción completa de lo que es posible e imposible con respecto a la resolución de ecuaciones polinómicas (en una incógnita) por radicales. En las matemáticas modernas, hay muchas situaciones similares en las que la comprensión de un problema requiere estudiar ciertas permutaciones relacionadas con él.

Las permutaciones desempeñaron un papel importante en el criptoanálisis de la máquina Enigma , un dispositivo de cifrado utilizado por la Alemania nazi durante la Segunda Guerra Mundial . En particular, una propiedad importante de las permutaciones, a saber, que dos permutaciones son exactamente conjugadas cuando tienen el mismo tipo de ciclo, fue utilizada por el criptólogo Marian Rejewski para descifrar el cifrado alemán Enigma entre los años 1932 y 1933. ^{[12] [13]}

Definición

En los textos de matemáticas se acostumbra a indicar las permutaciones con letras griegas minúsculas. Normalmente se utilizan o . ^[14] ${\displaystyle \alpha ,\beta ,\gamma }$ ${\displaystyle \sigma ,\tau ,\rho ,\pi }$

Una permutación se puede definir como una biyección (una aplicación invertible, una función biyectiva y sobreyectiva) de un conjunto S a sí mismo:

${\displaystyle \sigma :S\ {\stackrel {\sim }{\longrightarrow }}\ S.}$

La permutación identidad se define por para todos los elementos , y se puede denotar por el número , ^[a] por , o por un único 1-ciclo (x). ^{[15] [16]} El conjunto de todas las permutaciones de un conjunto con n elementos forma el grupo simétrico , donde la operación de grupo es composición de funciones . Así, para dos permutaciones y en el grupo , su producto se define por: ${\displaystyle \sigma (x)=x}$ ${\displaystyle x\in S}$ ${\displaystyle 1}$ ${\displaystyle {\text{id}}={\text{id}}_{S}}$ ${\displaystyle S_{n}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle S_{n}}$ ${\displaystyle \pi =\sigma \tau }$

${\displaystyle \pi (i)=\sigma (\tau (i)).}$

La composición se escribe normalmente sin punto ni ningún otro signo. En general, la composición de dos permutaciones no es conmutativa : ${\displaystyle \tau \sigma \neq \sigma \tau .}$

Como biyección de un conjunto a sí mismo, una permutación es una función que realiza un reordenamiento de un conjunto, denominado permutación activa o sustitución . Un punto de vista más antiguo ve una permutación como un arreglo ordenado o lista de todos los elementos de S , llamado permutación pasiva . ^[17] Según esta definición, todas las permutaciones en § Notación de una línea son pasivas. Este significado es sutilmente distinto de cómo se usa pasivo (es decir, alias ) en Transformación activa y pasiva y en otros lugares, ^{[18] [19]} que consideraría todas las permutaciones abiertas a la interpretación pasiva (independientemente de si están en notación de una línea, notación de dos líneas, etc.).

Una permutación se puede descomponer en uno o más ciclos disjuntos que son las órbitas del grupo cíclico que actúa sobre el conjunto S . Un ciclo se obtiene aplicando repetidamente la permutación a un elemento: , donde suponemos . Un ciclo que consta de k elementos se denomina k -ciclo. (Véase § Notación de ciclos a continuación). ${\displaystyle \sigma }$ ${\displaystyle \langle \sigma \rangle =\{1,\sigma ,\sigma ^{2},\ldots \}}$ ${\displaystyle x,\sigma (x),\sigma (\sigma (x)),\ldots ,\sigma ^{k-1}(x)}$ ${\displaystyle \sigma ^{k}(x)=x}$

Un punto fijo de una permutación es un elemento x que se lleva consigo mismo, es decir , formando un 1-ciclo . Una permutación sin puntos fijos se denomina desarreglo . Una permutación que intercambia dos elementos (un único 2-ciclo) y deja los otros fijos se denomina transposición . ${\displaystyle \sigma }$ ${\displaystyle \sigma (x)=x}$ ${\displaystyle (\,x\,)}$

Notaciones

Se utilizan ampliamente varias notaciones para representar permutaciones de manera conveniente. La notación cíclica es una opción popular, ya que es compacta y muestra la estructura de la permutación con claridad. En este artículo se utilizará la notación cíclica a menos que se especifique lo contrario.

Notación de dos líneas

La notación de dos líneas de Cauchy ^{[20] [21]} enumera los elementos de S en la primera fila y la imagen de cada elemento debajo de él en la segunda fila. Por ejemplo, la permutación de S = {1, 2, 3, 4, 5, 6} dada por la función

${\displaystyle \sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1}$

se puede escribir como

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}.}$

Los elementos de S pueden aparecer en cualquier orden en la primera fila, por lo que esta permutación también podría escribirse:

${\displaystyle \sigma ={\begin{pmatrix}2&3&4&5&6&1\\6&5&4&3&1&2\end{pmatrix}}={\begin{pmatrix}6&5&4&3&2&1\\1&3&4&5&6&2\end{pmatrix}}.}$

Notación de una línea

Si existe un orden "natural" para los elementos de S , ^[b] digamos , entonces se usa esto para la primera fila de la notación de dos líneas: ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

Bajo este supuesto, se puede omitir la primera fila y escribir la permutación en notación de una línea como

${\displaystyle \sigma =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})}$,

es decir, como una disposición ordenada de los elementos de S . ^{[22] [23]} Se debe tener cuidado para distinguir la notación de una línea de la notación de ciclo que se describe a continuación: un uso común es omitir los paréntesis u otras marcas de cierre para la notación de una línea, mientras que se utilizan paréntesis para la notación de ciclo. La notación de una línea también se llama representación de palabras . ^[24]

El ejemplo anterior sería entonces:

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431.}$

(Es habitual utilizar comas para separar estas entradas sólo si algunas tienen dos o más dígitos).

Esta forma compacta es común en combinatoria elemental y en informática . Es especialmente útil en aplicaciones en las que las permutaciones se deben comparar como mayores o menores utilizando el orden lexicográfico .

Notación de ciclo

La notación de ciclos describe el efecto de aplicar repetidamente la permutación a los elementos del conjunto S , donde una órbita se denomina ciclo . La permutación se escribe como una lista de ciclos; dado que los ciclos distintos implican conjuntos disjuntos de elementos, esto se conoce como "descomposición en ciclos disjuntos".

Para escribir la permutación en notación cíclica se procede de la siguiente manera: ${\displaystyle \sigma }$

1. Escribe un corchete de apertura seguido de un elemento arbitrario x de : ${\displaystyle S}$ ${\displaystyle (\,x}$
2. Trace la órbita de x y escriba los valores bajo aplicaciones sucesivas de : ${\displaystyle \sigma }$ ${\displaystyle (\,x,\sigma (x),\sigma (\sigma (x)),\ldots }$
3. Repita hasta que el valor vuelva a x y cierre el paréntesis sin repetir x : ${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)}$
4. Continúe con un elemento y de S que aún no haya sido escrito y repita el proceso anterior: ${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)}$
5. Repita hasta que todos los elementos de S estén escritos en ciclos.

Además, es común omitir los 1-ciclos, ya que estos se pueden inferir: para cualquier elemento x en S que no aparezca en ningún ciclo, se supone implícitamente que . ^[25] ${\displaystyle \sigma (x)=x}$

Siguiendo la convención de omitir los ciclos 1, se puede interpretar un ciclo individual como una permutación que fija todos los elementos que no están en el ciclo (una permutación cíclica que tiene solo un ciclo de longitud mayor que 1). Entonces, la lista de ciclos disjuntos puede verse como la composición de estas permutaciones cíclicas. Por ejemplo, la permutación unifilar se puede escribir en notación de ciclo como: ${\displaystyle \sigma =265431}$

${\displaystyle \sigma =(126)(35)(4)=(126)(35).}$

Esto puede verse como la composición de permutaciones cíclicas: ${\displaystyle \sigma =\kappa _{1}\kappa _{2}}$

${\displaystyle \kappa _{1}=(126)=(126)(3)(4)(5),\quad \kappa _{2}=(35)=(35)(1)(2)(6).}$

Si bien las permutaciones en general no conmutan, los ciclos disjuntos sí lo hacen; por ejemplo:

${\displaystyle \sigma =(126)(35)=(35)(126).}$

Además, cada ciclo puede reescribirse desde un punto de inicio diferente; por ejemplo,

${\displaystyle \sigma =(126)(35)=(261)(53).}$

Por lo tanto, se pueden escribir los ciclos disjuntos de una permutación dada de muchas maneras diferentes. Una característica conveniente de la notación de ciclos es que la inversión de la permutación se da invirtiendo el orden de los elementos en cada ciclo. Por ejemplo,

${\displaystyle \sigma ^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).}$

Notación de ciclo canónico

En algunos contextos combinatorios resulta útil fijar un cierto orden para los elementos de los ciclos y de los ciclos (disjuntos) en sí mismos. Miklós Bóna denomina a las siguientes opciones de ordenación la notación de ciclo canónico:

• En cada ciclo, el elemento más grande se enumera primero.
• Los ciclos se ordenan en orden creciente de su primer elemento, sin omitir los ciclos 1.

Por ejemplo,

(513)(6)(827)(94)

es una permutación de S = {1, 2, . . . , 9} en notación de ciclo canónico. ^[26]

Richard Stanley llama a esto la "representación estándar" de una permutación, ^[27] y Martin Aigner utiliza la "forma estándar". ^[24] Sergey Kitaev también utiliza la terminología de la "forma estándar", pero invierte ambas opciones; es decir, cada ciclo enumera su elemento mínimo primero, y los ciclos se ordenan en orden decreciente de sus elementos mínimos. ^[28]

Composición de permutaciones

Hay dos formas de denotar la composición de dos permutaciones. En la notación más común, es la función que asigna cualquier elemento x a . La permutación más a la derecha se aplica primero al argumento, ^[29] porque el argumento se escribe a la derecha de la función. ${\displaystyle \sigma \cdot \tau }$ ${\displaystyle \sigma (\tau (x))}$

Una regla diferente para multiplicar permutaciones proviene de escribir el argumento a la izquierda de la función, de modo que la permutación más a la izquierda actúe primero. ^{[30] [31] [32]} En esta notación, la permutación a menudo se escribe como un exponente, por lo que σ actuando sobre x se escribe x ^σ ; luego el producto se define por . Este artículo utiliza la primera definición, donde la permutación más a la derecha se aplica primero. ${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$

La operación de composición de funciones satisface los axiomas de un grupo . Es asociativa , es decir , y los productos de más de dos permutaciones se escriben normalmente sin paréntesis. La operación de composición también tiene un elemento identidad (la permutación identidad ), y cada permutación tiene una inversa (su función inversa ) con . ${\displaystyle (\rho \sigma )\tau =\rho (\sigma \tau )}$ ${\displaystyle {\text{id}}}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma ^{-1}}$ ${\displaystyle \sigma ^{-1}\sigma =\sigma \sigma ^{-1}={\text{id}}}$

Otros usos del términopermutación

El concepto de permutación como un arreglo ordenado admite varias generalizaciones que han sido llamadas permutaciones , especialmente en la literatura antigua.

a-permutaciones denorte

En la literatura antigua y en los libros de texto elementales, una k -permutación de n (a veces llamada permutación parcial , secuencia sin repetición , variación o disposición ) significa una disposición ordenada (lista) de un subconjunto de k elementos de un conjunto n . ^{[c] [33] [34]} El número de tales k -permutaciones ( k -disposiciones) de se denota de diversas formas mediante símbolos como , , , , , o , ^[35] calculados mediante la fórmula: ^[36] ${\displaystyle n}$ ${\displaystyle P_{k}^{n}}$ ${\displaystyle _{n}P_{k}}$ ${\displaystyle ^{n}\!P_{k}}$ ${\displaystyle P_{n,k}}$ ${\displaystyle P(n,k)}$ ${\displaystyle A_{n}^{k}}$

${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }}$,

que es 0 cuando k > n , y en caso contrario es igual a

${\displaystyle {\frac {n!}{(n-k)!}}.}$

El producto está bien definido sin la suposición de que es un entero no negativo, y también es importante fuera de la combinatoria; se lo conoce como el símbolo de Pochhammer o como la -ésima potencia factorial descendente : ${\displaystyle n}$ ${\displaystyle (n)_{k}}$ ${\displaystyle k}$ ${\displaystyle n^{\underline {k}}}$

${\displaystyle P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.}$

Este uso del término permutación está estrechamente asociado con el término combinación para referirse a un subconjunto. Una k-combinación de un conjunto S es un subconjunto de k elementos de S : los elementos de una combinación no están ordenados. Ordenar las k -combinaciones de S de todas las formas posibles produce las k -permutaciones de S . El número de k -combinaciones de un n -conjunto, C ( n , k ), está por lo tanto relacionado con el número de k -permutaciones de n por:

${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!\,k!}}.}$

Estos números también se conocen como coeficientes binomiales , y generalmente se denotan : ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle C(n,k)={_{n}}C_{k}={\binom {n}{k}}.}$

Permutaciones con repetición

Las disposiciones ordenadas de k elementos de un conjunto S , donde se permite la repetición, se denominan k -tuplas . A veces se las ha denominado permutaciones con repetición , aunque no son permutaciones en el sentido habitual. También se las denomina palabras o cadenas sobre el alfabeto S . Si el conjunto S tiene n elementos, el número de k -tuplas sobre S es ${\displaystyle n^{k}.}$

Permutaciones de multiconjuntos

Permutaciones sin repetición a la izquierda, con repetición a la derecha

Si M es un multiconjunto finito , entonces una permutación de multiconjunto es una disposición ordenada de elementos de M en la que cada elemento aparece un número de veces exactamente igual a su multiplicidad en M. Un anagrama de una palabra que tiene algunas letras repetidas es un ejemplo de una permutación de multiconjunto. ^[d] Si las multiplicidades de los elementos de M (tomados en algún orden) son , , ..., y su suma (es decir, el tamaño de M ) es n , entonces el número de permutaciones de multiconjunto de M está dado por el coeficiente multinomial , ^[37] ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle m_{l}}$

${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.}$

Por ejemplo, el número de anagramas distintos de la palabra MISSISSIPPI es: ^[38]

${\displaystyle {\frac {11!}{1!\,4!\,4!\,2!}}=34650}$.

Una k -permutación de un multiconjunto M es una secuencia de k elementos de M en la que cada elemento aparece un número de veces menor o igual a su multiplicidad en M ( el número de repetición de un elemento ).

Permutaciones circulares

Las permutaciones, cuando se consideran como arreglos, a veces se denominan arreglos ordenados linealmente . Sin embargo, si los objetos están dispuestos de manera circular, este ordenamiento distinguido se debilita: no hay un "primer elemento" en el arreglo, ya que cualquier elemento puede considerarse como el inicio. Un arreglo de objetos distintos de manera circular se llama permutación circular . ^{[39] [e]} Estas pueden definirse formalmente como clases de equivalencia de permutaciones ordinarias de estos objetos, para la relación de equivalencia generada al mover el elemento final del arreglo lineal a su frente.

Dos permutaciones circulares son equivalentes si una puede rotarse dentro de la otra. Las siguientes cuatro permutaciones circulares de cuatro letras se consideran iguales.

 1 4 2 3 4 3 2 1 3 4 1 2 2 3 1 4

Las disposiciones circulares deben leerse en sentido antihorario, por lo que las dos siguientes no son equivalentes ya que ninguna rotación puede llevar una a la otra.

 1 1 4 3 3 4 2 2

¡ Hay ( n  – 1)! permutaciones circulares de un conjunto con n elementos.

Propiedades

El número de permutaciones de n objetos distintos es n !.

El número de n -permutaciones con k ciclos disjuntos es el número de Stirling sin signo del primer tipo , denotado como . ^[40] ${\displaystyle c(n,k)}$ ${\displaystyle [{\begin{smallmatrix}n\\k\end{smallmatrix}}]}$

Tipo de ciclo

Los ciclos (incluidos los puntos fijos) de una permutación de un conjunto con n elementos dividen ese conjunto; por lo tanto, las longitudes de estos ciclos forman una partición entera de n , que se denomina tipo de ciclo (o, a veces, estructura de ciclo o forma de ciclo ) de . Hay un "1" en el tipo de ciclo para cada punto fijo de , un "2" para cada transposición, y así sucesivamente. El tipo de ciclo de es ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$ ${\displaystyle (3,2,2,1).}$

Esto también se puede escribir en una forma más compacta como [1 ¹ 2 ² 3 ¹ ] . Más precisamente, la forma general es , donde son los números de ciclos de longitud respectiva. El número de permutaciones de un tipo de ciclo dado es ^[41] ${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$

${\displaystyle {\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}}$.

El número de tipos de ciclo de un conjunto con n elementos es igual al valor de la función de partición . ${\displaystyle p(n)}$

El polinomio de índice de ciclo de Polya es una función generadora que cuenta las permutaciones por su tipo de ciclo.

Conjugando permutaciones

En general, la composición de permutaciones escritas en notación de ciclo no sigue un patrón fácil de describir: los ciclos de la composición pueden ser diferentes de los que se están componiendo. Sin embargo, el tipo de ciclo se conserva en el caso especial de conjugar una permutación con otra permutación , lo que significa formar el producto . Aquí, es el conjugado de por y su notación de ciclo se puede obtener tomando la notación de ciclo para y aplicándola a todas las entradas en ella. ^[42] De ello se deduce que dos permutaciones son conjugadas exactamente cuando tienen el mismo tipo de ciclo. ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$

Orden de una permutación

El orden de una permutación es el entero positivo más pequeño m tal que . Es el mínimo común múltiplo de las longitudes de sus ciclos. Por ejemplo, el orden de es . ${\displaystyle \sigma }$ ${\displaystyle \sigma ^{m}=\mathrm {id} }$ ${\displaystyle \sigma =(152)(34)}$ ${\displaystyle {\text{lcm}}(3,2)=6}$

Paridad de una permutación

Toda permutación de un conjunto finito puede expresarse como el producto de transposiciones. ^[43] Aunque pueden existir muchas expresiones de este tipo para una permutación dada, todas ellas contienen un número par de transposiciones o un número impar de transposiciones. Por lo tanto, todas las permutaciones pueden clasificarse como pares o impares en función de este número.

Este resultado se puede extender para asignar un signo , escrito , a cada permutación. si es par y si es impar. Entonces, para dos permutaciones y ${\displaystyle \operatorname {sgn} \sigma }$ ${\displaystyle \operatorname {sgn} \sigma =+1}$ ${\displaystyle \sigma }$ ${\displaystyle \operatorname {sgn} \sigma =-1}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$

${\displaystyle \operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .}$

Resulta que ${\displaystyle \operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.}$

El signo de una permutación es igual al determinante de su matriz de permutación (abajo).

Representación matricial

Una matriz de permutación es una matriz n × n que tiene exactamente una entrada 1 en cada columna y en cada fila, y todas las demás entradas son 0. Hay varias formas de asignar una matriz de permutación a una permutación de {1, 2, ..., n }. Un enfoque natural es definir como la transformación lineal de la cual permuta la base estándar por , y definir como su matriz. Es decir, tiene su ^columna j igual al vector columna n × 1 : su entrada ( i , j ) es 1 si i = σ ( j ), y 0 en caso contrario. Dado que la composición de las aplicaciones lineales se describe mediante la multiplicación de matrices, se deduce que esta construcción es compatible con la composición de permutaciones: ${\displaystyle L_{\sigma }}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$ ${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$ ${\displaystyle M_{\sigma }}$ ${\displaystyle M_{\sigma }}$ ${\displaystyle \mathbf {e} _{\sigma (j)}}$

${\displaystyle M_{\sigma }M_{\tau }=M_{\sigma \tau }}$.

Por ejemplo, las permutaciones de una línea tienen producto y las matrices correspondientes son: ${\displaystyle \sigma =213,\ \tau =231}$ ${\displaystyle \sigma \tau =132}$ $${\displaystyle M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.}$$

Composición de permutaciones correspondiente a una multiplicación de matrices de permutación.

También es común en la literatura encontrar la convención inversa, donde una permutación σ se asocia a la matriz cuya entrada ( i , j ) es 1 si j = σ ( i ) y es 0 en caso contrario. En esta convención, las matrices de permutación se multiplican en el orden opuesto a las permutaciones, es decir, . En esta correspondencia, las matrices de permutación actúan en el lado derecho de los vectores fila estándar : . ${\displaystyle P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}}$ ${\displaystyle P_{\sigma }P_{\tau }=P_{\tau \sigma }}$ ${\displaystyle 1\times n}$ ${\displaystyle ({\bf {e}}_{i})^{T}}$ ${\displaystyle ({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}}$

La tabla de Cayley de la derecha muestra estas matrices para permutaciones de 3 elementos.

Permutaciones de conjuntos totalmente ordenados

En algunas aplicaciones, los elementos del conjunto que se está permutando se compararán entre sí. Esto requiere que el conjunto S tenga un orden total tal que se puedan comparar dos elementos cualesquiera. El conjunto {1, 2, ..., n } con la relación ≤ habitual es el conjunto que se utiliza con más frecuencia en estas aplicaciones.

Varias propiedades de una permutación están directamente relacionadas con el ordenamiento total de S, considerando la permutación escrita en notación de una línea como una secuencia . ${\displaystyle \sigma =\sigma (1)\sigma (2)\cdots \sigma (n)}$

Ascensos, descensos, carreras, superaciones, récords

Un ascenso de una permutación  σ de n es cualquier posición i  <  n donde el valor siguiente es mayor que el actual. Es decir, i es un ascenso si . Por ejemplo, la permutación 3452167 tiene ascensos (en las posiciones) 1, 2, 5 y 6. ${\displaystyle \sigma (i)<\sigma (i{+}1)}$

De manera similar, un descenso es una posición i  <  n con , por lo que cada i con es un ascenso o un descenso. ${\displaystyle \sigma (i)>\sigma (i{+}1)}$ ${\displaystyle 1\leq i<n}$

Una sucesión ascendente de una permutación es una subsecuencia creciente contigua no vacía que no puede extenderse en ninguno de sus extremos; corresponde a una secuencia máxima de ascensos sucesivos (éstos pueden estar vacíos: entre dos descensos sucesivos hay todavía una sucesión ascendente de longitud 1). Por el contrario, una subsecuencia creciente de una permutación no es necesariamente contigua: es una sucesión creciente obtenida omitiendo algunos de los valores de la notación unifilar. Por ejemplo, la permutación 2453167 tiene las sucesiones ascendentes 245, 3 y 167, mientras que tiene una subsecuencia creciente 2367.

Si una permutación tiene k  − 1 descensos, entonces debe ser la unión de k ejecuciones ascendentes. ^[44]

El número de permutaciones de n con k ascensos es (por definición) el número de Euler ; éste es también el número de permutaciones de n con k descensos. Sin embargo, algunos autores definen el número de Euler como el número de permutaciones con k ascensos, lo que corresponde a k − 1 descensos. ^[45] ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$ ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$

Una excedencia de una permutación σ ₁ σ ₂ ... σ _n es un índice j tal que σ _j > j . Si la desigualdad no es estricta (es decir, σ _j ≥ j ), entonces j se denomina excedencia débil . El número de n -permutaciones con k excedencias coincide con el número de n -permutaciones con k descensos. ^[46]

Un registro o máximo de izquierda a derecha de una permutación σ es un elemento i tal que σ ( j ) < σ ( i ) para todo j < i .

Lema de transición de Foata

La biyección fundamental de Foata transforma una permutación con una forma de ciclo canónico dada en la permutación cuya notación de una línea tiene la misma secuencia de elementos con los paréntesis eliminados. ^{[27] [47]} Por ejemplo: ${\displaystyle \sigma }$ ${\displaystyle f(\sigma )={\hat {\sigma }}}$

${\displaystyle \sigma =(513)(6)(827)(94)={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}},}$ ${\displaystyle {\hat {\sigma }}=513682794={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&1&3&6&8&2&7&9&4\end{pmatrix}}.}$

Aquí el primer elemento de cada ciclo canónico de se convierte en un registro (máximo de izquierda a derecha) de . Dado , se pueden encontrar sus registros e insertar paréntesis para construir la transformación inversa . Subrayando los registros en el ejemplo anterior: , lo que permite la reconstrucción de los ciclos de . ${\displaystyle \sigma }$ ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$ ${\displaystyle {\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4}$ ${\displaystyle \sigma }$

La siguiente tabla muestra y para las seis permutaciones de S = {1, 2, 3}, con el texto en negrita en cada lado que muestra la notación utilizada en la biyección: notación de una línea para y notación de ciclo canónico para . ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma }$ ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma }$

Como primer corolario, el número de n -permutaciones con exactamente k registros es igual al número de n -permutaciones con exactamente k ciclos: este último número es el número de Stirling sin signo de primera especie , . Además, la aplicación de Foata lleva una n -permutación con k excedencias débiles a una n -permutación con k − 1 ascensos. ^[47] Por ejemplo, (2)(31) = 321 tiene k = 2 excedencias débiles (en el índice 1 y 2), mientras que f (321) = 231 tiene k − 1 = 1 ascenso (en el índice 1; es decir, de 2 a 3). ${\displaystyle c(n,k)}$

Inversiones

En el rompecabezas 15 el objetivo es conseguir que los cuadrados estén en orden ascendente. Las posiciones iniciales que tienen un número impar de inversiones son imposibles de resolver. ^[48]

Una inversión de una permutación  σ es un par ( i , j ) de posiciones donde las entradas de una permutación están en el orden opuesto: y . ^[49] Por lo tanto, un descenso es una inversión en dos posiciones adyacentes. Por ejemplo, σ = 23154 tiene ( i , j ) = (1, 3), (2, 3) y (4, 5), donde ( σ ( i ), σ ( j )) = (2, 1), (3, 1) y (5, 4). ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$

A veces, una inversión se define como el par de valores ( σ ( i ), σ ( j )); esto no hace ninguna diferencia para el número de inversiones, y el par inverso ( σ ( j ), σ ( i )) es una inversión en el sentido anterior para la permutación inversa σ ⁻¹ .

El número de inversiones es una medida importante del grado en que las entradas de una permutación están fuera de orden; es el mismo para σ y para σ ⁻¹ . Ordenar una permutación con k inversiones (es decir, transformarla en la permutación identidad), aplicando sucesivamente (multiplicación por la derecha por) transposiciones adyacentes , es siempre posible y requiere una secuencia de k operaciones de este tipo. Además, cualquier elección razonable para las transposiciones adyacentes funcionará: basta con elegir en cada paso una transposición de i e i + 1 donde i es un descenso de la permutación modificada hasta ahora (de modo que la transposición eliminará este descenso particular, aunque podría crear otros descensos). Esto es así porque la aplicación de dicha transposición reduce el número de inversiones en 1; mientras este número no sea cero, la permutación no es la identidad, por lo que tiene al menos un descenso. El ordenamiento por burbuja y el ordenamiento por inserción pueden interpretarse como casos particulares de este procedimiento para ordenar una secuencia. Por cierto, este procedimiento demuestra que cualquier permutación σ puede escribirse como un producto de transposiciones adyacentes; para ello, se puede simplemente invertir cualquier secuencia de tales transposiciones que transforme σ en la identidad. De hecho, al enumerar todas las secuencias de transposiciones adyacentes que transformarían σ en la identidad, se obtiene (después de la inversión) una lista completa de todas las expresiones de longitud mínima que escriben σ como un producto de transposiciones adyacentes.

El número de permutaciones de n con k inversiones se expresa mediante un número mahoniano . ^[50] Este es el coeficiente de en la expansión del producto ${\displaystyle q^{k}}$

$${\displaystyle [n]_{q}!=\prod _{m=1}^{n}\sum _{i=0}^{m-1}q^{i}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right),}$$

La notación denota el factorial q . Esta expansión aparece comúnmente en el estudio de los collares . ${\displaystyle [n]_{q}!}$

Sea tal que y . En este caso, digamos que el peso de la inversión es . Kobayashi (2011) demostró la fórmula de enumeración ${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$ ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle \sigma (i)-\sigma (j)}$ $${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

donde denota el orden de Bruhat en los grupos simétricos . Este orden parcial graduado aparece a menudo en el contexto de los grupos de Coxeter . ${\displaystyle \leq }$

Permutaciones en computación

Permutaciones de numeración

Una forma de representar permutaciones de n cosas es mediante un entero N con 0 ≤  N  <  n !, siempre que se proporcionen métodos convenientes para convertir entre el número y la representación de una permutación como una disposición ordenada (secuencia). Esto proporciona la representación más compacta de permutaciones arbitrarias, y en informática es particularmente atractivo cuando n es lo suficientemente pequeño como para que N pueda almacenarse en una palabra de máquina; para palabras de 32 bits esto significa n  ≤ 12, y para palabras de 64 bits esto significa n  ≤ 20. La conversión se puede realizar mediante la forma intermedia de una secuencia de números d _n , d _{n −1} , ..., d ₂ , d ₁ , donde d _i es un entero no negativo menor que i (se puede omitir d ₁ , ya que siempre es 0, pero su presencia hace que la conversión posterior a una permutación sea más fácil de describir). El primer paso es simplemente expresar N en el sistema de numeración factorial , que es simplemente una representación particular de radix mixto , donde, para números menores que n !, las bases (valores de posición o factores de multiplicación) para dígitos sucesivos son ( n − 1)! , ( n − 2)! , ..., 2!, 1!. El segundo paso interpreta esta secuencia como un código de Lehmer o (casi equivalentemente) como una tabla de inversión.

En el código de Lehmer para una permutación  σ , el número d _n representa la elección hecha para el primer término  σ ₁ , el número d _{n −1} representa la elección hecha para el segundo término σ _{2 entre los} n − 1 elementos restantes del conjunto, y así sucesivamente. Más precisamente, cada d _{n +1− i} da el número de elementos restantes estrictamente menores que el término σ _i . Dado que esos elementos restantes están destinados a aparecer como algún término posterior σ _j , el dígito d _{n +1− i} cuenta las inversiones ( i , j ) que involucran a i como índice menor (el número de valores j para los cuales i  <  j y σ _i  >  σ _j ). La tabla de inversión para  σ es bastante similar, pero aquí d _{n +1− k} cuenta el número de inversiones ( i , j ) donde k  =  σ _j ocurre como el menor de los dos valores que aparecen en orden invertido. ^[51]

Ambas codificaciones pueden visualizarse mediante un diagrama de Rothe n  por  n ^[52] (nombrado en honor a Heinrich August Rothe ) en el que los puntos en ( i , σ _i ) marcan las entradas de la permutación, y una cruz en ( i , σ _j ) marca la inversión ( i , j ); por la definición de inversiones, una cruz aparece en cualquier cuadrado que venga tanto antes del punto ( j , σ _j ) en su columna, como antes del punto ( i , σ _i ) en su fila. El código de Lehmer enumera los números de cruces en filas sucesivas, mientras que la tabla de inversión enumera los números de cruces en columnas sucesivas; es simplemente el código de Lehmer para la permutación inversa, y viceversa.

Para convertir efectivamente un código de Lehmer d _n , d _{n −1} , ..., d ₂ , d ₁ en una permutación de un conjunto ordenado S , se puede empezar con una lista de los elementos de S en orden creciente, y para i aumentando de 1 a n establecer σ _i en el elemento de la lista que está precedido por d _{n +1− i} otros, y eliminar ese elemento de la lista. Para convertir una tabla de inversión d _n , d _{n −1} , ..., d ₂ , d ₁ en la permutación correspondiente, se pueden recorrer los números de d ₁ a d _n mientras se insertan los elementos de S de mayor a menor en una secuencia inicialmente vacía; en el paso que usa el número d de la tabla de inversión, el elemento de S insertado en la secuencia en el punto donde está precedido por d elementos ya presentes. Alternativamente, se podrían procesar los números de la tabla de inversión y los elementos de S en el orden opuesto, comenzando con una fila de n espacios vacíos y en cada paso colocar el elemento de S en el espacio vacío que está precedido por otros d espacios vacíos.

La conversión de números naturales sucesivos al sistema de numeración factorial produce esas secuencias en orden lexicográfico (como es el caso con cualquier sistema de numeración de base mixta), y su posterior conversión a permutaciones preserva el orden lexicográfico, siempre que se utilice la interpretación del código de Lehmer (usando tablas de inversión, se obtiene un orden diferente, donde se comienza comparando permutaciones por el lugar de sus entradas 1 en lugar de por el valor de sus primeras entradas). La suma de los números en la representación del sistema de numeración factorial da el número de inversiones de la permutación, y la paridad de esa suma da la firma de la permutación. Además, las posiciones de los ceros en la tabla de inversión dan los valores de los máximos de izquierda a derecha de la permutación (en el ejemplo 6, 8, 9) mientras que las posiciones de los ceros en el código de Lehmer son las posiciones de los mínimos de derecha a izquierda (en las posiciones del ejemplo los 4, 8, 9 de los valores 1, 2, 5); Esto permite calcular la distribución de tales extremos entre todas las permutaciones. Una permutación con código de Lehmer d _n , d _{n −1} , ..., d ₂ , d ₁ tiene un ascenso n − i si y solo si d _i ≥ d _{i +1} .

Algoritmos para generar permutaciones

En computación puede ser necesario generar permutaciones de una secuencia dada de valores. Los métodos más adecuados para ello dependen de si se quieren algunas permutaciones elegidas aleatoriamente o todas las permutaciones y, en este último caso, de si se requiere un orden específico. Otra cuestión es si se debe tener en cuenta la posible igualdad entre las entradas de la secuencia dada; en tal caso, se deben generar únicamente permutaciones multiconjunto distintas de la secuencia.

Una forma obvia de generar permutaciones de n es generar valores para el código de Lehmer (posiblemente usando la representación del sistema numérico factorial de números enteros hasta n !), y convertirlos en las permutaciones correspondientes. Sin embargo, el último paso, aunque sencillo, es difícil de implementar de manera eficiente, porque requiere n operaciones de selección de una secuencia y eliminación de la misma, en una posición arbitraria; de las representaciones obvias de la secuencia como una matriz o una lista enlazada , ambas requieren (por diferentes razones) alrededor de n ² /4 operaciones para realizar la conversión. Como n probablemente sea bastante pequeño (especialmente si se necesita la generación de todas las permutaciones), eso no es un gran problema, pero resulta que tanto para la generación aleatoria como para la sistemática hay alternativas simples que funcionan considerablemente mejor. Por esta razón, no parece útil, aunque ciertamente posible, emplear una estructura de datos especial que permita realizar la conversión del código de Lehmer a la permutación en tiempo O ( n log n ) .

Generación aleatoria de permutaciones

Para generar permutaciones aleatorias de una secuencia dada de n valores, no hay diferencia si se aplica una permutación de n seleccionada aleatoriamente a la secuencia, o se elige un elemento aleatorio del conjunto de permutaciones distintas (multiconjunto) de la secuencia. Esto se debe a que, aunque en el caso de valores repetidos puede haber muchas permutaciones distintas de n que resulten en la misma secuencia permutada, el número de dichas permutaciones es el mismo para cada resultado posible. A diferencia de la generación sistemática, que se vuelve inviable para n grandes debido al crecimiento del número n !, no hay razón para suponer que n será pequeño para la generación aleatoria.

La idea básica para generar una permutación aleatoria es generar aleatoriamente una de las n ! secuencias de números enteros d ₁ , d ₂ ,..., d _n que satisfagan 0 ≤ d _i < i (ya que d ₁ es siempre cero, se puede omitir) y convertirla en una permutación mediante una correspondencia biyectiva . Para la última correspondencia, se podría interpretar la secuencia (inversa) como un código de Lehmer, y esto da un método de generación publicado por primera vez en 1938 por Ronald Fisher y Frank Yates . ^[53] Si bien en ese momento la implementación en computadora no era un problema, este método sufre la dificultad esbozada anteriormente para convertir de código de Lehmer a permutación de manera eficiente. Esto se puede remediar utilizando una correspondencia biyectiva diferente: después de utilizar d _i para seleccionar un elemento entre los i elementos restantes de la secuencia (para valores decrecientes de i ), en lugar de eliminar el elemento y compactar la secuencia desplazando más elementos un lugar hacia abajo, se intercambia el elemento con el elemento restante final. De este modo, los elementos que quedan por seleccionar forman un rango consecutivo en cada punto del tiempo, aunque no aparezcan en el mismo orden en que lo hicieron en la secuencia original. La asignación de una secuencia de números enteros a permutaciones es algo complicada, pero se puede observar que produce cada permutación exactamente de una manera, mediante una inducción inmediata . Cuando el elemento seleccionado resulta ser el último elemento restante, se puede omitir la operación de intercambio. Esto no ocurre con la suficiente frecuencia como para justificar la prueba de la condición, pero el elemento final debe incluirse entre los candidatos de la selección, para garantizar que se puedan generar todas las permutaciones.

El algoritmo resultante para generar una permutación aleatoria de se puede describir de la siguiente manera en pseudocódigo :a[0], a[1], ..., a[n − 1]

para  i  desde  n  hasta 2, haga  d i ← elemento aleatorio de { 0, ..., i − 1 } intercambie  a [ d i ] y a [ i − 1]

Esto se puede combinar con la inicialización de la matriz de la siguiente maneraa[i] = i

para  i  de 0 a  n −1 do  d i +1 ← elemento aleatorio de { 0, ..., i } a [ i ] ← a [ d i +1 ] a [ d i +1 ] ← i

Si d _{i +1} = i , la primera asignación copiará un valor no inicializado, pero la segunda lo sobrescribirá con el valor correcto i .

Sin embargo, Fisher-Yates no es el algoritmo más rápido para generar una permutación, porque Fisher-Yates es esencialmente un algoritmo secuencial y los procedimientos de "dividir y vencer" pueden lograr el mismo resultado en paralelo. ^[54]

Generación en orden lexicográfico

Existen muchas maneras de generar sistemáticamente todas las permutaciones de una secuencia dada. ^[55] Un algoritmo clásico, simple y flexible se basa en encontrar la siguiente permutación en orden lexicográfico , si existe. Puede manejar valores repetidos, para cuyo caso genera cada permutación multiconjunto distinta una vez. Incluso para permutaciones ordinarias es significativamente más eficiente que generar valores para el código de Lehmer en orden lexicográfico (posiblemente usando el sistema de numeración factorial ) y convertirlos en permutaciones. Comienza ordenando la secuencia en orden (débilmente) creciente (lo que da su permutación lexicográficamente mínima), y luego repite avanzando a la siguiente permutación siempre que se encuentre una. El método se remonta a Narayana Pandita en la India del siglo XIV, y ha sido redescubierto con frecuencia. ^[56]

El siguiente algoritmo genera lexicográficamente la siguiente permutación después de una permutación dada. Cambia la permutación dada en el lugar.

1. Encuentre el mayor índice k tal que a [ k ] < a [ k + 1] . Si no existe dicho índice, la permutación es la última permutación.
2. Encuentra el mayor índice l mayor que k tal que a [ k ] < a [ l ] .
3. Intercambie el valor de a [ k ] con el de a [ l ].
4. Invierta la secuencia desde a [ k + 1] hasta el elemento final a [ n ] inclusive.

Por ejemplo, dada la secuencia [1, 2, 3, 4] (que está en orden creciente), y dado que el índice está basado en cero , los pasos son los siguientes:

1. Índice k = 2, porque 3 se coloca en un índice que satisface la condición de ser el índice más grande que aún es menor que a [ k + 1] que es 4.
2. Índice l = 3, porque 4 es el único valor en la secuencia que es mayor que 3 para satisfacer la condición a [ k ] < a [ l ].
3. Los valores de a [2] y a [3] se intercambian para formar la nueva secuencia [1, 2, 4, 3].
4. La secuencia que sigue al k -índice a [2] hasta el elemento final se invierte. Como sólo hay un valor después de este índice (el 3), la secuencia permanece inalterada en este caso. Por lo tanto, el sucesor lexicográfico del estado inicial se permuta: [1, 2, 4, 3].

Siguiendo este algoritmo, la siguiente permutación lexicográfica será [1, 3, 2, 4], y la permutación número 24 será [4, 3, 2, 1], en cuyo punto a [ k ] < a [ k + 1] no existe, lo que indica que esta es la última permutación.

Este método utiliza aproximadamente 3 comparaciones y 1,5 intercambios por permutación, amortizados en toda la secuencia, sin contar la clasificación inicial. ^[57]

Generación con cambios mínimos

Una alternativa al algoritmo anterior, el algoritmo Steinhaus–Johnson–Trotter , genera un ordenamiento de todas las permutaciones de una secuencia dada con la propiedad de que dos permutaciones consecutivas cualesquiera en su salida difieren intercambiando dos valores adyacentes. Este ordenamiento de las permutaciones era conocido por los campaneros ingleses del siglo XVII, entre quienes se lo conocía como "cambios simples". Una ventaja de este método es que la pequeña cantidad de cambio de una permutación a la siguiente permite que el método se implemente en tiempo constante por permutación. El mismo también puede generar fácilmente el subconjunto de permutaciones pares, nuevamente en tiempo constante por permutación, omitiendo cada otra permutación de salida. ^[56]

Una alternativa a Steinhaus–Johnson–Trotter es el algoritmo de Heap , ^[58] considerado por Robert Sedgewick en 1977 como el algoritmo más rápido para generar permutaciones en aplicaciones. ^[55]

La siguiente figura muestra el resultado de los tres algoritmos mencionados anteriormente para generar todas las permutaciones de longitud , y de seis algoritmos adicionales descritos en la literatura. ${\displaystyle n=4}$

Ordenación de todas las permutaciones de longitud generadas por diferentes algoritmos. Las permutaciones están codificadas por colores, donde ${\displaystyle n=4}$  1 ,  2 ,  3 ,  4 . ^[59]

1. Ordenamiento lexicográfico;
2. Algoritmo de Steinhaus-Johnson-Trotter ;
3. Algoritmo de Heap ;
4. Algoritmo de transposición de estrellas de Ehrlich: ^[56] en cada paso, la primera entrada de la permutación se intercambia con una entrada posterior;
5. Algoritmo de inversión de prefijo de Zaks: ^[60] en cada paso, se invierte un prefijo de la permutación actual para obtener la siguiente permutación;
6. Algoritmo de Sawada-Williams: ^[61] cada permutación difiere de la anterior ya sea por un desplazamiento cíclico a la izquierda de una posición, o por un intercambio de las dos primeras entradas;
7. Algoritmo de Corbett: ^[62] cada permutación difiere de la anterior por un desplazamiento cíclico hacia la izquierda de algún prefijo en una posición;
8. Ordenamiento de pista única: ^[63] cada columna es un desplazamiento cíclico de las otras columnas;
9. Código Gray de pista única: ^[63] cada columna es un desplazamiento cíclico de las otras columnas, además dos permutaciones consecutivas difieren solo en una o dos transposiciones.
10. Algoritmo de generación de permutaciones anidadas en pasos conectados a los subgrupos anidados . Cada permutación se obtiene a partir de la anterior mediante una multiplicación por transposición hacia la izquierda. El algoritmo está conectado al sistema_de_números_factoriales del índice. ${\displaystyle S_{k}\subset S_{k+1}}$

Generación de permutaciones en pasos de intercambio anidados

Aquí se describe una secuencia explícita de intercambios (transposiciones, 2-ciclos ), en la que cada intercambio aplicado (a la izquierda) a la cadena anterior proporciona una nueva permutación, de modo que se pueden recuperar todas las permutaciones, cada una solo una vez. ^[64] Este procedimiento de conteo/generación tiene una estructura adicional (llamémosla anidada), ya que se da en pasos: después de recuperar completamente , continuar recuperando por cosets de en , eligiendo apropiadamente los representantes de coset que se describirán a continuación. Tenga en cuenta que, dado que cada uno se genera secuencialmente, hay un último elemento . Entonces, después de generar por intercambios, la siguiente permutación en tiene que ser para algún . Luego, se repiten todos los intercambios que se generaron , generando todo el coset , llegando a la última permutación en ese coset ; el siguiente intercambio tiene que mover la permutación a representante de otro coset . ${\displaystyle (pq)}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}\backslash S_{k-1}}$ ${\displaystyle S_{k-1}\tau _{i}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}}$ ${\displaystyle \tau _{i}}$ ${\displaystyle S_{m}}$ ${\displaystyle \lambda _{m}\in S_{m}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}\backslash S_{k-1}}$ ${\displaystyle \tau _{1}=(p_{1}k)\lambda _{k-1}}$ ${\displaystyle 1\leq p_{1}<k}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k-1}\tau _{1}}$ ${\displaystyle \lambda _{k-1}\tau _{1}}$ ${\displaystyle \tau _{2}=(p_{2}k)\lambda _{k-1}\tau _{1}}$

Continuando de la misma manera, se obtienen representantes de clases laterales para las clases laterales de en ; el conjunto ordenado ( ) se llama el conjunto de comienzos de clases laterales. Dos de estos representantes están en la misma clase lateral si y solo si , es decir, . En conclusión, las permutaciones son todas representantes de clases laterales distintas si y solo si para cualquier , (sin condición de repetición). En particular, para que todas las permutaciones generadas sean distintas no es necesario que los valores sean distintos. En el proceso, se obtiene eso y esto proporciona el procedimiento de recursión. ${\displaystyle \tau _{j}=(p_{j}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}}$ ${\displaystyle (p_{1},\ldots ,p_{k-1})}$ ${\displaystyle 0\leq p_{i}<k}$ ${\displaystyle \tau _{j}(\tau _{i})^{-1}=(p_{j}k)\lambda _{k-1}(p_{j-1}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i+1}k)=\varkappa _{ij}\in S_{k-1}}$ ${\displaystyle \varkappa _{ij}(k)=k}$ ${\displaystyle \tau _{i}\in S_{k}-S_{k-1}}$ ${\displaystyle k>j>i\geq 1}$ ${\displaystyle (\lambda _{k-1})^{j-i}p_{i}\neq p_{j}}$ ${\displaystyle p_{i}}$ ${\displaystyle \lambda _{k}=\lambda _{k-1}(p_{k-1}k)\lambda _{k-1}(p_{k-2}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}}$

EJEMPLOS: obviamente, para uno tiene ; para construir solo hay dos posibilidades para los comienzos de las clases laterales que satisfacen la condición de no repetición; la elección lleva a . Para continuar generando, uno necesita comienzos de clases laterales apropiados (que satisfacen la condición de no repetición): hay una elección conveniente: , que lleva a . Entonces, para construir una elección conveniente para los comienzos de las clases laterales (que satisfacen la condición de no repetición) es , que lleva a . ${\displaystyle \lambda _{2}}$ ${\displaystyle \lambda _{2}=(12)}$ ${\displaystyle \lambda _{3}}$ ${\displaystyle p_{1}=p_{2}=1}$ ${\displaystyle \lambda _{3}=\lambda _{2}(13)\lambda _{2}(13)\lambda _{2}=(13)}$ ${\displaystyle S_{4}}$ ${\displaystyle p_{1}=1,p_{2}=2,p_{3}=3}$ ${\displaystyle \lambda _{4}=(13)(1234)(13)=(1432)}$ ${\displaystyle \lambda _{5}}$ ${\displaystyle p_{1}=p_{2}=p_{3}=p_{4}=1}$ ${\displaystyle \lambda _{5}=(15)}$

A partir de los ejemplos anteriores, se puede ir inductivamente a un nivel superior de una manera similar, eligiendo comienzos de coset de en , de la siguiente manera: para pares, eligiendo todos los comienzos de coset iguales a 1 y para impares, eligiendo comienzos de coset iguales a . Con tales elecciones, la "última" permutación es para impares y para pares ( ). Usando estas fórmulas explícitas, uno puede calcular fácilmente la permutación de cierto índice en los pasos de conteo/generación con un cálculo mínimo. Para esto, es útil escribir el índice en base factorial. Por ejemplo, la permutación para el índice es: , dando como resultado finalmente, . ${\displaystyle k}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{k+1}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (1,2,\dots ,k)}$ ${\displaystyle \lambda _{k}=(1k)}$ ${\displaystyle k}$ ${\displaystyle \lambda _{k}=(1k_{-})(12\cdots k)(1k_{-})}$ ${\displaystyle k}$ ${\displaystyle k_{-}=k-1}$ ${\displaystyle 699=5(5!)+4(4!)+1(2!)+1(1!)}$ ${\displaystyle \sigma =\lambda _{2}(13)\lambda _{2}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(56)\lambda _{5}(46)\lambda _{5}(36)\lambda _{5}(26)\lambda _{5}(16)\lambda _{5}=}$ ${\displaystyle \lambda _{2}(13)\lambda _{2}((15)\lambda _{4})^{4}(\lambda _{5})^{-1}\lambda _{6}=(23)(14325)^{-1}(15)(15)(123456)(15)=}$ ${\displaystyle (23)(15234)(123456)(15)}$ ${\displaystyle \sigma =(1653)(24)}$

Como la multiplicación por permutación de intercambio requiere poco tiempo de cálculo y cada nueva permutación generada requiere solo una de esas multiplicaciones de intercambio, este procedimiento de generación es bastante eficiente. Además, como hay una fórmula simple, tener la última permutación en cada una puede ahorrar incluso más tiempo para ir directamente a una permutación con cierto índice en menos pasos de lo esperado, ya que se puede hacer en bloques de subgrupos en lugar de intercambio por intercambio. ${\displaystyle S_{k}}$

Aplicaciones

Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212^[65]). Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the permutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.^[66]

See also

• Mathematics portal

• Alternating permutation
• Convolution
• Cyclic order
• Even and odd permutations
• Josephus permutation
• Levi-Civita symbol
• List of permutation topics
• Major index
• Permutation category
• Permutation group
• Permutation pattern
• Permutation representation (symmetric group)
• Probability
• Rencontres numbers
• Sorting network
• Substitution cipher
• Superpattern
• Superpermutation
• Twelvefold way
• Weak order of permutations

Notes

1. 1 is frequently used to represent the identity element in a non-commutative group
2. The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.
3. More precisely, variations without repetition. The term is still common in other languages and appears in modern English most often in translation.
4. The natural order in this example is the order of the letters in the original word.
5. In older texts circular permutation was sometimes used as a synonym for cyclic permutation, but this is no longer done. See Carmichael (1956, p. 7)

References

1. Webster (1969)
2. McCoy (1968, p. 152)
3. Nering (1970, p. 86)
4. Heath, Thomas Little (1981). A History of Greek Mathematics. New York: Dover Publications. ISBN 0-486-24073-8. OCLC 7703465.
5. Broemeling, Lyle D. (1 November 2011). "An Account of Early Statistical Inference in Arab Cryptology". The American Statistician. 65 (4): 255–257. doi:10.1198/tas.2011.10191. S2CID 123537702.
6. Biggs, N. L. (1979). "The Roots of Combinatorics". Historia Math. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
7. Stedman 1677, p. 4.
8. Stedman 1677, p. 5.
9. Stedman 1677, pp. 6–7.
10. Stedman 1677, p. 8.
11. Stedman 1677, pp. 13–18.
12. Rejewski, Marian (1980). "An application of the theory of permutations in breaking the Enigma cipher". Applicationes Mathematicae. 16 (4): 543–559. doi:10.4064/am-16-4-543-559. ISSN 1233-7234.
13. Cash, David (2019). "CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma" (PDF).
14. Scheinerman, Edward A. (March 5, 2012). "Chapter 5: Functions". Mathematics: A Discrete Introduction (3rd ed.). Cengage Learning. p. 188. ISBN 978-0840049421. Archived from the original on February 5, 2020. Retrieved February 5, 2020. It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.
15. Rotman 2002, p. 41
16. Bogart 1990, p. 487
17. Cameron 1994, p. 29, footnote 3.
18. Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). The Symmetries of Things. A K Peters. p. 179. A permutation---say, of the names of a number of people---can be thought of as moving either the names or the people. The alias viewpoint regards the permutation as assigning a new name or alias to each person (from the Latin alias = otherwise). Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin alibi = in another place.)
19. "Permutation notation - Wikiversity". en.wikiversity.org. Retrieved 2024-08-04.
20. Cauchy, A. L. (January 1815). "Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme" [Memoir on the number of values which a function can acquire when one permutes within it, in all possible ways, the variables which it contains]. Journal de l'École polytechnique (in French). 10: 1–28. See p. 4.
    • English translation
21. Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, p. 94, ISBN 9780486458687, Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.
22. Bogart 1990, p. 17
23. Gerstein 1987, p. 217
24. Aigner, Martin (2007). A Course in Enumeration. Springer GTM 238. pp. 24–25. ISBN 978-3-540-39035-0.
25. Hall 1959, p. 54
26. Bona 2012, p.87 [The book has a typo/error here, as it gives (45) instead of (54).]
27. Stanley, Richard P. (2012). Enumerative Combinatorics: Volume I, Second Edition. Cambridge University Press. p. 30, Prop 1.3.1. ISBN 978-1-107-01542-5.
28. Kitaev, Sergey (2011). Patterns in Permutations and Words. Springer Science & Business Media. p. 119. ISBN 978-3-642-17333-2.
29. Biggs, Norman L.; White, A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 978-0-521-22287-7.
30. Dixon, John D.; Mortimer, Brian (1996). Permutation Groups. Springer. ISBN 978-0-387-94599-6.
31. Cameron, Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 978-0-521-65302-2.
32. Jerrum, M. (1986). "A compact representation of permutation groups". J. Algorithms. 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6. S2CID 18896625.
33. "Combinations and Permutations". www.mathsisfun.com. Retrieved 2020-09-10.
34. Weisstein, Eric W. "Permutation". mathworld.wolfram.com. Retrieved 2020-09-10.
35. Uspensky 1937, p. 18
36. Charalambides, Ch A. (2002). Enumerative Combinatorics. CRC Press. p. 42. ISBN 978-1-58488-290-9.
37. Brualdi 2010, p. 46, Theorem 2.4.2
38. Brualdi 2010, p. 47
39. Brualdi 2010, p. 39
40. Bona 2012, pp. 97–103.
41. Sagan, Bruce (2001), The Symmetric Group (2 ed.), Springer, p. 3
42. Humphreys 1996, p. 84.
43. Hall 1959, p. 60
44. Bóna 2004, p. 4f.
45. Bona 2012, pp. 4–5.
46. Bona 2012, p. 25.
47. Bona 2012, pp. 109–110.
48. Slocum, Jerry; Weisstein, Eric W. (1999). "15 – puzzle". MathWorld. Wolfram Research, Inc. Retrieved October 4, 2014.
49. Bóna 2004, p. 43.
50. Bóna 2004, pp. 43ff.
51. Knuth 1973, p. 12.
52. H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263–305. Cited in Knuth 1973, p. 14
53. Fisher, R.A.; Yates, F. (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27. OCLC 14222135.
54. Bacher, A.; Bodini, O.; Hwang, H.K.; Tsai, T.H. (2017). "Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation" (ACM Trans. Algorithms 13(2): 24:1–24:43 ed.). pp. 24–43.
55. Sedgewick, R (1977). "Permutation generation methods" (PDF). Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692. S2CID 12139332. Archived (PDF) from the original on 2008-02-21.
56. Knuth 2005, pp. 1–26.
57. "std::next_permutation". cppreference.com. 4 December 2017. Retrieved 31 March 2018.
58. Heap, B. R. (1963). "Permutations by Interchanges". The Computer Journal. 6 (3): 293–298. doi:10.1093/comjnl/6.3.293.
59. Mütze, Torsten; Sawada, Joe; Williams, Aaron. "Generate permutations". Combinatorial Object Server. Retrieved May 29, 2019.
60. Zaks, S. (1984). "A new algorithm for generation of permutations". BIT Numerical Mathematics. 24 (2): 196–204. doi:10.1007/BF01937486. S2CID 30234652.
61. Sawada, Joe; Williams, Aaron (2018). "A Hamilton path for the sigma-tau problem". Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. New Orleans, Louisiana: Society for Industrial and Applied Mathematics (SIAM). pp. 568–575. doi:10.1137/1.9781611975031.37.
62. Corbett, P. F. (1992). "Rotator graphs: An efficient topology for point-to-point multiprocessor networks". IEEE Transactions on Parallel and Distributed Systems. 3 (5): 622–626. doi:10.1109/71.159045.
63. Arndt, Jörg (2011). Matters Computational. Ideas, Algorithms, Source Code. Springer. doi:10.1007/978-3-642-14764-7. ISBN 978-3-642-14763-0.
64. Popp, O.T. (2002). Quickly Handling Big Permutations. priv. comm.
65. "3GPP TS 36.212".
66. Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). "Unique permutation hashing". Theoretical Computer Science. 475: 59–65. doi:10.1016/j.tcs.2012.12.047.

Bibliography

• Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
• Bóna, Miklós (2004), Combinatorics of Permutations, Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Bona, Miklos (2012), Combinatorics of Permutations (2nd ed.), CRC Press, ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
• Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
• Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
• Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
• Hall, Marshall Jr. (1959), The Theory of Groups, MacMillan
• Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, vol. 3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
• Knuth, Donald (2005), Generating All Tuples and Permutations, The Art of Computer Programming, vol. 4, Addison–Wesley, ISBN 978-0-201-85393-3 Fascicle 2, first printing.
• McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68015225
• Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: Wiley, LCCN 76091646
• Rotman, Joseph J. (2002), Álgebra moderna avanzada , Prentice-Hall, ISBN 978-0-13-087868-7
• Stedman, Fabian (1677), Campanalogia , Londres El editor aparece como "WS", que puede haber sido William Smith, posiblemente actuando como agente de la Sociedad de Jóvenes Universitarios , a cuya sociedad está dirigida la "Dedicatoria". En las citas, la "S" larga original ha sido reemplazada por una "s" corta moderna.
• Uspensky, James (1937), Introducción a la probabilidad matemática, McGraw-Hill
• Séptimo diccionario colegiado nuevo de Webster , Springfield: G. & C. Merriam Company , 1969

Lectura adicional

• Biggs, Norman L. (2002), Matemáticas discretas (2.ª ed.), Oxford University Press, ISBN 978-0-19-850717-8
• Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlín, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2El enlace lleva a una versión revisada (en LaTeX) y reescrita de forma gratuita del texto publicado originalmente por Springer-Verlag.
• Knuth, Donald (1998), Ordenación y búsqueda , The Art of Computer Programming, vol. 3 (segunda edición), Addison–Wesley, ISBN 978-0-201-89685-5Sección 5.1: Propiedades combinatorias de permutaciones, págs. 11–72.
• Sedgewick, Robert (1977). "Métodos de generación de permutaciones". ACM Computing Surveys . 9 (2): 137–164. doi : 10.1145/356689.356692 . S2CID  12139332.
• Masato, Kobayashi (2011). "Enumeración de permutaciones bigrassmannianas por debajo de una permutación en orden Bruhat". Orden . 1 : 131–137.

Enlaces externos

• "Permutación", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]