Permutación

Versión matemática de un cambio de orden.

Cada una de las seis filas es una permutación diferente de tres bolas distintas.

En matemáticas , una permutación de un conjunto es, en términos generales, una disposición de sus miembros en una secuencia u orden lineal , o si el conjunto ya está ordenado, una reordenación de sus elementos. La palabra "permutación" también se refiere al acto o proceso de cambiar el orden lineal de un conjunto ordenado. ^[1]

Por ejemplo, hay seis permutaciones (ordenamientos) 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 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 clasificació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 , generalmente escrito como n ! , que significa el producto de todos los números enteros positivos menores o iguales a n .

Formalmente, una permutación de un conjunto S se define como una biyección de S hacia 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 . Tal función es equivalente a la reordenación de los elementos de S en la que cada elemento i es reemplazado por el correspondiente . Por ejemplo, la permutación (3, 1, 2) se describe mediante la función definida como ${\displaystyle f:S\to S}$ ${\displaystyle f(i)}$ ${\displaystyle \sigma }$

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

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

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

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

Historia

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

En Grecia, Plutarco escribió que Jenócrates de Calcedonia (396-314 a. C.) descubrió la cantidad de sílabas diferentes posibles en el idioma griego. 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 . Contiene el primer uso de permutaciones y combinaciones, para enumerar todas las palabras árabes posibles con y sin vocales. ^[5]

La regla para determinar el número de permutaciones de n objetos se conocía 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 como sigue:

El producto de la multiplicación de las series aritméticas que comienzan y aumentan por la unidad y continúan hasta el número de lugares, serán las variaciones de número con cifras determinadas. ^[6]

En 1677, Fabian Stedman describió los factoriales al explicar el número de permutaciones de campanas en el cambio de repique . Partiendo de dos campanas: "primero hay que 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 figuras que deben variarse". producido a partir de tres", que nuevamente se ilustra. Su explicación implica "desecha 3, y quedará 1,2; desecha 2, y quedará 1,3; desecha 1, y quedará 2,3". ^[8] Luego pasa a cuatro campanas y repite el argumento de desechar mostrando que habrá cuatro conjuntos diferentes de tres. Efectivamente, este es un proceso recursivo. Continúa con cinco campanas utilizando el método de "desechar" 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 modo que un repique completo de cambios en un número parece formarse uniendo los repiques completos de todos los números menores. en un cuerpo entero; ^[10]

Stedman amplía la consideración de permutaciones; continúa considerando 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 ocurrió alrededor de 1770, cuando Joseph Louis Lagrange , en el estudio de ecuaciones polinomiales, observó que las propiedades de las permutaciones de las raíces de una ecuación están relacionadas con las posibilidades de resuélvelo. Esta línea de trabajo resultó finalmente, a través del trabajo 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) mediante radicales. En las matemáticas modernas, hay muchas situaciones similares en las que comprender un problema requiere estudiar ciertas permutaciones relacionadas con él.

Las permutaciones jugaron 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 conjugadas exactamente cuando tienen el mismo tipo de ciclo, fue utilizada por el criptólogo Marian Rejewski para descifrar el cifrado alemán Enigma en los años 1932-1933. ^{[12] [13]}

Definición

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

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

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

La permutación de identidad se define por para todos los elementos y puede denotarse por el número , ^[a] por o por un solo 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 del grupo es composición de funciones . Así, para dos permutaciones y en el grupo , su producto está definido por: ${\displaystyle \sigma (x)=x}$ ${\displaystyle x\in S}$ ${\displaystyle 1}$ ${\displaystyle {\text{id}}={\text{id}}_{S}}$ ${\displaystyle S_{n}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle S_{n}}$ ${\displaystyle \pi =\sigma \tau }$

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

