miércoles, 23 de marzo de 2011

Collares bicolores – Órbitas y estabilizadores

Llamemos C al conjunto de permutaciones de n cuentas, r de ellas de color negro y s de color blanco, con r+s=n. En total existirán Cn,r = Cn,s elementos. Con las condiciones que se impusieron en la anterior entrada en la definición de un collar se advierte que vamos a someter a ese conjunto C a una serie de giros, y que consideraremos pertenecientes a un mismo collar a las permutaciones que se pueden convertir una en la otra mediante un giro.

Concretamos:

Llamemos g1 al giro que traslada cada cuenta al lugar de su siguiente en el sentido de las agujas del reloj. En términos de permutaciones equivaldría a mover cada elemento un lugar y al último convertirlo en primero. Así, en la permutación XOXXO el efecto de g1 sería OXXOX. Se puede formalizar más, pero así se entiende bien. Esta definición es independiente del número de cuentas.



Igualmente, llamaremos g2 a la composición de g1 consigo mismo, es decir g2(x)= (g1.g1)(x)=g1(g1(x)). En la práctica equivaldría a un giro doble. De igual forma podemos definir el giro triple g3(x)= (g1.g2)(x)=g1(g2(x)) y así sucesivamente hasta llegar a gn que equivaldría a la transformación identidad e.

Hemos definido en realidad un grupo G (puedes demostrarlo), el de los giros en C, subgrupo del de sustituciones de C. Formalizamos la idea:

Diremos que un grupo G actúa sobre un conjunto C cuando para cada elemento g de G se define una operación externa g(x)=y, donde x e y son elementos del conjunto C, tal que cumpla e(x)=x y además (g.f)(x)=g(f(x)), ambas para todo x de C. En nuestro caso de giros sobre permutaciones se cumplen ambas, luego diremos que G actúa sobre C. La imagen intuitiva es que se hacen girar los collares de todas las formas posibles.

Dos conceptos importantes se desprenden de esa definición

Órbita

Llamaremos órbita o trayectoria de un elemento x del conjunto C sobre el que actúa G, al conjunto orb(x) formado por todas las imágenes posibles de x mediante los elementos de G. En la imagen tienes un ejemplo de órbita según los giros en un conjunto de seis cuentas.


 Las órbitas no son subgrupos, sino subconjuntos de C. Si vuelves a leer desde el principio, entenderás que la definición de “collar” coincide con la de “órbita”

Los collares que hemos definido coinciden con las órbitas de las permutaciones si sobre ellas actúan los giros.

Hay otra definición de collar en la que entran las simetrías, pero lo dejamos por si deseas ampliar el tema.

Estabilizador

Para una permutación cualquiera x, llamaremos estabilizador de x est(x) al subgrupo de giros que la dejan invariante, es decir, todos los g tales que g(x)=x.

Es fácil demostrar que est(x) constituye un subgrupo.



Así, el estabilizador de la permutación de la imagen está formado por el subgrupo {e, g2, g4}. Si no ves simetrías aparentes en una permutación, es fácil que su estabilizador sea {e}, sólo la identidad.

Repasa algunos ejemplos y verás que es fácil encontrar su estabilizador.

¿Por qué hablamos de estabilizadores? Porque nos sirven para contar órbitas o, lo que es lo mismo, collares.

Lo dejamos para otro día. Si quieres avanzar en el tema, busca por ahí el lema de Burnside.