Grupos simetricos Sn V:1.01

Grupos simétricos Sn V1.01: Operaciones con ciclos y permutaciones de Sn (An)

Por: Daniel San Miguel Reyero:

e-mail: CHEPI-@santandersupernet.com
e-mail: dsmiguel@hotmail.com

Fecha: 28-II-1997, 8-V-97

Este directorio es para la HP-48 G/GX no funcionará correctamente en las HP-48 S/SX sin transformar los programas ( no son nada complicados ) darán problemas , al menos, las ayudas incorporadas en cada comando, el archivo original instala al ejecutarse te dirá que este programa es de uso público ( puedes hacer con el lo que te de la gana, pues no está registrado ni nada parecido, alguien me cuenta como hacerlo :-) ) pero por favor se educado y siempre que lo distribuyas hazlo en su forma original sin ninguna modificación y por tanto figurando mi autoría, si lo utilizas para otro trabajo haz una referencia como mandan las buenas costumbres ;-). Ya se que el programa no vale gran cosa pues el problema no da para mucho, pero lo he hecho yo y lo hago como quiero, y mira me hacía ilusión. Si crees necesario cualquier cambio ponte en contacto con migo (CHEPI-@santandersupernet.com y si cambié de servidor prueba en dsmiguel@hotmail.com ).

cada programa dispone de una ayuda que se activa al detectar un error para visualizarla es suficiente activar el programa con la pila vacía o con un dato no válido, por ejemplo un carácter en el nivel uno de la pila. si disponemos de muy poca memoria se pueden eliminar esta ayudas muy fácilmente, pues los programas siguen la estructura:

IFERR

programa (no necesario delimitado por << >>)

THEN

"ayuda" CLLCD 1 DISP 7 FREEZE

END

Con lo que ganaremos pasos al dejar únicamente el programa, es decir borrar

IFERR

lo_que_hay_aquí_lo_dejamos_es_el_programa

THEN ...todo lo que haya ... END

TEORÍA Y PROGRAMAS:

El grupo Simétrico de orden n es el conjunto de todas las biyecciones de un conjunto de n elementos en si mismo, este conjunto tiene estructura de grupo no abeliano (no conmutativo en general ) por ejemplo el conjunto S3 es:

1 --> 1 1 --> 1 1 --> 2 1 --> 2 1 --> 3 1 --> 3
2 --> 2 2 --> 3 2 --> 3 2 --> 1 2 --> 1 2 --> 2
3 --> 3 3 --> 2 3 --> 1 3 --> 3 3 --> 2 3 --> 1

Rápidamente se ve que Card(Sn)=n!, generalmente se suelen representar las permutaciones (cada una de las biyecciones) de la siguiente manera:

|1 2 3| |1 2 3| |1 2 3| |1 2 3| |1 2 3| |1 2 3| (son las )
|1 2 3| |1 3 2| |2 3 1| |2 1 3| |3 1 2| |3 2 1| (de arriba)

Nomenclatura que utilizaremos en lo sucesivo:

En la HP48 utilizaremos solo la segunda fila en forma matricial, es decir:

[ 1 2 3 4 5 6 7 8 9]
[4 8 9 6 2 1 3 5 7] <---> [4 8 9 6 2 1 3 5 7]

Como las permutaciones son aplicaciones biyectivas la composición de dos ellas será otra biyección de Sn, para ello está el siguiente programa:

[t·s]     Calcula la composición de dos permutaciones, de Sn:
                                                                            i s(i) j t(j)
2: [t1 ... tn]         [1 2 4 5 3]        1 ---> 2 ---> 2     1
                                                                            2 ---> 1 ---> 1     2
1: [s1 ... sn]         [2 1 3 5 4]        3 ---> 3 ---> 4     3
                                                                            4 ---> 5 ---> 3     4
-> [t1(s1) ... tn(sn)] [2 1 4 3 5]       5 ---> 4 ---> 5     5