La composición suele escribirse 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 una reordenación de un conjunto, denominada permutación o sustitución activa . Un punto de vista más antiguo ve una permutación como una disposición ordenada o una lista de todos los elementos de S , llamada permutación pasiva (ver § Notación unifilar a continuación). ^[17]

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 asumimos . Un ciclo que consta de k elementos se llama k -ciclo. (Consulte § Notación de ciclo 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 toma consigo mismo, es decir , formando un 1-ciclo . Una permutación sin puntos fijos se llama trastorno . Una permutación que intercambia dos elementos (un solo ciclo de 2) y deja los demás fijos se llama transposición . ${\displaystyle \sigma }$ ${\displaystyle \sigma (x)=x}$ ${\displaystyle (\,x\,)}$

Notaciones

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

Notación de dos líneas

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

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

Se puede escribir como

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

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

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

Notación de una línea

Si hay un orden "natural" para los elementos de S , digamos ^[b] , 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 esta suposición, 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. ^{[20] [21]} 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 paréntesis u otras marcas adjuntas para la notación de una línea, mientras se usan paréntesis para la notación de ciclo. La notación unifilar también se llama representación de palabras . ^[22]

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

(Lo habitual es 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 e informática . Es especialmente útil en aplicaciones donde las permutaciones deben compararse como mayores o menores mediante el orden lexicográfico .

Notación de ciclo

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

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

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 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 esté 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 ciclos 1, ya que se pueden inferir: para cualquier elemento x en S que no aparece en ningún ciclo, se supone implícitamente . ^[23] ${\displaystyle \sigma (x)=x}$

Siguiendo la convención de omitir 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 de una línea se puede escribir en notación cíclica 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 se puede reescribir desde un punto de partida diferente; Por ejemplo,

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

Así, uno puede 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).}$

Notación de ciclo canónico

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

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

Por ejemplo,

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

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

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

Composición de permutaciones

