Permutación

En matemátiques, una permutación ye la variación del orde o de la disposición de los elementos d'un conxuntu ordenáu o una tupla ensin elementos repitíos.

Por casu, nel conxuntu {1,2,3}, cada ordenación posible de los sos elementos, ensin repitilos, ye una permutación. Esiste un total de 6 permutaciones pa conxuntos de 3 elementos, nesti casu: "1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" y "3,2,1".

Definición formal

La definición intuitiva de permutación, como ordenamientos o arreglos de los elementos d'un conxuntu formalizar col usu del llinguaxe de funciones matemátiques.

Una permutación d'un conxuntu X ye una función biyectiva de dichu conxuntu en sí mesmu.

Exemplu de permutación considerada como función biyectiva.

Pa ilustrar la definición, retomemos l'exemplu descritu na introducción. Nel exemplu, X={1, 2, 3}.

Entós, cada correspondencia unu a unu ente'l conxuntu {1, 2, 3} a sigo mesmu equival a una forma d'ordenar los elementos.

Por casu, la asignación biyectiva dada por

• 1 → 1
• 2 → 2
• 3 → 3

puede faese corresponder al ordenamientu "1, 2, 3".

Per otru llau, la asignación biyectiva dada por

• 1 → 3
• 2 → 2
• 3 → 1

puede faese corresponder al ordenamientu "3, 2, 1".

Na definición de permutación, nun s'establez condición dalguna sobre X, que puede inclusive ser infinitu. Sicasí, ye común considerar namái'l casu en que X ye un conxuntu finito al estudiar permutaciones.

En combinatoria

La combinatoria trata del númberu de distintes maneres qu'esisten de considerar conxuntos formaos a partir d'elementos d'un conxuntu dau, respetando ciertes regles, como'l tamañu, l'orde, la repetición, la partición. Asina un problema combinatoriu consiste usualmente n'establecer una regla sobre cómo tienen de ser les agrupaciones y determinar cuántes esisten que cumplan dicha regla. Básicamente, tres asunto: permutaciones, combinaciones y variaciones.

Un tipu importante d'eses agrupaciones son les llamaes permutaciones. Dada una n-tupla ordenada de los elementos d'un conxuntu, el númberu de permutaciones ye'l númberu de n-tuplas ordenaes posibles.

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.

En teoría de grupos

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

Artículu principal: Paridá d'una permutación

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

Artículu principal: grupu simétricu

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

Datu históricu

L'estudiu de les permutaciones de les raigaños d'ecuaciones alxebraiques dexó-y a Galois ellaborar los entamos de la teoría de grupos y usar esti vocablu, per primer vegada, en matemátiques. Y empezó polos grupos non abelianos.

El conceutu de permutación apaez na obra hebrea Séfer Yetzirah ('El llibru de la creación'), un manuscritu ellaboráu por un místicu ente l'añu 200 y el 600. Pero esistía yá un resultáu anterior de Jenócrates de Calcedonia (396-314 e. C.)^[1]

Ver tamién

• Ciclu (permutación)
• Matriz permutación
• Combinatoria
• Combinaciones
• Variaciones

Referencies

1. Grimaldi, Ralph: «Matemátiques discreta y combinatoria» 0-201-65376-1 , páx.44

• Datos: Q161519
• Multimedia: Permutations