Permutación circular

 

Descomposición de una permutación en transposiciones[editar]

Permutaciones de 4 elementos

De izquierda a derecha aparecen las permutaciones en forma matricial, en forma de vector y como producto de transposiciones. Los números a la derecha indican la cantidad de transposiciones con que se puede escribir cada permutación (este número no es único, pero sí su paridad). Las permutaciones impares están marcadas con verde o naranja.

Una transposición es una permutación que intercambia dos elementos y fija los restantes. Dicho de otro modo, es un ciclo de longitud 2. Una propiedad interesante es que cualquier permutación se puede construir como una composición de transposiciones, aunque no de manera única. Dadas dos descomposiciones en transposiciones de una permutación se cumple que ambas usaran un número par o ambas usarán un número impar, eso permite definir de manera unívoca la signatura de una permutación.

Las transposiciones permiten descomponer una permutación cualquiera de una forma diferente a la descomposición en ciclos. En particular, las transposiciones que aparezcan no tendrán que ser disjuntas: Por ejemplo, el ciclo (1 2 3 4) = (1 2) (2 3) (3 4).

Nótese la diferencia entre permutación, ciclo y transposición, dado lo similar de la notación, la expresión anterior es equivalente a:{\displaystyle {\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4\\2&1&3&4\end{pmatrix}}\circ {\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}}\circ {\begin{pmatrix}1&2&3&4\\1&3&2&4\end{pmatrix}}\circ {\begin{pmatrix}1&2&3&4\\1&2&4&3\end{pmatrix}}}

La composición señalada como: {\displaystyle \circ } se opera de derecha a izquierda y no es conmutativa.

Aquí el orden de aplicación es importante: en primer lugar (3 4) deja el 4 en su sitio definitivo y el 3 descolocado. Después (2 3) deja en su sitio definitivo el 3 y el 2 descolocado, que quedará recolocado definitivamente por (1 2).

Para ver que cualquier permutación se descompone como producto de transposiciones bastará ver que todo ciclo lo hace. La descomposición no es única. Por ejemplo:{\displaystyle (a_{1},\ldots ,a_{n})=}{\displaystyle (a_{1},a_{2})(a_{2},a_{3})\cdots (a_{n-1},a_{n})=(a_{1},a_{n})(a_{1},a_{n-1})\cdots (a_{1},a_{2}).}

El número de transposiciones de la descomposición tampoco es único. Por ejemplo:{\displaystyle (a_{1},\ldots ,a_{n})=}{\displaystyle (a_{n-1},a_{n})(a_{1},a_{n-1})(a_{n-1},a_{n})(a_{1},a_{n-1})(a_{1},a_{n-2})\cdots (a_{1},a_{2}).}

Pero la paridad del número de transposiciones de la descomposición sí está determinada. Es decir, para cualquier par de descomposiciones distintas de {\displaystyle \sigma } con n y con m transposiciones, respectivamente, n y m tienen la misma paridad (serán simultáneamente pares o impares).

Dada una permutación cualquiera, se define el siguiente homomorfismo de grupos:

{\displaystyle \varepsilon :S_{n}\to (\{-1,1\},\cdot )\approx (\mathbb {Z} _{2},+),\qquad \varepsilon (\sigma )=(-1)^{m},}

donde {\displaystyle \scriptstyle S_{n}} es el grupo simétrico de n elementos y m es un número entero, tal que existen transposiciones {\displaystyle \scriptstyle \tau _{i}} tales que:

{\displaystyle \sigma =\tau _{1}\tau _{2}\dots \tau _{m}\in S_{n}.}

Permutación par y permutación impar[editar]

Artículo principal: Paridad de una permutación

Llamaremos permutación par (resp. impar) a la que se escribe como composición de un número par (resp. impar) de transposiciones.

Como ejemplo, dado el conjunto {1, 2, 3} de las 6=3! permutaciones posibles:

Permutación 1[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (1)(2)(3)\equiv id}

Las transposiciones: La identidad no tiene transposiciones. El número de transposiciones de id es 0(cero).

Permutación 2[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (1)(23)\equiv (23)}

Las transposiciones:{\displaystyle (23)\,}

El número de transposiciones es :1.

Permutación 3[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (12)(3)\equiv (12)}

Las transposiciones:{\displaystyle (12)\,}

El número de transposiciones es :1.

Permutación 4[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (123)\,}

Las transposiciones:{\displaystyle (12)(23)\,}

El número de transposiciones es :2.

Permutación 5[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (132)\,}

Las transposiciones:{\displaystyle (13)(32)\,}

El número de transposiciones es :2.

Permutación 6[editar]

La permutación{\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}

Escritas en notación de ciclos:{\displaystyle (13)(2)\equiv (13)}

Las transposiciones: La transposición es:{\displaystyle (13)\,}

El número de transposiciones es :1.

Conclusión[editar]

En general, se demuestra que la mitad de las n! permutaciones de un conjunto de n elementos son pares y la otra mitad impares. Esto surge como consecuencia directa de la existencia del morfismo {\displaystyle \varepsilon :S_{n}\to (\{-1,1\},\cdot )} que tiene como núcleo justamente a las permutaciones pares.

Estructura de grupo[editar]

Artículo principal: Grupo simétrico

Dado un número natural {\displaystyle n\geq 1}, consideramos el conjunto {\displaystyle X=\{1,2,...,n\}}. Definimos el grupo de permutaciones de {\displaystyle n} elementos, que denotaremos por {\displaystyle S_{n}}, o lo que es lo mismo, el conjunto de aplicaciones biyectivas de {\displaystyle X} a {\displaystyle X}.

Las permutaciones pares forman un subgrupo normal de índice 2 del grupo Sn, al que llamaremos grupo alternado, y notaremos por {\displaystyle A_{n}}.

Desorden[editar]

Permutación completa o desorden es una permutación de objetos en la que ninguno de los elementos aparece en su lugar natural.

Por ejemplo: la permutación 23451 es un desorden o permutación completa de un 12345 ya que ninguna cifra se encuentra en su posición original. Pero si la permutación fuera 15423 no se consideraría un desorden, debido a que el número 1 se encuentra en su posición natural.

TeoremaEl número de permutaciones completas de un conjunto de {\displaystyle n} elementos es:{\displaystyle PC_{n}=n!\left(1-{1 \over 1!}+{1 \over 2!}-{1 \over 3!}+...+(-1)^{n}{1 \over n!}\right)}

Se puede demostrar utilizando el principio de inclusión-exclusión.

Dato histórico[editar]

El estudio de las permutaciones de las raíces de ecuaciones algebraicas le permitió a Galois elaborar los inicios de la teoría de grupos y usar este vocablo, por primera vez, en matemáticas. Y empezó por los grupos no abelianos.

El concepto de permutación aparece en la obra hebrea Séfer Yetzirah ('El libro de la creación'), un manuscrito elaborado por un místico entre el año 200 y el 600. Pero existía ya un resultado anterior de Jenócrates de Calcedonia (396-314 a. C.)

​