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.

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  de  elementos, el númberu de toes los sos permutaciones ye igual a factorial de n:
.

Demostración:
Yá que hai  formes d'escoyer el primer elementu y, una vegada escoyíu ésti, namái tenemos  formes d'escoyer el segundu elementu, y asina socesivamente, vemos que cuando llegamos al elementu k-ésimo namái tenemos  posibles elementos pa escoyer, lo que nos lleva a que tenemos  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 
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  podemos espresar una permutación  sobre ésti por aciu una matriz de correspondencies:

Claramente ye biyectiva, yá que podemos atopar una aplicación inversa  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:

 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:
 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.
 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.
 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,  quedaría espresada como composición de dos ciclos:
= (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:
 = (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 
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:





El númberu de tresposiciones de la descomposición tampoco ye únicu. Por casu:





Pero la paridá del númberu de tresposiciones de la descomposición sí ta determinada. Esto ye, pa cualquier par de descomposiciones distintes de  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:

onde  ye'l grupu simétricu de n elementos y m ye un númberu enteru, tal qu'esisten tresposiciones  tales que:

 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  que tien como nucleu xustamente a les permutaciones pares.

 Estructura de grupu 

Dau un númberu natural , consideramos el conxuntu . Definimos el grupu de permutaciones de  elementos, que denotaremos por , o lo que ye lo mesmo, el conxuntu d'aplicaciones biyectivas de  a .

Les permutaciones pares formen un subgrupu normal d'índiz 2 del grupu Sn, al que vamos llamar grupu alternáu, y vamos notar por .

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.)Grimaldi, Ralph: «Matemátiques discreta y combinatoria» 0-201-65376-1 , páx.44 

 Ver tamién 
 Ciclu (permutación)
 Matriz permutación
 Combinatoria
 Combinaciones
 Variaciones

 Referencies 

Categoría:Combinatoria