Resumen Grupo3

RESUMEN COMPOSICIÓN DE PERMUTACIONES

Teoría de Grafos Integrantes: Gasparella Elsa C.I 19.319.657 Suarez Marleidy C.I 19.047.710 Leal Carolina C.I 15.396.835 Romero Marbis C.I 19.096.535 Maryori Márquez C.I. 19.593.937 Rivas Rosa C.I 14.401.687 Valero Edixon C.I. 19.043.756 Sección: SIS 604M.

DEFINICIÓN DE PERMUTACIÓN

Dado un conjunto finito con todos sus elementos diferentes, llamamos permutación a cada una de las posibles ordenaciones de los elementos de dicho conjunto. Por ejemplo, en el conjunto {1,2, 3}, cada ordenación posible de sus elementos, sin repetirlos, es una permutación. Existe un total de 6 permutaciones para estos elementos: "1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" y "3,2,1". La noción de permutación suele aparecer en dos contextos: • •

Como noción fundamental de combinatoria, centrándonos en el problema de su recuento. En teoría de grupos, al definir nociones de simetría.

Definición Alternativa La permutación antes citada "1,3,2" puede verse como la imagen de una aplicación σ de la lista inicial de objetos (1, 2, 3) en la lista de objetos reordenados (1, 3, 2). De este modo σ(1)=1, σ(2)=3 y σ(3)=2. También podemos definir a la permutación como la propia aplicación σ. Así, formalmente, una permutación de un conjunto X es una biyección de X en sí mismo. Aunque esta segunda definición generaliza a la primera al admitir conjuntos infinitos, el término permutación se usa principalmente para un conjunto finito X, y así lo haremos en el resto del artículo.

En combinatoria: La combinatoria trata del número de diferentes maneras que existen de considerar conjuntos formados a partir de elementos de un conjunto dado respetando ciertas reglas. Así un problema combinatorio consiste usualmente en establecer una regla sobre cómo deben ser las combinaciones y determinar cuántas existen que cumplan dicha regla. Un tipo importante de esas combinaciones son las llamadas permutaciones. Dada una n-tupla ordenada de elementos de un conjunto, el número de permutaciones es el número de n-tuplas ordenadas diferentes que pueden construirse a partir de dicho conjunto.

PERMUTACIÓN PAR Y PERMUTACIÓN IMPAR

Llamaremos permutación par (resp. impar) a la que se escribe como composición de un número par (resp. impar) de trasposiciones. Como ejemplo, de las 6=3! permutaciones del conjunto {1, 2, 3}, escritas 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 es fácil de comprobar al aplicar la fórmula anterior de descomposición de un ciclo en trasposiciones.

•

e (la identidad) también es par.

En general, se demuestra que la mitad de las n! permutaciones de un conjunto de n elementos son pares y la otra mitad impares. Estructura de grupo Dado un número natural , consideramos el conjunto X = {1,2,...,n}. Definimos el grupo de permutaciones de n elementos, que denotaremos por Sn, o lo que es lo mismo, el conjunto de aplicaciones biyectivas de X a X. Las permutaciones pares forman un subgrupo normal de índice 2 del grupo Sn, al que llamaremos grupo alternado, y notaremos por An. CICLO DE PERMUTACIÓN

Un ciclo que deja fijos a los elementos 2 y 5 y mueve cíclicamente al resto. Un ciclo es un tipo especial de permutación que fija cierto número de elementos (quizás ninguno) mientras que mueve cíclicamente el resto. En caso de no fijar ningún elemento lo denominaríamos permutación cíclica. Más concretamente, si un ciclo afecta a un elemento x cualquiera del conjunto, al aplicar dicho ciclo reiteradamente todos los elementos afectados por el reordenamiento pasarán por la posición de x en algún momento. Y de forma recíproca, el elemento x pasará por todas las posiciones de todos los elementos afectados por la permutación. Los ciclos son tipos de permutación especialmente importantes, pues pueden usarse como piezas básicas para construir cualquier otra permutación.

