Fórmula del númberu de permutaciones

Dau un conxuntu finito ${\displaystyle A\,\!}$ de ${\displaystyle n\,\!}$ elementos, el númberu de toes los sos permutaciones ye igual a factorial de n:
${\displaystyle n!=n(n-1)(n-2)\cdots 1\,\!}$.

Demostración: Yá que hai ${\displaystyle n\,\!}$ formes d'escoyer el primer elementu y, una vegada escoyíu ésti, namái tenemos ${\displaystyle (n-1)\,\!}$ formes d'escoyer el segundu elementu, y asina socesivamente, vemos que cuando llegamos al elementu k-ésimo namái tenemos ${\displaystyle [n-(k-1)]\,\!}$ posibles elementos pa escoyer, lo que nos lleva a que tenemos ${\displaystyle n(n-1)(n-2)\cdots 2\cdot 1\,\!}$ formes d'ordenar el conxuntu, xustamente lo qu'enunciamos enantes.

Exemplu: sía'l conxuntu A={1,2,3} nesti casu hai 6 permutaciones, en forma compacta: 123, 132, 213, 231, 312, 321. N'álxebra, pa estudiar los grupos simétricos presentar ente paréntesis y en dos files, na primera siempres apaez 1 2 3.

Una variante de lo mesmo, si va formase un comité qu'arreya presidente, tesoreru y secretariu, habiendo trés candidatos a, b, c ; cuando s'escueye por sortéu los cargos socesivamente, hai seis posibilidad o ordenaciones: abc, acb, bca, bac, cab, cba.

Notaciones

Representación gráfica de la permutación σ que revela la so estructura compuesta por 2 ciclos de llargor 4.

La primer forma d'escribir una permutación σ, anque nun ye la más compacta, consiste n'escribila en forma de matriz de dos renglones, asitiando nel primer renglón los elementos del dominiu 1, 2, 3,...,n, y nel segundu les imáxenes correspondientes a los elementos reordenaos σ(1), σ(2), σ(3),...,σ(n).
Por casu, dau'l conxuntu ordenáu ${\displaystyle \{1,...,8\}}$ podemos espresar una permutación ${\displaystyle \sigma }$ sobre ésti por aciu una matriz de correspondencies:

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

Claramente ye biyectiva, yá que podemos atopar una aplicación inversa ${\displaystyle \sigma ^{-1}}$ de forma que la so composición xenera l'aplicación identidá. Pa ello, en primer llugar intercambiamos los renglones y finalmente reordenamos les columnes de cuenta que los elementos del dominiu queden ordenaos de forma natural:

${\displaystyle \sigma ^{-1}={\begin{pmatrix}3&4&5&7&6&1&8&2\\1&2&3&4&5&6&7&8\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5&6&7&8\\6&8&1&2&3&5&4&7\end{pmatrix}}}$

Notación de ciclos

Esiste otra notación más compacta, llamada notación de ciclos. Un ciclu de llargor ye una permutación qu'intercambia cíclicamente elementos y afita los restantes. Esta notación revela meyor la estructura interna de la permutación. Pa ello:

1. Empezamos con cualquier elementu. Escribir, a la so derecha escribimos la so imaxe, a la derecha d'esta, la imaxe de la so imaxe, y siguimos asina hasta que se complete un ciclu.
2. Depués coyemos cualesquier elementu ensin contener nel primer ciclu, volvemos escribir la so imaxe a la so derecha, y siguimos hasta completar el segundu ciclu.
3. El procesu sigue hasta que la permutación entera quedó descrita como productu de ciclos dixuntos.

Siguiendo col mesmu exemplu d'antes, en notación de ciclos, ${\displaystyle \sigma }$ quedaría espresada como composición de dos ciclos:

${\displaystyle \sigma }$= (1 3 5 6)(2 4 7 8).

Descomposición d'una permutación en ciclos dixuntos

La descomposición realizada pol procedimientu anterior nun ye única en principiu, pos podríen llograse cualesquier d'estes resultancies equivalentes:

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

