domingo, 27 de marzo de 2011

Collares bicolores – Conteo de collares

Los conceptos de órbita (collares en nuestro caso) y de estabilizador están relacionados por un cálculo. Si representamos como |C| al cardinal de un conjunto C, tendremos que

Si G actúa sobre un conjunto C, para cada elemento x de C se cumple que |Orb(x)|=|G|/|est(x) |

Es decir, el cardinal de la órbita de x equivale al cociente del cardinal del grupo que actúa sobre él y el de su estabilizador. 

Así, en el ejemplo de la imagen, el grupo de giros tiene cardinal 6 y en párrafos anteriores vimos que su estabilizador tiene 3, luego su órbita contendrá 6/3=2 elementos, el de la imagen y su simétrico intercambiando negras y blancas.

En los collares con n primo no existen subgrupos propios, luego todos los collares tendrán n elementos equivalentes. Estudia los collares de siete elementos y lo comprobarás.
 
Hay una forma de contar todos los collares mediante órbitas y estabilizadores. Se trata del lema o teorema de Burnside:

Sea G un grupo que actúa sobre un conjunto C, y llamemos r(g) al número de elementos de C que quedan invariantes respecto a g (x=g(x)). En ese caso el número de órbitas en C viene dado por 



Puedes consultar la demostración en textos adecuados.

Lo aplicamos al caso de collares de 6 cuentas, 3 negras y 3 blancas. Contamos los puntos fijos de cada giro:

e: Todos los elementos son fijos, contamos 20 elementos
g1, g3, g5: No tienen elementos fijos
g2, g4: Cada uno presenta 2 elementos fijos. Contamos 4

Aplicamos el teorema de Burnside: O=(20+0+4)/6 = 4 órbitas, tal como sabíamos desde el principio. Encontramos cuatro collares distintos.

En el caso que propusimos de 2 cuentas negras y 4 blancas tendríamos:

Número total de elementos: 6!/(2!.4!)= 15 permutaciones
e: Todos los elementos son fijos, contamos 15 elementos
g1, g2, g3, g5: No tienen elementos fijos
g3: Presenta 3 elementos fijos.

Luego O=(15+0+3)/6 = 3 órbitas, que se corresponden con los propuestos en nuestra primera entrada.

Puedes estudiar el caso sencillo de collares de 4 cuentas. Desarrolla por separado los casos de 3 de un color y 1 del otro o el de 2 colores de cada clase. Te deben resultar un collar del primer tipo y dos del segundo. Dibújalos si quieres.

En el caso de 7, al ser primo, no hay puntos fijos y el cálculo se reduce a dividir entre 7 el número de permutaciones. Por ejemplo, si C7,4 =C7,3 = 35, el número de collares será igual a 35/7 = 5. En el caso de 5 y 2 serían 3=21/7

Ahí los tienes todos


Son 10 en total, y si le añadimos los que resultan de intercambiar negras y blancas, se convierten en 20. Este resultado y otros similares los puedes encontrar en http://oeis.org/A000031