Práctica 4: El Grupo Simétrico

4.1 Introducción

Composición de permutaciones: Una permutación en Mathematica se representa como una lista de listas, en la que cada una de las sublistas representa un ciclo. Así, un ciclo se representará como una lista doble. Una composición de permutaciones se representará como una lista cuyas entradas son los ciclos de las permutaciones que deseamos componer.

permut1 = {{1, 2, 3, 4, 5}};

permut2={{1,2,3,4,5},{6,5}};

4.2 Aplica

La función aplica devuelve la imagen del elemento x, una vez aplicada la permutación per.

aplica[per_,x_]:= 
Module[{n,i}, 
If[Length[per]==0,Return[x]];
n=x; 
Do[ If[MemberQ[per[[i]],n], 
	n=per[[i,Mod[Position[per[[i]],n][[1,1]], 
	Length[per[[i]]]]+1]]],{i,Length[per],1,-1}]; 
Return[n]; ]

aplica[permut1, 3]

aplica[permut2,6]

Para componer dos permutaciones, bastará con unir los ciclos que componen cada permutación en una sola como se muestra con un ejemplo: 
permut1 ° permut2={{1,2,3,4,5},{1,2,3,4,5},{6,5}}

4.3 Ciclos Disjuntos

La siguiente función calcula los ciclos disjuntos de una permutación o de una composición de permutaciones.

disjuntos[per_]:= 
Module[{d1,d2,d3={},n}, 
d1=Apply[Union,per];
While[d1!={},
	n=d1[[1]];
	d2={}; 
	While[MemberQ[d1,n], 
		AppendTo[d2,n]; 
		d1=Drop[d1,Position[d1,n][[1]]]; 
		n=aplica[per,n] ] ; 
	AppendTo[d3,d2]];
Return[d3]; ]

disjuntos[permut2]

disjuntos[permut1]

4.4 Orden

El orden de una permutación viene dado por el mínimo común múltiplo de las longitudes de sus ciclos disjuntos.

orden[per_]:=Module[{d1,i,n}, 
	d1=disjuntos[per];
	d2=Table[Length[d1[[i]]],{i,1,Length[d1]}]; 
	n=Apply[LCM,d2]; 
	Return[n]; ]

permut3 = {{1, 2, 3, 4, 5, 6, 7, 8}, {1, 3, 5, 6, 7}, {2, 5, 6}, {1, 
            2}};

disjuntos[permut3]

orden[permut3]

Vamos a comprobar el orden obtenido, al ser 6, al componer permut3 6 veces consigo misma se obtendrá como resultado la permutación identidad.
A continuación, aplicamos la permutación "permut3" 6 veces.

permut3 = Table[permut3, {i, 1, 6}]

permut3 todavía no tiene la estructura adecuada para definir una permutación. Si nos fijamos, está formada por una lista de permutaciones, y no por una lista de ciclos. Para solucionar este problema, realizamos la  concatenación de todas las permutaciones utilizando Join (quita los paréntesis de más).

permut4 = Apply[Join, permut3]

disjuntos[permut4]

Esta última permutación es la permutación indentidad, luego podemos deducir que el orden de permut3 es el efectivamente 6.

4.5 Transposiciones

Como ya sabemos, toda permutación se puede expresar como composición de ciclos de longitud par.
La función "trans" escribe como producto de transposiciones "un solo ciclo".

trans[ciclo_]:=Module[{d={},i}, 
	Do[AppendTo[d,{ciclo[[1]],ciclo[[i]]}], 
                   {i,Length[ciclo],2,-1}]; 
                   Return[d]; ]

trans[{1,2,3,4}]

trans[{{3}}]

La función "transposicion" expresa como producto de transposiciones cualquier permutación.

transposicion[per_]:=Module[{d1={},d2={},i}, 
	Do[AppendTo[d1,trans[per[[i]]]], 
           {i,1,Length[per]}]; 
	Do[If[d1[[i]]!={},AppendTo[d2,d1[[i]]]],{i,1,Length[d1]}]; 
           Return[Flatten[d2,1]]; ]

transposicion[{{1,2,3},{4,5,6,7,11}}]

4.6 Signatura

Un ciclo tiene signatura +1 si es de longitud impar y -1 en caso contrario.  Además la signatura del producto de varios ciclos es igual al producto de la signatura de cada uno de ellos.

La función "sig" calcula la signatura de un solo ciclo

\(sig[ciclo_] := 
      Module[{n}, 
		n = Length[ciclo]; 
		If[Mod[n, 2] == 0, 
          Return[\(-1\)], Return[1]]]\)

sig[{1, 2, 3}]

sig[{1, 2, 3, 4}]

La función "signatura" calcula la signatura de cualquier permutación.

signatura[per_]:=Module[{d}, 
d=Table[sig[per[[i]]],{i,1,Length[per]}]; 
Return[Apply[Times,d]]]

signatura[{{1,3},{2,4},{3,5}}]

4.7 Inverso

Esta función calcula el inverso de una permutación

inverso[per_]:=Module[{d={},i}, 
Do[PrependTo[d,Reverse[per[[i]]]],{i,1,Length[per]}]; 
Return[d]; ]

permut5 = {{1, 2, 3}, {1, 2}};

permut6=inverso[permut5]