Definición formal: Sea

y

.

Un ciclo de longitud r o r-ciclo de Sn es una permutación σ tal que del conjunto {1,2,...,n} hay r elementos diferentes secuenciados, a1,a2,...,ar, para los cuales se cumple que: M(σ) = {a1,a2,...,ar}, de tal manera que σ(x) = x si

.

σ(a1) = a2,σ(a2) = a3,...,σ(ar − 1) = ar y σ(ar) = a1. MATRIZ DE PERMUTACIÓN La matriz permutación es la matriz cuadrada con todos sus n×n elementos iguales a 0, excepto uno cualquiera por cada fila y columna, el cual debe ser igual a 1. De acuerdo a esta definición existen n! matrices de permutación distintas, de las cuales una mitad corresponde a matrices de permutación par (con el determinante igual a 1) y la otra mitad a matrices de permutación impar (con el determinante igual a -1). Para n = 3 se tiene: Matrices de permutación par:

Matrices de permutación impar:

Puede notarse que las matrices de permutación conforman un grupo de orden n! respecto al producto.

PROPIEDADES DE LA MATRIZ DE PERMUTACIÓN

El elemento neutro del grupo es la matriz identidad.

• • • • • • •

El elemento inverso de cada elemento del grupo de matrices de permutación es la matriz traspuesta correspondiente. Cada elemento del grupo de matrices de permutación es una matriz ortogonal. El producto de matrices de permutación par siempre genera una matriz de permutación par. El producto de matrices de permutación impar siempre genera una matriz de permutación par. El producto de matrices de permutación de paridad distinta siempre genera una matriz de permutación impar. Observe que las matrices de permutación par conforman un semigrupo y que además el grupo de matrices de permutación no es conmutativo. Cada elemento del grupo de matrices de permutación fuera del semigrupo es una matriz simétrica.

El grupo simétrico sobre un conjunto X, denotado por SX es el grupo formado por las funciones biyectivas (permutaciones) de X en sí mismo. Los subgrupos de denominan grupos de permutaciones. El Teorema de Cayley afirma que todo grupo G es isomorfo a un grupo de permutaciones (ie: un subgrupo del simétrico). De especial relevancia es el grupo simétrico sobre el conjunto finito X = {1,...,n}, denotado por Sn. El grupo Sn tiene orden n! y no es abeliano para n>2. COMPOSICIÓN DE PERMUTACIÓN Hay diversas formas de representar una permutación. Podemos escribir una permutación σ en forma de matriz, situando en primera fila los elementos del dominio 1, 2, 3..., y en la segunda las imágenes correspondientes σ(1), σ(2), σ(3),.... Dada dos permutaciones, su composición se realiza siguiendo las reglas usuales de composición de funciones:

Si

y

su composición es:

El cálculo de la composición puede seguirse de un modo visual, recordando que al componer funciones se opera de derecha a izquierda:

Como las permutaciones son funciones de un conjunto en sí mismo, se pueden componer. Ejemplo 1: Sean: δ= 1 2 3 4

y

2 4 1 3

r= 1 2 3 4 4 2

3 1

Entonces r δ es: rδ= 1 2 3 4 2 1 4 3

Ejemplo 2: Sean f= 1 2 3 4 3 4 2 1

y

g= 1 2 3 4 4 2

3 1

Entonces la permutación es: f(1) = 3 y g(3)= 3;

entonces fg(1)= 3

f(2) = 4 y g(4)= 1;

entonces fg(2)= 1

f(3) = 2 y g(2)= 2;

entonces fg(3)= 2

f(4) = 1 y g(1)= 4;

entonces fg(4)= 4

Podemos entonces escribir fg = 1 2 3 4 3 1 2 4

Ejercicio a resolver: Hallar la permutación gf, es decir, actuando primero g y después f, o simbólicamente (gf)(i)= f(g(i). Responder: ¿Da lo mismo? ¿Qué quiere decir esto?