Hay dos formas de indicar 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, ^[27] porque el argumento está escrito 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. ^{[28] [29] [30]} 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 está definido por . Este artículo utiliza la primera definición, donde se aplica primero la permutación más a la derecha. ${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$

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

Otros usos del término permutación

El concepto de permutación como disposición ordenada admite varias generalizaciones que han sido llamadas permutaciones , especialmente en la literatura más antigua.

k -permutaciones de n

En la literatura más 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 n -conjunto. ^{[c] [31] [32]} El número de tales k -permutaciones ( k -arreglos) de se denota de diversas formas mediante símbolos como , , , , o , ^[33] calculados mediante la fórmula: ^[34] ${\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 el supuesto de que sea un número entero no negativo y también es importante fuera de la combinatoria; se conoce como símbolo de Pochhammer o como potencia factorial descendente -ésima : ${\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 significar 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 , normalmente denotados : ${\displaystyle {\tbinom {n}{k}}}$

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

Permutaciones con repetición

Las disposiciones ordenadas de k elementos de un conjunto S , donde se permite la repetición, se denominan k -tuplas . A veces se les ha denominado permutaciones con repetición , aunque no son permutaciones en el sentido habitual. También se les llama palabras sobre el alfabeto S. Si el conjunto S tiene n elementos, el número de k -tuplas sobre S es Un lenguaje formal es un conjunto de palabras que obedecen reglas específicas. ${\displaystyle n^{k}.}$

Permutaciones de multiconjuntos

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

Si M es un multiconjunto finito , entonces una permutación 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 permutación de conjuntos múltiples. ^[d] Si las multiplicidades de los elementos de M (tomado en algún orden) son , , ..., y su suma (es decir, el tamaño de M ) es n , entonces el número de permutaciones multiconjunto de M viene dado por el coeficiente multinomial , ^[35] ${\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: ^[36]

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

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

Permutaciones circulares

Las permutaciones, cuando se consideran arreglos, a veces se denominan arreglos ordenados linealmente . Sin embargo, si los objetos están dispuestos de forma circular, este ordenamiento distinguido se debilita: no hay un "primer elemento" en la disposición, ya que cualquier elemento puede considerarse como el comienzo. Una disposición de objetos distintos de manera circular se llama permutación circular . ^{[37] [e]} Estos 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 de la disposición lineal hacia su frente.

Dos permutaciones circulares son equivalentes si una se puede girar hacia la otra. Las siguientes cuatro permutaciones circulares en 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 el sentido contrario a las agujas del reloj, por lo que las dos siguientes no son equivalentes ya que ninguna rotación puede acercar una a la otra.

 1 1 4 3 3 4 2 2

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

Propiedades

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

El número de n -permutaciones con k ciclos disjuntos es el número de Stirling sin signos de primera especie , denotado o . ^[38] ${\displaystyle c(n,k)}$ ${\displaystyle [{\begin{smallmatrix}n\\k\end{smallmatrix}}]}$

Tipo de ciclo

Los ciclos (incluidos los puntos fijos) de una permutación de un conjunto con n elementos dividen ese conjunto; por lo que las longitudes de estos ciclos forman una partición entera de n , que se denomina tipo de ciclo (o, a veces, estructura o forma del 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 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 están los números de ciclos de duración respectiva. El número de permutaciones de un tipo de ciclo determinado es ^[39] ${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$

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

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

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

Conjugando permutaciones

En general, la composición de permutaciones escritas en notación cíclica no sigue un patrón que se describa fácilmente: 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í, está el conjugado de by y su notación de ciclo se puede obtener tomando la notación de ciclo y aplicándola a todas las entradas que contiene. ^[40] De ello se deduce que dos permutaciones son conjugadas exactamente cuando tienen el mismo tipo de ciclo. ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$

Orden de una permutación

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

Paridad de una permutación

Toda permutación de un conjunto finito se puede expresar como producto de transposiciones. ^[41] Aunque pueden existir muchas expresiones de este tipo para una permutación determinada, todas contienen un número par de transposiciones o todas contienen un número impar de transposiciones. Por tanto, todas las permutaciones se pueden clasificar como pares o impares según este número.

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

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

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

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

Representación matricial

Una matriz de permutación es una matriz de 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,... ., norte }. 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 j- ^ésima columna igual al vector de columna n × 1 : su entrada ( i , j ) es 1 si i = σ ( j ), y 0 en caso contrario. Dado que la composición de asignaciones lineales se describe mediante la multiplicación de matrices, se deduce que esta construcción es compatible con la composición de permutaciones: ${\displaystyle L_{\sigma }}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$ ${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$ ${\displaystyle M_{\sigma }}$ ${\displaystyle M_{\sigma }}$ ${\displaystyle \mathbf {e} _{\sigma (j)}}$

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

Por ejemplo, las permutaciones de una línea tienen producto y las matrices correspondientes son: ${\displaystyle \sigma =213,\ \tau =231}$ ${\displaystyle \sigma \tau =132}$

$${\displaystyle M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.}$$

Composición de permutaciones correspondientes a una multiplicación de matrices de permutaciones.

También es común en la literatura encontrar la convención inversa, donde se asocia una permutación σ 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 al de las permutaciones, es decir, . En esta correspondencia, las matrices de permutación actúan en el lado derecho de los vectores de 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 Cayley de la derecha muestra estas matrices para permutaciones de 3 elementos.

Permutaciones de conjuntos totalmente ordenados

En algunas aplicaciones, los elementos del conjunto que se permutan se compararán entre sí. Esto requiere que el conjunto S tenga un orden total para que se puedan comparar dos elementos cualesquiera. El conjunto {1, 2, ..., n } con la relación ≤ habitual es el conjunto más utilizado 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 unifilar como una secuencia . ${\displaystyle \sigma =\sigma (1)\sigma (2)\cdots \sigma (n)}$

Ascensos, descensos, carreras, superaciones, récords

Un ascenso de una permutación  σ de n es cualquier posición i  <  n donde el siguiente valor 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 ejecución ascendente de una permutación es una subsecuencia contigua creciente no vacía que no se puede extender en ninguno de los extremos; corresponde a una secuencia máxima de ascensos sucesivos (este último puede estar vacío: entre dos descensos sucesivos todavía hay un tramo ascendente de longitud 1). Por el contrario, una subsecuencia creciente de una permutación no es necesariamente contigua: es una secuencia creciente obtenida omitiendo algunos de los valores de la notación unifilar. Por ejemplo, la permutación 2453167 tiene las carreras 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 recorridos ascendentes. ^[42]

El número de permutaciones de n con k ascensos es (por definición) el número de Euler ; este 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 recorridos ascendentes, que corresponden a k − 1 descensos. ^[43] ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$ ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$

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 llama excedencia débil . El número de n -permutaciones con k excedencias coincide con el número de n -permutaciones con k descensos. ^[44]

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

Lema de transición de Foata

La biyección fundamental de Foata transforma una permutación con una forma de ciclo canónico dada en la permutación cuya notación unifilar tiene la misma secuencia de elementos sin paréntesis. ^{[25] [45]} 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 , uno puede encontrar sus registros e insertar paréntesis para construir la transformación inversa . Subrayando los registros del ejemplo anterior: , 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 a cada lado mostrando la notación utilizada en la biyección: notación de una línea para y notación de ciclo canónico para . ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma }$ ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma }$

Como primer corolario, el número de n -permutaciones con exactamente k registros es igual al número de n -permutaciones con exactamente k ciclos: este último número es el número de Stirling sin signos del primer tipo , . 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. ^[45] Por ejemplo, (2)(31) = 321 tiene k = 2 superaciones débiles (en el índice 1 y 2), mientras que f (321) = 231 tiene k − 1 = 1 ascenso (en el índice 1; es decir, de 2 a 3). ${\displaystyle c(n,k)}$

Inversiones

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

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 . ^[47] Así, 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 desordenadas; es lo mismo para σ y para σ ⁻¹ . Poner en orden una permutación con k inversiones (es decir, transformarla en la permutación identidad), aplicando sucesivamente (multiplicación por la derecha por) transposiciones adyacentes , siempre es posible y requiere una secuencia de k tales operaciones. Además, cualquier elección razonable para las transposiciones adyacentes funcionará: basta con elegir en cada paso una transposición de i y 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 generar otros descensos). Esto es así porque 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 una descendencia. La clasificación por burbujas y la clasificación por inserción se pueden interpretar como instancias particulares de este procedimiento para ordenar una secuencia. Por cierto, este procedimiento demuestra que cualquier permutación σ puede escribirse como producto de transposiciones adyacentes; porque esto simplemente puede invertir cualquier secuencia de tales transposiciones que transformen σ 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 de Mahonia . ^[48] ​​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}!}$

Deja tal eso y . En este caso, digamos que el peso de la inversión es . Kobayashi (2011) demostró la fórmula de enumeración ${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$ ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle \sigma (i)-\sigma (j)}$

$${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

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

Permutaciones en informática

Permutaciones de numeración

Una forma de representar permutaciones de n cosas es mediante un número 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 contenerse 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 número 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). Entonces, el primer paso es simplemente expresar N en el sistema numérico factorial , que es simplemente 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 )! , ( norte - 2)! , ..., 2!, 1!. El segundo paso interpreta esta secuencia como un código de Lehmer o (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 hecha para el primer término  σ ₁ , el número d _{n −1} representa la elección hecha para el segundo término σ ₂ entre los n − 1 elementos restantes del conjunto , Etcétera. Más precisamente, cada d _{n +1− i} da el número de elementos restantes estrictamente menor que el término σ _i . Dado que los elementos restantes seguramente 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 un índice más pequeño (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. ^[49]

Ambas codificaciones se pueden visualizar mediante un diagrama de Rothe n  por  n ^[50] (llamado así 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 ); Según la definición de inversiones, una cruz aparece en cualquier cuadrado que viene antes del punto ( j , σ _j ) en su columna y antes del punto ( i , σ _i ) en su fila. El código 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 comenzar con una lista de los elementos de S en orden creciente, y para i aumentando de 1 a n establezca σ _i en el elemento de la lista que está precedido por d _{n +1− i} otros, y elimine 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 utiliza el número d de la tabla de inversión, el elemento de S se inserta en la secuencia en el punto donde está precedido por d elementos ya presentes. Alternativamente, se podrían procesar los números de la tabla de inversión y los elementos de S en el orden opuesto, comenzando con una fila de n espacios vacíos, y en cada paso colocar el elemento de S en el espacio vacío precedido por d otros espacios vacíos. ranuras.

La conversión de números naturales sucesivos al sistema numérico factorial produce esas secuencias en orden lexicográfico (como es el caso 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 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 numérico 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 la derecha. -mínimos a la izquierda (en el ejemplo, las posiciones 4, 8, 9 de los valores 1, 2, 5); esto permite calcular la distribución de dichos extremos entre todas las permutaciones. Una permutación con código de Lehmer d _n , d _{n −1} , ..., d ₂ , d ₁ tiene un ascenso n − i si y solo si d _i ≥ d _{i +1} .

Algoritmos para generar permutaciones.

En informática, puede ser necesario generar permutaciones de una secuencia determinada de valores. Los métodos mejor adaptados para hacer esto dependen de si se desean algunas permutaciones elegidas al azar o todas las permutaciones y, en el último caso, si se requiere un orden específico. Otra cuestión es si debe tenerse en cuenta la posible igualdad entre entradas en la secuencia dada; si es así, sólo se deberían generar permutaciones de conjuntos múltiples distintos de la secuencia.

Una forma obvia de generar permutaciones de n es generar valores para el código de Lehmer (posiblemente usando la representación del sistema numérico factorial de números enteros hasta n !), y convertirlos en las permutaciones correspondientes. Sin embargo, el último paso, aunque sencillo, es difícil de implementar de manera eficiente, porque requiere n operaciones, cada una de ellas de selección de una secuencia y eliminación de ella, 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 ^2/4 operaciones para realizar la conversión. Dado que 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 existen alternativas simples que funcionan considerablemente mejor. Por esta razón no parece útil, aunque sí posible, emplear una estructura de datos especial que permita realizar la conversión de código Lehmer a permutación en tiempo O ( n log n ) .

Generación aleatoria de permutaciones.

Para generar permutaciones aleatorias de una secuencia dada de n valores, no hay diferencia si se aplica una permutación de n seleccionada aleatoriamente a la secuencia o se elige un elemento aleatorio del conjunto de permutaciones distintas (multiconjuntos) de la secuencia. Esto se debe a que, aunque en el caso de valores repetidos puede haber muchas permutaciones distintas de n que den como resultado la misma secuencia permutada, el número de dichas permutaciones es el mismo para cada resultado posible. A diferencia de la generación sistemática, que se vuelve inviable para n grande 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 uno de los n ! secuencias de números enteros d ₁ , d ₂ ,..., d _n que satisfacen 0 ≤ d _i < i (dado que d ₁ es siempre cero, se puede omitir) y convertirlo en una permutación a través de una correspondencia biyectiva . Para esta ú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 . ^[51] Si bien en ese momento la implementación informática no era un problema, este método adolece de la dificultad descrita anteriormente para convertir de código Lehmer a permutación de manera eficiente. Esto se puede remediar usando una correspondencia biyectiva diferente: después de usar 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 hacia abajo más elementos un lugar , se intercambia el elemento con el elemento final restante. Por lo tanto, los elementos que quedan para la selección forman un rango consecutivo en cada momento, aunque no aparezcan en el mismo orden que en la secuencia original. El mapeo de una secuencia de números enteros a permutaciones es algo complicado, pero se puede ver 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 suficiente frecuencia como para justificar la prueba de la condición, pero el elemento final debe incluirse entre los candidatos de la selección, para garantizar que se puedan generar todas las permutaciones.

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

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

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

para  i  de 0 a  n −1 hacer  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 "divide y vencerás" pueden lograr el mismo resultado en paralelo. ^[52]

Generación en orden lexicográfico

Hay muchas formas de generar sistemáticamente todas las permutaciones de una secuencia determinada. ^[53] Un algoritmo clásico, simple y flexible se basa en encontrar la siguiente permutación en el orden lexicográfico , si existe. Puede manejar valores repetidos, en 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 Lehmer en orden lexicográfico (posiblemente usando el sistema numérico factorial ) y convertirlos en permutaciones. Comienza clasificando 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. ^[54]

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

1. Encuentre el índice k más grande tal que a [ k ] < a [ k + 1] . Si no existe tal índice, la permutación es la última permutación.
2. Encuentre el índice más grande l mayor que k tal que a [ k ] < a [ l ] .
3. Intercambie el valor de a [ k ] por el de a [ l ].
4. Invierta la secuencia desde a [ k + 1] hasta e incluyendo el elemento final a [ n ].

Por ejemplo, dada la secuencia [1, 2, 3, 4] (que está en orden creciente), y dado que el índice es de base 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 después del índice k a [2] hasta el elemento final se invierte. Debido a que solo hay un valor después de este índice (el 3), la secuencia permanece sin cambios en este caso. Así se permuta el sucesor lexicográfico del estado inicial: [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], momento en el que 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. ^[55]

Generación con cambios mínimos

Una alternativa al algoritmo anterior, el algoritmo Steinhaus-Johnson-Trotter , genera un orden en 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 orden de las permutaciones era conocido por los campaneros ingleses del siglo XVII, entre los cuales 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 un tiempo constante por permutación. Lo mismo también puede generar fácilmente el subconjunto de permutaciones pares, nuevamente en tiempo constante por permutación, omitiendo cualquier otra permutación de salida. ^[54]

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

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

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

1. Ordenamiento lexicográfico;
2. Algoritmo de Steinhaus-Johnson-Trotter ;
3. algoritmo de montón ;
4. Algoritmo de transposición de estrellas de Ehrlich: ^[54] 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: ^[58] en cada paso, se invierte un prefijo de la permutación actual para obtener la siguiente permutación;
6. Algoritmo de Sawada-Williams: ^[59] cada permutación difiere de la anterior ya sea por un desplazamiento cíclico hacia la izquierda en una posición o por un intercambio de las dos primeras entradas;
7. Algoritmo de Corbett: ^[60] 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 vía única: ^[61] cada columna es un desplazamiento cíclico de las otras columnas;
9. Código Gray de pista única: ^[61] cada columna es un desplazamiento cíclico de las otras columnas, además dos permutaciones consecutivas cualesquiera difieren solo en una o dos transposiciones.

Permutaciones meandricas

Los sistemas meandricos dan lugar a permutaciones meandricas , un subconjunto especial de permutaciones alternativas . Una permutación alternativa del conjunto {1, 2, ..., 2 n } es una permutación cíclica (sin puntos fijos) tal que los dígitos en la notación cíclica se alternan entre enteros pares e impares. Las permutaciones medias son útiles en el análisis de la estructura secundaria del ARN. No todas las permutaciones alternativas son meándricas. ¡Se ha utilizado una modificación del algoritmo de Heap para generar todas las permutaciones alternativas de orden n (es decir, de longitud 2 n ) sin generar todas (2 n )! permutaciones. ^{[62] [ ¿ fuente poco confiable? ]} Es necesaria la generación de estas permutaciones alternativas antes de analizarlas para determinar si son meándricas o no.

El algoritmo es recursivo. La siguiente tabla muestra un paso del procedimiento. En el paso anterior, se generaron todas las permutaciones alternativas de longitud 5. A tres copias de cada uno de estos se les agrega un "6" en el extremo derecho, y luego se aplica una transposición diferente que involucra esta última entrada y una entrada anterior en una posición par (incluida la identidad; es decir, sin transposición).

Aplicaciones

Las permutaciones se utilizan en el componente entrelazador 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 ^[63] ). 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 un hashing óptimo en Unique Permutation Hashing. ^[64]

Ver también

• Portal de matemáticas

• Permutación alterna
• Circunvolución
• orden cíclico
• Permutaciones pares e impares
• permutación de Josefo
• Símbolo de Levi-Civita
• Lista de temas de permutación
• índice principal
• Categoría de permutación
• grupo de permutación
• Patrón de permutación
• Representación de permutación (grupo simétrico)
• Probabilidad
• números de encuentros
• Red de clasificación
• Cifrado de sustitución
• Superpatrón
• Superpermutación
• Doce caminos
• Orden débil de permutaciones

Notas

1. 1 se usa con frecuencia para representar el elemento identidad en un grupo no conmutativo
2. El orden suele entenderse implícitamente. Naturalmente, un conjunto de números enteros se escribe de menor a mayor; un conjunto de letras está escrito en orden lexicográfico. Para otros conjuntos, es necesario especificar explícitamente un orden natural.
3. Más precisamente, variaciones sin repetición . El término sigue siendo común en otros idiomas y aparece con mayor frecuencia en las traducciones en inglés moderno.
4. El orden natural en este ejemplo es el orden de las letras de la palabra original.
5. En textos más antiguos, la permutación circular a veces se usaba como sinónimo de permutación cíclica , pero esto ya no se hace. Véase Carmichael (1956, p. 7).

Referencias

1. Webster (1969)
2. McCoy (1968, pág.152)
3. Nering (1970, pág.86)
4. Brezo, Thomas Little (1981). Una historia de las matemáticas griegas. Nueva York: Publicaciones de Dover. ISBN 0-486-24073-8. OCLC  7703465.
5. Broemeling, Lyle D. (1 de noviembre de 2011). "Un relato de la inferencia estadística temprana en criptología árabe". El estadístico estadounidense . 65 (4): 255–257. doi :10.1198/tas.2011.10191. S2CID  123537702.
6. Biggs, Países Bajos (1979). "Las raíces de la combinatoria". Historia de las Matemáticas . 6 (2): 109-136. doi :10.1016/0315-0860(79)90074-0.
7. Stedman 1677, pag. 4.
8. Stedman 1677, pag. 5.
9. Stedman 1677, págs. 6–7.
10. Stedman 1677, pag. 8.
11. Stedman 1677, págs. 13-18.
12. Rejewski, Marian (1980). "Una aplicación de la teoría de las permutaciones para descifrar el cifrado Enigma". Aplicaciones Mathematicae . 16 (4): 543–559. doi : 10.4064/am-16-4-543-559 . ISSN  1233-7234.
13. Efectivo, David (2019). "CMSC 28400 Introducción a la criptografía Otoño de 2019 - Notas n.º 2: Permutaciones y enigma" (PDF) .
14. Scheinerman, Edward A. (5 de marzo de 2012). "Capítulo 5: Funciones". Matemáticas: una introducción discreta (3ª ed.). Aprendizaje Cengage. pag. 188.ISBN _ 978-0840049421. Archivado desde el original el 5 de febrero de 2020 . Consultado el 5 de febrero de 2020 . Es habitual utilizar letras griegas minúsculas (especialmente π, σ y τ) para representar permutaciones.
15. Rotman 2002, pag. 41
16. Bogart 1990, pag. 487
17. Cameron 1994, pag. 29, nota al pie 3.
18. Cauchy, AL (enero de 1815). "Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières posibles les quantités qu'elle renferme" [Memoria sobre el número de valores que una función puede adquirir cuando se permuta dentro de ella, en todas las formas posibles, las variables que contiene]. Journal de l'École Polytechnique (en francés). 10 : 1–28. Ver pág. 4.
    • Traducción en inglés
19. Wussing, Hans (2007), La génesis del concepto de grupo abstracto: una contribución a la historia del origen de la teoría de grupos abstractos, Publicaciones Courier Dover, p. 94, ISBN 9780486458687, Cauchy utilizó su notación de permutación, en la que los arreglos se escriben uno debajo del otro y ambos están entre paréntesis, por primera vez en 1815.
20. Bogart 1990, pag. 17
21. Gerstein 1987, pag. 217
22. Aigner, Martín (2007). Un curso de enumeración . Springer GTM 238. págs. ISBN 978-3-540-39035-0.
23. Salón 1959, pag. 54
24. Bona 2012, p.87 [El libro tiene un error tipográfico aquí, ya que proporciona (45) en lugar de (54).]
25. Stanley, Richard P. (2012). Combinatoria enumerativa: Volumen I, Segunda edición . Prensa de la Universidad de Cambridge. pag. 30, Proposición 1.3.1. ISBN 978-1-107-01542-5.
26. Kitaev, Sergey (2011). Patrones en permutaciones y palabras . Medios de ciencia y negocios de Springer. pag. 119.ISBN _ 978-3-642-17333-2.
27. Biggs, Norman L.; Blanco, AT (1979). Grupos de permutación y estructuras combinatorias . Prensa de la Universidad de Cambridge. ISBN 978-0-521-22287-7.
28. Dixon, John D.; Mortimer, Brian (1996). Grupos de permutación . Saltador. ISBN 978-0-387-94599-6.
29. Cameron, Peter J. (1999). Grupos de permutación . Prensa de la Universidad de Cambridge. ISBN 978-0-521-65302-2.
30. Jerrum, M. (1986). "Una representación compacta de grupos de permutación". J. Algoritmos . 7 (1): 60–78. doi :10.1016/0196-6774(86)90038-6. S2CID  18896625.
31. "Combinaciones y permutaciones". www.mathsisfun.com . Consultado el 10 de septiembre de 2020 .
32. Weisstein, Eric W. "Permutación". mathworld.wolfram.com . Consultado el 10 de septiembre de 2020 .
33. Uspensky 1937, pag. 18
34. Charalambides, Ch A. (2002). Combinatoria enumerativa. Prensa CRC. pag. 42.ISBN _ 978-1-58488-290-9.
35. Brualdi 2010, pag. 46, Teorema 2.4.2
36. Brualdi 2010, pag. 47
37. Brualdi 2010, pag. 39
38. Bona 2012, págs. 97-103.
39. Sagan, Bruce (2001), The Symmetric Group (2 ed.), Springer, p. 3
40. Humphreys 1996, pag. 84.
41. Salón 1959, pag. 60
42. Bona 2004, pag. 4f.
43. Bona 2012, págs. 4-5.
44. Bona 2012, pag. 25.
45. Bona 2012, págs. 109-110.
46. Slocum, Jerry; Weisstein, Eric W. (1999). "15 - rompecabezas". MundoMatemático . Wolfram Research, Inc. Consultado el 4 de octubre de 2014 .
47. Bona 2004, pag. 43.
48. Bóna 2004, págs. 43 y siguientes.
49. Knuth 1973, pag. 12.
50. HA Rothe , Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263–305. Citado en Knuth 1973, p. 14
51. Pescador, RA; Yates, F. (1948) [1938]. Tablas estadísticas para investigaciones biológicas, agrícolas y médicas (3ª ed.). Londres: Oliver y Boyd. págs. 26 y 27. OCLC  14222135.
52. Bacher, A.; Bodini, O.; Hwang, Hong Kong; Tsai, TH (2017). "Generación de permutaciones aleatorias mediante el lanzamiento de monedas: algoritmos clásicos, nuevos análisis e implementación moderna" (ACM Trans. Algorithms 13(2): 24:1–24:43 ed.). págs. 24–43.
53. Sedgewick, R (1977). "Métodos de generación de permutaciones" (PDF) . Encuestas Informáticas . 9 (2): 137–164. doi :10.1145/356689.356692. S2CID  12139332. Archivado (PDF) desde el original el 21 de febrero de 2008.
54. Knuth 2005, págs. 1-26.
55. "std::next_permutation". cppreference.com . 4 de diciembre de 2017 . Consultado el 31 de marzo de 2018 .
56. Montón, BR (1963). "Permutaciones por intercambios". La revista informática . 6 (3): 293–298. doi : 10.1093/comjnl/6.3.293 .
57. Mütze, Torsten; Sawada, Joe; Williams, Aarón. "Generar permutaciones". Servidor de objetos combinatorios . Consultado el 29 de mayo de 2019 .
58. Zaks, S. (1984). "Un nuevo algoritmo para generación de permutaciones". BIT Matemáticas Numéricas . 24 (2): 196–204. doi :10.1007/BF01937486. S2CID  30234652.
59. Sawada, Joe; Williams, Aarón (2018). "Un camino de Hamilton para el problema sigma-tau". Actas del 29º Simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2018 . Nueva Orleans, Luisiana: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). págs. 568–575. doi : 10.1137/1.9781611975031.37 .
60. Corbett, PF (1992). "Gráficos de rotador: una topología eficiente para redes multiprocesador punto a punto". Transacciones IEEE en sistemas paralelos y distribuidos . 3 (5): 622–626. doi : 10.1109/71.159045.
61. Arndt, Jörg (2011). Asuntos computacionales. Ideas, algoritmos, código fuente . Saltador . doi :10.1007/978-3-642-14764-7. ISBN 978-3-642-14763-0.
62. Alexiou, A.; Psiha, M.; Vlamos, P. (2011). "Algoritmo basado en permutación combinatoria para la representación de estructuras secundarias de ARN cerradas". Bioinformación . 7 (2): 91–95. doi :10.6026/97320630007091. PMC 3174042 . PMID  21938211. 
63. "3GPP TS 36.212".
64. Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). "Hash de permutación único". Informática Teórica . 475 : 59–65. doi : 10.1016/j.tcs.2012.12.047 .