La descomposición canónica d'una permutación como productu de ciclos llógrase asitiando en primer llugar de cada ciclu'l númberu más pequeñu del mesmu. Darréu dar# en l'allugamientu de los ciclos, asitiando primero'l ciclu que'l so primer elementu sía menor. Frecuentemente, suelen omitise los ciclos de llargor 1. Asina la permutación (1 3)(2)(4 5) escríbese a cencielles como (1 3)(4 5).

Descomposición d'una permutación en transposiciones

Permutaciones de 4 elementos

D'esquierda a derecha apaecen les permutaciones en forma matricial, en forma de vector y como productu de tresposiciones. Los númberos a la derecha indiquen la cantidá de tresposiciones con que puede escribise cada permutación (esti númberu nun ye únicu, pero sí la so paridá). Les permutaciones impares tán marcaes con verde o naranxa.

Una tresposición ye una permutación qu'intercambia dos elementos y afita los restantes. Dichu otra manera, ye un ciclu de llargor 2. Una propiedá interesante ye que cualesquier permutación puede construyise como una composición de transposiciones, anque non de manera única. Daes dos descomposiciones en transposiciones d'una permutación cumplir que dambes usaren un númberu par o dambes van usar un númberu impar, eso dexa definir de manera unívoca la signatura d'una permutación.

Les tresposiciones dexen descomponer una permutación cualesquier d'una forma distinta a la descomposición en ciclos. En particular, les tresposiciones qu'apaezan nun van tener que ser dixuntes: Por casu, el ciclu (1 2 3 4) = (1 2) (2 3) (3 4). Equí l'orde d'aplicación ye importante: en primer llugar (3 4) dexa'l 4 nel so sitiu definitivu y el 3 descolocáu. Dempués (2 3) dexa nel so sitiu definitivu'l 3 y el 2 descolocáu, que va quedar recolocado definitivamente por (1 2).

Pa ver que cualesquier permutación descomponse como productu de tresposiciones va bastar ver que tou ciclu facer. La descomposición nun ye única. Por casu:

${\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úmberu de tresposiciones de la descomposición tampoco ye únicu. Por casu:

${\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 paridá del númberu de tresposiciones de la descomposición sí ta determinada. Esto ye, pa cualquier par de descomposiciones distintes de ${\displaystyle \sigma }$ con n y con m tresposiciones, respeutivamente, n y m tienen la mesma paridá (van ser simultáneamente pares o impares).

Dada una permutación cualesquier, defínese'l siguiente homomorfismo de grupos:

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

onde ${\displaystyle \scriptstyle S_{n}}$ ye'l grupu simétricu de n elementos y m ye un númberu enteru, tal qu'esisten tresposiciones ${\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

Vamos Llamar permutación par (resp. impar) a la que s'escribe como composición d'un númberu par (resp. impar) de tresposiciones.

Como exemplu, de les 6=3! permutaciones del conxuntu {1, 2, 3}, escrites en notación de ciclos:

• (1 2), (2 3) y (1 3) son, de forma trivial, impares.
• (1 2 3) y (1 3 2) son pares, como ye bono de comprobar al aplicar la fórmula anterior de descomposición d'un ciclu en tresposiciones.
• y (la identidá) tamién ye par.

Polo xeneral, demuéstrase que la metá de les n! permutaciones d'un conxuntu de n elementos son pares y la otra metá impares. Esto surde de resultes direuta de la esistencia del morfismo ${\displaystyle \varepsilon :S_{n}\to (\{-1,1\},\cdot )}$ que tien como nucleu xustamente a les permutaciones pares.

Estructura de grupu

Dau un númberu natural ${\displaystyle n\geq 1}$, consideramos el conxuntu ${\displaystyle X=\{1,2,...,n\}}$. Definimos el grupu de permutaciones de ${\displaystyle n}$ elementos, que denotaremos por ${\displaystyle S_{n}}$, o lo que ye lo mesmo, el conxuntu d'aplicaciones biyectivas de ${\displaystyle X}$ a ${\displaystyle X}$.

Les permutaciones pares formen un subgrupu normal d'índiz 2 del grupu S_n, al que vamos llamar grupu alternáu, y vamos notar por ${\displaystyle A_{n}}$.