Permutación

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${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$, entonces se utiliza esto para la primera fila de la notación de dos líneas:

${\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 esta suposición, se puede omitir la primera fila y escribir la permutación en notación de una sola 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 ] Debe} tenerse cuidado de 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 delimitación para la notación de una línea, mientras que se usan paréntesis para la notación de ciclo. La notación de una línea también se llama representación de palabra . ^{[ 24 ]}

El ejemplo anterior quedaría entonces así:

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

(Normalmente, se utilizan comas para separar estas entradas solo si algunas tienen dos o más dígitos).

Esta forma compacta es común en combinatoria elemental e informática . Resulta especialmente útil en aplicaciones donde se comparan permutaciones para determinar si son mayores o menores utilizando el orden lexicográfico .

La notación cíclica 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 involucran conjuntos de elementos disjuntos , esto se conoce como "descomposición en ciclos disjuntos".

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

1. Escriba un corchete de apertura seguido de un elemento arbitrario x de${\displaystyle S}$: ${\displaystyle (\,x}$
2. Traza la órbita de x , anotando los valores bajo sucesivas aplicaciones 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úa con un elemento y de S que aún no se haya escrito y repite el proceso anterior:${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)}$
5. Repita el procedimiento 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 asume implícitamente${\displaystyle \sigma (x)=x}$. ^{[ 25 ]}

Siguiendo la convención de omitir los ciclos de longitud 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 de una línea${\displaystyle \sigma =265431}$se puede escribir en notación cíclica como: $${\displaystyle \sigma =(126)(35)(4)=(126)(35).}$$ Esto puede verse como la composición${\displaystyle \sigma =\kappa _{1}\kappa _{2}}$de permutaciones cíclicas $${\displaystyle \kappa _{1}=(126)=(126)(3)(4)(5),\quad \kappa _{2}=(35)=(35)(1)(2)(4)(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 partida diferente; por ejemplo, $${\displaystyle \sigma =(126)(35)=(261)(53).}$$ Así, 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 obtiene invirtiendo el orden de los elementos en cada ciclo. Por ejemplo, $${\displaystyle \sigma ^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).}$$

Toda permutación tiene una notación de ciclo particular que resulta útil en muchos contextos combinatorios, especialmente en la biyección de Foata que se describe a continuación. La notación de ciclo canónica se define de la siguiente manera:

• En cada ciclo, el elemento más grande aparece primero;
• Los ciclos están ordenados en orden ascendente según su primer elemento, sin omitir los ciclos de 1 elemento.

Por ejemplo,$${\displaystyle (513)(6)(827)(94)}$$es una permutación de${\displaystyle S=\{1,2,\ldots ,9\}}$en notación de ciclo canónico ( terminología de Miklós Bóna ). ^{[ 26 ]} Richard Stanley llama a esto la representación estándar , ^{[ 27 ]} y Martin Aigner usa la forma estándar . ^{[ 24 ]} Sergey Kitaev también usa la terminología de "forma estándar", pero invierte ambas elecciones; es decir, cada ciclo enumera primero su elemento mínimo, y los ciclos se ordenan en orden descendente de sus elementos mínimos. ^{[ 28 ]}

Hay dos maneras de denotar la composición de dos permutaciones. En la notación más común,${\displaystyle \sigma \cdot \tau }$es la función que asigna cualquier elemento x a${\displaystyle \sigma (\tau (x))}$. 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.

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úa 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 ^σ ; entonces el producto se define por${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$Este artículo utiliza la primera definición, donde se aplica primero la permutación más a la derecha.

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

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 arreglo ) significa un arreglo ordenado (lista) de un subconjunto de k elementos de un conjunto de n . ^{[ c ] [ 33 ] [ 34 ]} El número de tales k- permutaciones ( k -arreglos) de${\displaystyle n}$se denota de diversas maneras mediante símbolos como${\displaystyle P_{k}^{n}}$, ${\displaystyle _{n}P_{k}}$,${\displaystyle ^{n}\!P_{k}}$,${\displaystyle P_{n,k}}$,${\displaystyle P(n,k)}$, o${\displaystyle A_{n}^{k}}$, ^{[ 35 ]} calculado mediante la fórmula: ^{[ 36 ]}$${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factores} },}$$