El conjunto Sn con la composición de aplicaciones es un grupo es decir, cerrado para la operación "·" (composición de aplicaciones ), asociativo, toda permutación tiene inversa por ser una aplicación biyectiva y tiene elemento neutro, esta es la permutación identidad: [1 2 ... n], el siguiente programa nos da la identidad en Sn (por trivial que resulte este programa es útil con n grande y es usado por otros programas, no borrar):

[ID.n] Dado n natural >0, nos da la permutación identidad

1: n --> [1 2 3 4 ... n]

   8 --> [1 2 3 4 5 6 7 8]

Hay un tipo de permutaciones especiales que solo cambian algunos índices, y los que modifican lo hacen de forma cíclica, veamos: |1 2 3 4 5| Es decir 5 -> 2, 2 -> 3, 3 ->5 con lo que podemos abreviar
|1 3 5 4 2| con {5 2 3} que es equivalente a { 2 3 5} y a {3 5 2}

A este tipo de permutaciones los denominamos ciclos, y en la HP-48 los representamos con listas de enteros (de tipo real para la HP, USR RPL) [CI->PE] Pasa de un ciclo a una permutación

2: {c1 ... cr}       {2 3 5}

1:   n                  5      ( necesita saber en que Sn trabajas )

---> [p1 ... pn]   [1 3 5 4 2]

Un resultado muy importante de la teoría de los grupos simétricos es que toda permutación se puede descomponer de manera única en ciclos disjuntos dos a dos, esta descomposición nos la da el siguiente programa:

[PE->CI] Transforma una permutación en su descomposición en ciclos disjuntos

1:  [p1 ... pn]      [2 1 9 8 7 6 5 3 4]

--> {c11 ... c1r1}        {1 2}

         ...             {3 9 4 8}

    {cs1 ... csrs}         {5 7}

[ORD.P] Nos da el orden de una permutación de Sn:

1: [p1 ... pn] --> r : p^r=Idn

   [2 1 5 3 4] --> 6

Como cada permutación es una biyección, tendrá una aplicación inversa, que será biyectiva con lo que tenemos una permutación inversa de la dada: [INV.P] Nos da la inversa de una permutación de Sn:

1: [p1 ... pn] --> [q1 ... qn] =INV[p1 ... pn]

   [2 1 4 3 5] --> [2 1 4 3 5] pues tiene orden 2 t·t=Idn lo comprobamos

                               con DUP [t·s] = Idn=[1 2 3 4 5]

   [1 2 4 5 3] --> [1 2 5 3 4]

Una definición necesaria para construir un subgrupo normal de Sn es el signo de una permutación, que nos es dado según el número de pares inversos que tiene la permutación, un par inverso es cuando pi>pj con i<j, un ejemplo: [2 1 5 4 3] tiene los pares inversos (2 1), (5 4), (5 3), (4, 3) con lo que tiene un número par de pares inversos y por tanto es una permutación par, para ello tenemos el siguiente programa:

[SIG.P] Dada una permutación nos da el número de pares inversos y su signo:

1:  [p1 ... pn]  [2 1 5 4 3] [2 1 5 3 4]

-->     r             4          3

      -1^r            1         -1

La importancia de este resultado es que la aplicación Sn ---> {1 -1} que a cada permutación le asocia su signo es un homomorfismo de grupos y por tanto su núcleo es un subgrupo normal, es decir el conjunto de permutaciones pares denominado An es un subgrupo normal.

   Nombre       Tamaño  Fecha    CRC

-------------- -------- ------- ---------

  GRU.Sn         1891    8-V-97 FB0B hex

 INSTALA         2546    8-V-97 CED7 hex

-------------- -------- ------- ---------

Nota: copo podréis observar vale casi más el fichero la documentación que el programa, este es el resultado de docenas de programas para la hp48 no documentados que casi han provocado mi desesperación, pero creo que es de agradecer.

Daniel San Miguel Reyero