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

editar

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

editar

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

editar

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

editar

Notaciones

editar
 
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   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

editar

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,   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

editar

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

editar
 
  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:

 
 

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

editar

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

editar

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

editar

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

editar

Referencies

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