Bibliografía

• 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 los grupos , MacMillan
• Humphreys, JF (1996), Un curso de teoría de grupos, Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Clasificación y búsqueda , El arte de la programación informática, vol. 3 Este libro menciona el código Lehmer (sin usar 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), Generando 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 y 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, Fabián (1677), Campanalogía , Londres El editor se indica como "WS", que pudo haber sido William Smith, posiblemente actuando como agente de la Sociedad de Jóvenes Universitarios , sociedad a la que está dirigida la "Dedicatoria". Entre 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 nuevo diccionario colegiado de Webster , Springfield: G. & C. Merriam Company , 1969

Otras lecturas

• 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-2. El enlace es a una versión revisada y reescrito (LaTeX'ed) disponible gratuitamente del texto publicado originalmente por Springer-Verlag.
• Knuth, Donald (1998), Clasificación y búsqueda , El arte de la programación informática, vol. 3 (Segunda ed.), Addison – Wesley, ISBN 978-0-201-89685-5. Sección 5.1: Propiedades combinatorias de permutaciones, págs. 11–72.
• Sedgewick, Robert (1977). "Métodos de generación de permutaciones". Encuestas de Computación ACM . 9 (2): 137–164. doi : 10.1145/356689.356692 . S2CID  12139332.
• Masato, Kobayashi (2011). "Enumeración de permutaciones bigrassmannianas debajo de una permutación en orden Bruhat". Orden . 1 : 131-137.

enlaces externos

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