que es 0 cuando k > n , y en caso contrario es igual a $${\displaystyle {\frac {n!}{(nk)!}}.}$$

El producto está bien definido sin asumir que${\displaystyle n}$es un entero no negativo y tiene importancia también fuera de la combinatoria; se le conoce como el símbolo de Pochhammer.${\displaystyle (n)_{k}}$o como el${\displaystyle k}$-octavo factorial descendente${\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: es decir, una k-combinación de un conjunto S es un subconjunto de k elementos (no ordenado) de S. Ordenar las k -combinaciones de S de todas las maneras posibles produce las k -permutaciones de S. Por lo tanto, el número de k -combinaciones de un conjunto de n elementos, C ( n , k ), está relacionado con el número de k -permutaciones de n mediante: $${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!\,k!}}.}$$

Estos números también se conocen como coeficientes binomiales , generalmente denotados${\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 llama 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 con 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${\displaystyle m_{1}}$,${\displaystyle m_{2}}$, ...,${\displaystyle m_{l}}$y su suma (es decir, el tamaño de M ) es n , entonces el número de permutaciones de multiconjuntos de M viene dado por un coeficiente multinomial : ^{[ 37 ]}$${\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 ). En este caso, el número de permutaciones se puede determinar con funciones generadoras : es${\displaystyle k!}$veces el coeficiente de${\displaystyle x^{k}}$en el producto

${\displaystyle \prod _{i=1}^{l}\sum _{j=0}^{m_{i}}{\frac {x^{j}}{j!}}}$. ^{[ 39 ]}

Continuando con el ejemplo anterior, en el caso del multiconjunto de letras en MISSISSIPPI, la función generadora resultante es $${\displaystyle {\begin{aligned}&(1+x)\cdot (1+x+x^{2}/2)\cdot (1+x+x^{2}/2+x^{3}/6+x^{4}/24)^{2}=\\&1+4x+{\frac {15}{2!}}x^{2}+{\frac {53}{3!}}x^{3}+{\frac {176}{4!}}x^{4}+{\frac {550}{5!}}x^{5}+{\frac {1610}{6!}}x^{6}+{\frac {4340}{7!}}x^{7}+{\frac {10430}{8!}}x^{8}+{\frac {21420}{9!}}x^{9}+{\frac {34650}{10!}}x^{10}+{\frac {34650}{11!}}x^{11}.\end{aligned}}}$$ Así, el número de 11-permutaciones es 34650 (el mismo resultado que el anterior), pero también tenemos el número de k -permutaciones con k que varía de 0 a 11.

Las permutaciones, cuando se consideran como arreglos, a veces se denominan arreglos linealmente ordenados . Sin embargo, si los objetos se disponen de forma circular, este orden distintivo 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 forma circular se denomina permutación circular . ^{[ 40 ] [ 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 último elemento del arreglo lineal al frente.

Dos permutaciones circulares son equivalentes si una puede transformarse en la otra mediante rotación. Las siguientes cuatro permutaciones circulares de cuatro letras se consideran iguales.

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&4&\\2&&1\\&3&\end{matrix}}\qquad {\begin{matrix}&2&\\3&&4\\&1&\end{matrix}}\qquad {\begin{matrix}&3&\\1&&2\\&4&\end{matrix}}}$$

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

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&1&\\3&&4\\&2&\end{matrix}}}$$

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