permut7 = Join[permut5, permut6]

Comprobamos que es la identidad:

disjuntos[permut7]

La función que a continuación se presenta está destinada a facilitar la resolución de los ejercicios de este tema. Esta función compone una permutación "x" con otra "y". Por otro lado, si "y" es un número natural "n", entonces compone la permutación "x" con ella misma  "n" veces.

composicion[x_,y_]:=Module[{},
If[IntegerQ[y],Return[Flatten[Table[x,{y}],1]],Return[Flatten[{x,y},1]]]]

Ejercicios:

1. Sea α=(1 2 3 4 5), calcular (α^2),(α^3),(α^4) y  (α^5).

2. Calcular el producto de las permutaciones (α^2)(β^3), siendo α=(1 4 3 2)(5 7 6) y β=(1 6 2 3 4)(5 7)

3. Calcula la signatura de las permutaciones de los ejercicios anteriores.

4. Calcula el inverso de la permutación α=(1 3 5 7)(2 4)(6 8 9) y  comprueba el resultado.

5. Expresa las permutaciones siguientes como productos de transposiciones y comprueba el resultado:
	     a) α=(1 2 3 4)(5 6)
	     b) β=(1 3 5)(2 4 6 8 10 11 9)(7 15 12 14 13)
	     c) αβ

6. Calcular los elementos de los  grupos generados por las permutaciones  α=(1 2 3 4 5) y
β=(1 7 5)(6 2 4 3) respectivamente.

7. En cierto departamento de una universidad, la secretaria ha recibido 20 cartas, una para cada uno de los miembros de dicho departamento. Ésta ha colocado las cartas en el casillero de cada uno de dichos miembros sin tener en cuenta su destinatario. De este modo, el profesor 3 recibió la carta dirigida al 1, el 5 la de 3, y así con todos los impares, hasta el 1 que ha recibido la del profesor 19. Los propietarios de los casilleros pares quedaron de la siguiente forma: el 4 recibió la de 2, el 10 la de 4, el 18 la de 10, el 2 la de 18 y el 6 y el 12 las recibieron intercambiadas. El resto recibieron su carta correctamente. Si todos devolvieron la carta a la secretaria siguiendo el orden natural, y la secretaria repartió de nuevo las cartas siguiendo el mismo método, ¿ cuántas veces debió repartir la secretaria  las cartas para que todo el mundo quedara contento ?. ¿ Existe una forma más rápida de arreglar el equívoco ?

8. Otra secretaria recibe un ordenador inusual: cuando se pulsa la tecla correspondiente a un carácter, sobre la pantalla aparece otro distinto. Sin embargo, todo carácter marcado en el teclado puede ser obtenido pulsando alguna tecla del mismo. La secretaria decide escribir el texto siguiente en la forma usual: 
ALGUNAS VECES ENCONTRAR UNA RAZON ME DEJA EXHAUSTA. PERO YO PERSISTO.
Obteniendo la siguiente copia.
RULVZRH XOJOH OZJTZEMRM VZR MRSTZ YO IONR OGCRVHER. AOMT 
DT AOMHPHET.
Ella retoma el resultado y lo escribe en la forma usual, obteniendo otra copia indescifrable. De nuevo, coge la segunda copia y la escribe para obtener otra versión... Si la secretaria repite este proceso de forma indefinida,  ¿obtendrá alguna vez una copia del texto original ?. Calcular la copia que obtendrá tras realizar el proceso 2327 veces.

9. La siguiente línea muestra un mensaje encriptado utilizando un criptosistema basado en la siguiente  permutación: 
STES SRSCBOBOI STEN JOSA
Si aplicamos de nuevo nuestro criptosistema al mensaje anterior obtenemos el siguiente  mensaje sin sentido:
TEST TCTBJIJIO TESA RITN
¿Cuántas veces deberíamos aplicar la permutación  sucesivamente hasta leer correctamente el mensaje?.  Desencriptar el mensaje.

10. La puertas de un instituto de investigación se abren al teclear un código de acceso de 10 dígitos. Cada mes el código de acceso cambia siguiendo una pauta marcada por una permutación de dichos dígitos. Dicha permutación es (1 2 3 5 7 4)(8 9 6 10). Si el código de esta semana es 8374502901, ¿cuál será dentro de medio año ?.¿ Cada cuántos meses se repite un código ?.

11. Un timador realiza el típico juego de esconder un garbanzo debajo de un vaso. Para ello el timador utiliza, en lugar de los habituales 3 vasos, un total de 10, con lo que el juego es mucho más complejo. Un matemático observa que en cada partida  utiliza los mismos movimientos, los cuales coinciden con la siguiente permutación (3 8 10)(3 1 2 5 6)(4 7 9 8). El matemático propone al timador la siguiente apuesta: si me dices en qué vaso has introducido el garbanzo y el número de partidas que has realizado, te propongo apostar la cantidad que habitualmente apuestas en una partida multiplicada  por dicho número de veces, a que adivino en qué lugar acaba el garbanzo. Define una función que ayude al matemático a ganar su apuesta. Si introduce el garbanzo en el cuarto  vaso, después de 7 partidas, ¿donde estará  el garbanzo?. ¿ Cuántas partidas tardará el garbanzo en volver al cuarto vaso ?.