Permutación

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\a S}$${\displaystyle \sigma (i)}$${\estilo de visualización \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,\lpuntos ,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.

Los objetos similares a permutaciones llamados 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 "descartar 3, y quedará 1.2; descartar 2, y quedará 1.3; descartar 1, y quedará 2.3". ^[8] Luego pasa a cuatro campanas y repite el argumento de descartar mostrando que habrá cuatro conjuntos diferentes de tres. Efectivamente, este es un proceso recursivo. Continúa con cinco campanas utilizando el método de "descartar" 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.

El estudio de las permutaciones como sustituciones en n elementos condujo a la noción de grupo como estructura algebraica, a través de los trabajos de Cauchy (memorias de 1815).

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 1932 y 1933. ^{[12] [13]}

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\en S}$${\estilo de visualización 1}$${\displaystyle {\text{id}}={\text{id}}_{S}}$ $Estilo de visualización S_{n}$${\estilo de visualización \sigma}$${\estilo de visualización \tau}$$Estilo de visualización 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 encuentra 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\,)}$

Se utilizan ampliamente varias notaciones para representar permutaciones de forma 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.

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}}.}$

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 .

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).}$

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, es una permutación de en notación de ciclo canónico. ^[26]$${\displaystyle (513)(6)(827)(94)}$$${\displaystyle S=\{1,2,\ldots ,9\}}$

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]

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}}}$

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

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}}.}$

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}.}$

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 ).

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.

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}}]}$

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.

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 }$

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}$

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).

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 }.}$$

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.

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)}$

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 .

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 }$

${\displaystyle {\hat {\sigma }}=f(\sigma )}$	${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$
${\displaystyle \mathbf {123} =(\,1\,)(\,2\,)(\,3\,)}$	${\displaystyle 123=\mathbf {(\,1\,)(\,2\,)(\,3\,)} }$
${\displaystyle \mathbf {132} =(\,1\,)(\,3\,2\,)}$	${\displaystyle 132=\mathbf {(\,1\,)(\,3\,2\,)} }$
${\displaystyle \mathbf {213} =(\,2\,1\,)(\,3\,)}$	${\displaystyle 213=\mathbf {(\,2\,1\,)(\,3\,)} }$
${\displaystyle \mathbf {231} =(\,3\,1\,2\,)}$	${\displaystyle 321=\mathbf {(\,2\,)(\,3\,1\,)} }$
${\displaystyle \mathbf {312} =(\,3\,2\,1\,)}$	${\displaystyle 231=\mathbf {(\,3\,1\,2\,)} }$
${\displaystyle \mathbf {321} =(\,2\,)(\,3\,1\,)}$	${\displaystyle 312=\mathbf {(\,3\,2\,1\,)} }$

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)}$

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 σ ⁻¹ . Poner en orden una permutación con k inversiones (es decir, transformarla en la permutación identidad), mediante la aplicación sucesiva (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 el momento (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 }$

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.

Diagrama de Rothe para${\displaystyle \sigma =(6,3,8,1,4,9,7,2,5)}$

σ yo i	1	2	3	4	5	6	7	8	9	Código Lehmer
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
Tabla de inversión	3	6	1	2	4	0	2	0	0

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 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} .

En informática 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 al azar 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 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 Lehmer a la permutación en tiempo O ( n log n ) .

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 tales 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, hacemos  d i ← elemento aleatorio de { 0, ..., i − 1 } intercambiamos  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]

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]

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}$

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}}$

Aquí se describe una secuencia explícita de permutaciones (transposiciones, 2-ciclos ), en la que cada permutación aplicada (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. Nótese que, dado que cada uno se genera secuencialmente, hay un último elemento . Entonces, después de generar por permutaciones, la siguiente permutación en tiene que ser para algún . Luego, se repiten todas las permutaciones que se generaron , generando toda la coset , llegando a la última permutación en esa coset ; el siguiente permutación tiene que mover la permutación a representante de otra 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 inicios de coset de en , de la siguiente manera: para pares, eligiendo todos los inicios de coset iguales a 1 y para impares, eligiendo inicios 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}}$

Las permutaciones se utilizan en el componente de intercalador de los algoritmos de detección y corrección de errores , como los códigos turbo ; por ejemplo, el estándar de telecomunicaciones móviles 3GPP Long Term Evolution utiliza estas ideas (consulte la especificación técnica 3GPP 36.212 ^[65] ). Tales aplicaciones plantean la cuestión de la generación rápida de permutaciones que satisfagan ciertas propiedades deseables. Uno de los métodos se basa en los polinomios de permutación . También como base para el hash óptimo en Unique Permutation Hashing. ^[66]

• Bogart, Kenneth P. (1990), Combinatoria introductoria (2.ª ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
• Bóna, Miklós (2004), Combinatoria de permutaciones , Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Bona, Miklos (2012), Combinatoria de permutaciones (2ª ed.), CRC Press, ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge University Press, ISBN 978-0-521-45761-3
• Carmichael, Robert D. (1956) [1937], Introducción a la teoría de grupos de orden finito , Dover, ISBN 978-0-486-60300-1
• Fraleigh, John B. (1976), Un primer curso de álgebra abstracta (2.ª ed.), Lectura: Addison-Wesley , ISBN 0-201-01984-1
• Gerstein, Larry J. (1987), Matemáticas discretas y estructuras algebraicas , WH Freeman and Co., ISBN 978-0-7167-1804-8
• Hall, Marshall Jr. (1959), La teoría de grupos , MacMillan
• Humphreys, JF (1996), Un curso de teoría de grupos, Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Ordenación y búsqueda , El arte de la programación informática, vol. 3 Este libro menciona el código de Lehmer (sin utilizar ese nombre) como una variante C ₁ ,..., C _n de las tablas de inversión en el ejercicio 5.1.1–7 (p. 19), junto con otras dos variantes.
• Knuth, Donald (2005), Generación de todas las tuplas y permutaciones , El arte de la programación informática , vol. 4, Addison–Wesley, ISBN 978-0-201-85393-3Fascículo 2, primera impresión.
• McCoy, Neal H. (1968), Introducción al álgebra moderna, edición revisada , Boston: Allyn and Bacon , LCCN  68015225
• Nering, Evar D. (1970), Álgebra lineal y teoría de matrices (2.ª ed.), Nueva 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

• 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.

Wikimedia Commons tiene medios relacionados con Permutaciones .

Wikiversidad tiene recursos de aprendizaje sobre la notación de permutación.

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