Los ciclos (incluidos los puntos fijos) de una permutación${\displaystyle \sigma }$de un conjunto con n elementos particionan 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${\displaystyle \sigma }$. Hay un "1" en el tipo de ciclo para cada punto fijo de${\displaystyle \sigma }$, un "2" por cada transposición, y así sucesivamente. El tipo de ciclo de${\displaystyle \beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$es${\displaystyle (3,2,2,1).}$

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

${\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 ciclos de un conjunto con n elementos es igual al valor de la función de partición.${\displaystyle p(n)}$.

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

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

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

Toda permutación de un conjunto finito puede expresarse como el producto de transposiciones. ^{[ 44 ]} Si bien pueden existir muchas expresiones de este tipo para una permutación dada, todas contienen un número par o un número impar de transposiciones. Por lo tanto, todas las permutaciones pueden clasificarse como pares o impares según este número.

Este resultado puede extenderse para asignar un signo , escrito${\displaystyle \operatorname {sgn} \sigma }$, a cada permutación.${\displaystyle \operatorname {sgn} \sigma =+1}$si${\displaystyle \sigma }$es par y${\displaystyle \operatorname {sgn} \sigma =-1}$si${\displaystyle \sigma }$es impar. Entonces, para dos permutaciones${\displaystyle \sigma }$y${\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 maneras de asignar una matriz de permutación a una permutación de {1, 2, ..., n }. Un enfoque natural es definir${\displaystyle L_{\sigma }}$ser la transformación lineal de${\displaystyle \mathbb {R} ^{n}}$que permuta la base estándar${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$por${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$y definir${\displaystyle M_{\sigma }}$ser su matriz. Es decir,${\displaystyle M_{\sigma }}$tiene su j ^-ésima columna igual al vector columna n × 1${\displaystyle \mathbf {e} _{\sigma (j)}}$: su entrada ( i , j ) es 1 si i = σ ( j ), y 0 en caso contrario. Dado que la composición de 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 M_{\sigma }M_{\tau }=M_{\sigma \tau }.}$$ Por ejemplo, las permutaciones de una sola línea${\displaystyle \sigma =213,\ \tau =231}$tener producto${\displaystyle \sigma \tau =132}$y las matrices correspondientes son: $${\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 se asocia una permutación σ a la matriz.${\displaystyle P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}}$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 al de las permutaciones, es decir,${\displaystyle P_{\sigma }P_{\tau }=P_{\tau \sigma }}$En esta correspondencia, las matrices de permutación actúan en el lado derecho de la matriz estándar.${\displaystyle 1\times n}$vectores fila${\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.

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   ${\displaystyle \sigma (i)<\sigma (i{+}1)}$. Por ejemplo, la permutación 3452167 tiene ascensos (en las posiciones) 1, 2, 5 y 6.

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

Una secuencia ascendente de una permutación es una subsecuencia contigua creciente no vacía que no se puede extender en ninguno de sus extremos; corresponde a una secuencia máxima de ascensos sucesivos (esta última puede estar vacía: entre dos descensos sucesivos aún existe una secuencia ascendente de longitud  1). Por el contrario, una subsecuencia creciente de una permutación no es necesariamente contigua: es una secuencia creciente obtenida al omitir algunos de los valores de la notación de una línea. Por ejemplo, la permutación 2453167 tiene las secuencias 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 rachas ascendentes. ^{[ 45 ]}

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

Una superación 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 superación débil . El número de n -permutaciones con k superaciones coincide con el número de n -permutaciones con k descensos. ^{[ 47 ]}

Un récord 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${\displaystyle f(\sigma )={\hat {\sigma }}}$cuya notación de una sola línea tiene la misma secuencia de elementos sin paréntesis. ^{[ 27 ] [ 48 ]} Por ejemplo: $${\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 en cada ciclo canónico de σ se convierte en un registro (máximo de izquierda a derecha) de${\displaystyle {\hat {\sigma }}}$. Dado${\displaystyle {\hat {\sigma }}}$, uno puede encontrar sus registros e insertar paréntesis para construir la transformación inversa.${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$. Subrayando los registros en el ejemplo anterior:${\displaystyle {\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4}$, lo que permite la reconstrucción de los ciclos de σ .

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

$${\displaystyle {\begin{array}{l|l}{\hat {\sigma }}=f(\sigma )&\sigma =f^{-1}({\hat {\sigma }})\\\hline \mathbf {123} =(\,1\,)(\,2\,)(\,3\,)&123=\mathbf {(\,1\,)(\,2\,)(\,3\,)} \\\mathbf {132} =(\,1\,)(\,3\,2\,)&132=\mathbf {(\,1\,)(\,3\,2\,)} \\\mathbf {213} =(\,2\,1\,)(\,3\,)&213=\mathbf {(\,2\,1\,)(\,3\,)} \\\mathbf {231} =(\,3\,1\,2\,)&321=\mathbf {(\,2\,)(\,3\,1\,)} \\\mathbf {312} =(\,3\,2\,1\,)&231=\mathbf {(\,3\,1\,2\,)} \\\mathbf {321} =(\,2\,)(\,3\,1\,)&312=\mathbf {(\,3\,2\,1\,)} \end{array}}}$$ 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 ,${\displaystyle c(n,k)}$. Además, el mapeo de Foata toma una n -permutación con k excedencias débiles a una n -permutación con k − 1 ascensos. ^{[ 48 ]} 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).

Una inversión de una permutación σ es un par ( i , j ) de posiciones donde las entradas de una permutación están en orden opuesto: ${\displaystyle i<j}$y${\displaystyle \sigma (i)>\sigma (j)}$. ^{[ 50 ]} 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).

A veces, una inversión se define como el par de valores ( σ ( i ), σ ( j )); esto no hace ninguna diferencia en cuanto al 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 de desorden de las entradas de una permutación; es el mismo para σ y para σ ⁻¹ . Para ordenar una permutación con k inversiones (es decir, transformarla en la permutación identidad), aplicando sucesivamente transposiciones adyacentes (multiplicación por la derecha) , siempre es 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 elimine este descenso en particular, aunque podría crear otros). Esto se debe a que aplicar 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 de 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 producto de transposiciones adyacentes; pues para ello basta con invertir cualquier secuencia de dichas transposiciones que transforme σ en la identidad. De hecho, al enumerar todas las secuencias de transposiciones adyacentes que transformarían σ en la identidad, se obtiene (tras la inversión) una lista completa de todas las expresiones de longitud mínima que escriben σ como producto de transposiciones adyacentes.

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

$${\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${\displaystyle [n]_{q}!}$denota el q-factorial . Esta expansión aparece comúnmente en el estudio de collares .

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

dónde${\displaystyle \leq }$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 .

Una forma de representar permutaciones de n elementos es mediante un entero N con 0  ≤ N < n !, siempre que se disponga de 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, resulta 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, n ≤ 20. La conversión puede realizarse 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 facilita la descripción de la conversión posterior a una permutación). El primer paso consiste simplemente en expresar N en el sistema numérico factorial , que es una representación particular de base mixta , donde, para números menores que n !, las bases (valores posicionales 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 (de forma casi equivalente) 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 realizada para el primer término σ ₁ , el número d _{n −1} representa la elección realizada para el segundo término σ ₂ 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 necesariamente aparecerán 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 aparece como el menor de los dos valores que aparecen en orden invertido. ^{[ 52 ]}         

Ambas codificaciones pueden visualizarse mediante un diagrama de Rothe de n x n ^{[ 53 ]} (llamado así por 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 definición de inversiones, aparece una cruz en cualquier casilla que se encuentre antes del punto ( j , σj ) en su columna y antes del punto ( i , σi _{) en su fila. El código de Lehmer indica el número de cruces en filas sucesivas, mientras que la tabla de} inversión indica el número de cruces en columnas sucesivas; es simplemente el código de Lehmer para la permutación inversa, y viceversa.  

Para convertir eficazmente un código de Lehmer d _n , d _{n −1} , ..., d ₂ , d ₁ en una permutación de un conjunto ordenado S , se puede comenzar con una lista de los elementos de S en orden ascendente, y para i creciente de 1 a n establecer σ _i al elemento en 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 usando 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 inverso, 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 numérico factorial produce esas secuencias en orden lexicográfico (como ocurre con cualquier sistema numérico de base mixta), y su posterior conversión a permutaciones conserva 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 las permutaciones por la posición 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 numérico factorial da el número de inversiones de la permutación, y la paridad de esa suma da la signatura 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 el ejemplo, las posiciones 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 computación, puede ser necesario generar permutaciones de una secuencia de valores dada. Los métodos más adecuados para ello dependen de si se desean permutaciones elegidas al azar o todas las permutaciones, y en este último caso, si se requiere un orden específico. Otra cuestión es si se debe tener en cuenta la posible igualdad entre los elementos de la secuencia; de ser así, solo se deben generar 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 enteros hasta n !) y convertirlos en las permutaciones correspondientes. Sin embargo, este último paso, aunque sencillo, es difícil de implementar de manera eficiente, ya que requiere n operaciones de selección y eliminación de una secuencia en una posición arbitraria; de las representaciones obvias de la secuencia como un arreglo o una lista enlazada , ambas requieren (por diferentes razones) aproximadamente n² /4 operaciones para realizar la conversión. Dado que n probablemente sea bastante pequeño (especialmente si se necesita generar todas las permutaciones) ^, esto no representa un gran problema, pero resulta que tanto para la generación aleatoria como para la sistemática existen 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 permutación en tiempo O ( n log n ) .

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

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

Generación con cambios mínimos

Una alternativa al algoritmo anterior, el algoritmo de 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 al intercambiar dos valores adyacentes. Este ordenamiento de las permutaciones era conocido por los campaneros ingleses del siglo XVII, entre quienes se le 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, también en tiempo constante por permutación, omitiendo una permutación de salida sí y otra no. ^{[ 57 ]}

Una alternativa al algoritmo de Steinhaus-Johnson-Trotter es el algoritmo de Heap , ^{[ 59 ]} que Robert Sedgewick afirmó en 1977 que era el algoritmo más rápido para generar permutaciones en aplicaciones. ^{[ 56 ]}

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

1. Ordenación lexicográfica;
2. Algoritmo de Steinhaus-Johnson-Trotter ;
3. Algoritmo de Heap ;
4. Algoritmo de transposición en estrella de Ehrlich: ^{[ 57 ]} en cada paso, la primera entrada de la permutación se intercambia con una entrada posterior;
5. Algoritmo de inversión de prefijos de Zaks: ^{[ 61 ]} en cada paso, se invierte un prefijo de la permutación actual para obtener la siguiente permutación;
6. Algoritmo de Sawada-Williams: ^{[ 62 ]} 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: ^{[ 63 ]} cada permutación difiere de la anterior por un desplazamiento cíclico a la izquierda de algún prefijo en una posición;
8. Ordenación de una sola vía: ^{[ 64 ]} cada columna es un desplazamiento cíclico de las otras columnas;
9. Código Gray de una sola vía : ^{[ 64 ]} cada columna es un desplazamiento cíclico de las otras columnas, además de que dos permutaciones consecutivas cualesquiera difieren solo en una o dos transposiciones.
10. Algoritmo generador de intercambios anidados en pasos conectados a los subgrupos anidados.${\displaystyle S_{k}\subset S_{k+1}}$Cada permutación se obtiene a partir de la anterior mediante una transposición y multiplicación a la izquierda. El algoritmo está conectado al sistema numérico factorial del índice.

Las permutaciones se utilizan en el componente de entrelazado 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 (véase la especificación técnica 3GPP 36.212 ^{[ 66 ]} ). Estas 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 hashing óptimo en Unique Permutation Hashing ^{[ 67 ] .}