combinatoria con simetr´ıas - uamverso.mat.uam.es/~pablo.fernandez/cap15-burnside.pdf2 grupos de 1...

Capıtulo 15

Combinatoria con simetrıas

Las tecnicas combinatorias que hemos ido aprendiendo hasta ahora nos permiten contarobjetos sin que, en general, hayamos prestado particular atencion a su “disposicion geometri-ca”, salvo alguna incursion en las listas circulares (subsecciones 2.2.2 y 4.3.1). En este capıtulo,y luego en el capıtulo 16, nos ocuparemos de listas dispuestas geometricamente, lo que ensı no serıa una novedad si no fuera porque, con frecuencia, y a efectos practicos, algunas deesas disposiciones son equivalentes. Veamos un par de ejemplos, para empezar.

Ejemplo 15.0.1 Listas de ida y vuelta. Consideremos las 23 = 8 listas de longitud 3 conceros y unos. Podrıa ocurrir que, en cierto uso practico, las listas se leyeran indiferentementede izquierda a derecha o de derecha a izquierda.

Si fuera ası, tendrıamos que identificar las listas que se obtienen escribiendo los sımbolos enorden inverso

(0 0 0) (1 0 0) (0 1 0) (1 1 0) (1 0 1) (1 1 1)

(0 0 1) (0 1 1)

y tendrıamos unicamente 6 listas “no equivalentes”. ♣

Ejemplo 15.0.2 Listas circulares. Queremos contar el numero de listas circulares decuatro posiciones que podemos obtener con dos sımbolos distintos, a, b, de forma que nodistingamos entre dos listas si se obtiene una de otra por rotacion.

En principio, tenemos 24 = 16 formas diferentes de asignar los dos sımbolos a las cuatro po-siciones. Si listamos todas estas configuraciones, las revisamos cuidadosamente y verificamossu posible equivalencia, concluimos que, bajo el criterio anterior, solo hay 6 configuraciones“no equivalentes” (en jerga joyera, 6 collares distintos de dos colores): una con cuatro letras a,otra con cuatro letras b, una con tres letras b, otra mas con tres letras a y, por ultimo, doscon dos letras a y dos b.

a a

a a

b b

b b

b a

b b

a b

a a

b b

a a

b a

a b

Y, ¡atencion!, cualquier otra lista que podamos construir se obtiene de estas por rotacion.♣

1029

1030 Capıtulo 15. Combinatoria con simetrıas

La dificultad de esta combinatoria estriba en que las agrupaciones que hemos hecho deobjetos “equivalentes” tienen distintos tamanos. En el ejemplo de las listas de ceros y unos,las 8 de partida se agrupan de dos en dos (4 de ellas) o de una en una (las otras 4). En el de laslistas circulares, como puede comprobar el lector, las 16 listas con sımbolos a y b se agrupan en2 grupos de 1 lista, 3 grupos de 4 listas y 1 grupo de 2 listas (para dar las 6 no equivalentes).Ademas, en los ejemplos de interes, el numero de posiciones, sımbolos y operaciones deidentificacion puede ser muy grande, ası que el procedimiento casi artesanal seguido en estosejemplos no es muy adecuado. Este capıtulo nos proveera con los resultados y las tecnicasque permiten abordar estas cuestiones, que en general constan de tres ingredientes:

un conjunto X (en los ejemplos, X = 1, 2, 3 y X = vertices del cuadrado);el conjunto Y de formas de asignar ciertos sımbolos (Y = 0, 1 e Y = a, b enlos ejemplos) a los elementos de X ;y un conjunto G de operaciones de identificacion (en los ejemplos, leer de derechaa izquierda y rotar el cuadrado).

¿Que naturaleza tienen estos ingredientes? X es simplemente un conjunto. Como de cos-tumbre, los elementos concretos de X no son relevantes, y solo interesa cuantos elementoscontiene. Ası que, si |X | = n, supondremos, como es habitual, que X = 1, 2, . . . , n.

El conjunto Y sera el conjunto de todas las listas de longitud n que se pueden formar conciertos sımbolos, a los que llamaremos colores.

Finalmente, las operaciones de identificacion seran en general aplicaciones biyectivas delconjunto X en sı mismo y desempenaran un doble papel: aunque permutaran los elementosde X , lo que nos va a interesar es como identifican las listas de Y.

Ejemplo 15.0.3 Tarjetas de identificacion. Queremos disenar tarjetas para identificarclientes. Para ello, marcamos algunas de las 16 casillas de una tarjeta 4× 4.

Hay 216 tarjetas distintas (las correspondientes a marcar o no marcar cada casi-lla); a la izquierda exhibimos una de ellas.

×× × Digamos, por ejemplo, que las tarjetas

identificaran a los clientes de un aparcamiento, y que pretendemos que el lectorde tarjetas reconozca de que cliente se trata sea cual sea la posicion en que se in-

serte la tarjeta. Ası que no queremos distinguir entre configuraciones que se obtengan una deotra por rotacion. Por ejemplo, las siguientes configuraciones representarıan el mismo codigo:

×× ×

×××

× ××

×××

Y tampoco queremos distinguir entre configuraciones que se obtengan una de la otra medianteun volteo de arriba a abajo1, como por ejemplo:

×× × y ××

×1Quizas el lector eche en falta el volteo de izquierda a derecha. Medite primero sobre la relacion de este

volteo con las anteriores identificaciones y, en todo caso, siga leyendo.

(version preliminar 14 de diciembre de 2008)

1031

Con todas estas restricciones, ¿de cuantas tarjetas no equivalentes podemos disponer? Exhi-bamos, como antes, los ingredientes del problema.

El conjunto X es, en este caso, el conjunto de las 16 casillas.

Hay dos sımbolos (los “colores”), , × , marcar o no marcar cada casilla. Elconjunto Y esta formado por las 216 asignaciones de esos 2 sımbolos a las 16 casillas.

Y, por ultimo, las operaciones que identifican distintas asignaciones como una mismatarjeta son, en este caso, las rotaciones y el volteo. ♣

El objetivo de este capıtulo es ser capaz de calcular, en situaciones como las anteriores,el numero maximo de asignaciones de sımbolos que las operaciones senaladas no identifican.Este numero es, como hemos visto, 6 en los dos primeros ejemplos, y sera 16456 en el caso delas tarjetas (como comprobaremos en el ejemplo 15.3.7). Reconocera el lector que esta ultimacantidad no era tan facil de anticipar.

Ejemplo 15.0.4 Consideremos un problema inverso. La maquina del tiempo nos situa entorno a 1870. Nos interesamos por la disposicion geometrica de los 6 atomos de carbonode la molecula del benceno, cuya formula es C6H6, pues la estructura real de la moleculadeterminara muchas de sus propiedades.

Tenemos tres candidatos: que los seis atomos decarbono ocupen los vertices de un hexagono regular(como proponıa Kekule2), los de un octaedro o losde un prisma triangular recto3.

Disponemos, ademas, de informacion de caracter quımico: cuando se hace una doblesustitucion (esto es, cambiamos dos atomos de carbono por ciertos atomos –distintos– X e Y ),entonces obtenemos tres isomeros4 distintos. Nuestra intencion es utilizar esta informacionpara obtener evidencias en favor de alguno de los modelos.

♦

♦

♦

Senalemos los atomos de carbono con cırculosnegros, mientras que a X le asignaremos un sımbo-lo y a Y , un ♦. Como los atomos de carbono sonindistinguibles en cualquiera de los modelos, po-demos situar el atomo X en una cierta posicion ybuscar los posibles emplazamientos para Y . Tras un rapido analisis, llegamos a la conclusionde que el modelo del hexagono da lugar a tres configuraciones diferentes, que mostramos ala derecha. Las otras dos posiciones para el sımbolo ♦ no producen configuraciones nuevas:

2El quımico aleman Fiedrich Kekule (1829-1896) es bien conocido por haber descubierto la estructura delbenceno. En el vigesimo quinto aniversario del descubrimiento, Kekule pronuncio una conferencia en la queaseguro que su conjetura de la estructura hexagonal le llego a traves de un sueno, en el que veıa atomosde carbono enroscandose como serpientes (quizas es que Kekule se deleitaba olfateando benceno). Otrasfuentes afirman que Kekule habıa recomendado la traduccion de un libro en el que se proponıa la estructurahexagonal. Sea cual sea la verdad, las ideas de Kekule en el campo de los compuestos aromaticos tuvieronuna gran influencia en todo el desarrollo posterior de la Quımica.

3Las aristas marcadas aquı no significan necesariamente enlaces quımicos, solo disposicion espacial. Lascaras verticales del prisma, por cierto, son cuadrados.

4Se dice que unas moleculas o compuestos quımicos son isomeros cuando, teniendo la misma composicionquımica, tienen sin embargo distintas propiedades fısicas o quımicas.



son alguna de las exhibidas, salvo volteo de la figura. Para el octaedro y el prisma, comopodra comprobar el lector, solo hay dos y cinco configuraciones posibles, que mostramos enlas figuras:

♦

♦

♦ ♦

♦♦

♦

Por cierto, las dos primeras configuraciones en prisma son imagen especular una de la otra (lomismo ocurre con la tercera y cuarta). Pero dos moleculas ası tienen propiedades muy distin-tas (si lo duda el lector, consulte con su quımico de cabecera). La conclusion de este analisises que, de los modelos propuestos, solo el del hexagono es compatible con la informacion quetenıamos. Esto no basta para concluir que sea el modelo correcto (hoy, por cierto, sabemosque lo es), pero sı nos permite descartar los otros dos. Los ingredientes de este problema sonparecidos a los de los ejemplos anteriores: una serie de posiciones y unas operaciones queidentifican configuraciones (en este caso, asignaciones de sımbolos •, y ♦). ♣

Para poder abordar este tipo de problemas, necesitamos entender como actuan las iden-tificaciones que estamos considerando, y luego ser capaces de determinar cuantos objetoscoloreados distintos nos quedan tras las identificaciones. ¿Que estructura tiene el conjunto delas operaciones de identificacion? El lector perspicaz5 habra notado que entre las operacionesdel ejemplo de las tarjetas no incluimos una muy natural: el volteo de izquierda a derecha.Pero la realidad es que ya se consideraba, pues el volteo de izquierda a derecha se obtiene gi-rando 180 primero y luego volteando de arriba a abajo; y parece razonable que la aplicacionconsecutiva de dos operaciones de identificacion sea tambien una operacion de identificacion.El aparato matematico que esta detras de todo esto, al que dedicamos la siguiente seccion,es la nocion de grupo, o mas concretamente, la nocion de grupo de simetrıas de unconjunto.

15.1. Simetrıas de un conjunto. Grupos de simetrıas

Por simetrıa de un conjunto X entendemos una aplicacion biyectiva del conjunto X sobresı mismo. Al conjunto de todas las simetrıas del conjunto X lo denotaremos6 por S(X ). Comoya sabemos, en un conjunto X que tiene n elementos hay un total de n! simetrıas distintas.

El conjunto de todas las simetrıas S(X ) de un conjunto X tiene una estructura algebraicaque va a ser importante en las consideraciones que siguen, y es que forman un grupo7 bajola operacion de composicion de aplicaciones. A S(X ) se le conoce como grupo simetrico(completo) de X .

5Que ademas se lea las notas a pie de pagina.6Llamada de atencion sobre terminologıa: aquı, una rotacion es una simetrıa, lo que no se corresponde

con la nocion mas usual (y restringida) de simetrıa, que tiene que ver mas bien con la de imagen especular:simetrıa tiene aquı un significado matematico que no coincide con el del lenguaje geometrico ordinario.

7Como ya sabemos (seccion 3.2), un grupo es un conjunto en el que esta definida una operacion binariaque cumple una serie de propiedades: la operacion es cerrada, existen elementos neutro e inverso y se cumplela propiedad asociativa. En la seccion 15.6 trataremos el concepto abstracto de grupo.


15.1. Simetrıas de un conjunto. Grupos de simetrıas 1033

La composicion de g con f , que denotamos por g f , viene dada por

(g f)(x) = g(f(x)), para cada x ∈ X ,

esto es, la accion sucesiva de f primero y luego g. Ya sabemos que esta composicion esuna aplicacion biyectiva de X en sı mismo, y por tanto un elemento de S(X ). En ocasionesemplearemos la notacion fk para referirnos a la composicion de f consigo misma k veces.

El elemento neutro de S(X ) es la aplicacion identidad, que denotaremos por id, quefija cada elemento de X :

id(x) = x, para cada x ∈ X .

El inverso de una aplicacion f , que denotamos por f−1, es la aplicacion dada por

si f(x) = y entonces f−1(y) = x

para cada par de elementos x, y ∈ X . El inverso cumple que

f f−1 = f−1 f = id ,

es decir, los inversos conmutan. Pero, ¡atencion!, el grupo S(X ) nunca es conmutativo, salvocuando X tiene uno o dos elementos. Supongamos que X contiene al menos tres elementos,digamos a, b, c. Consideremos las aplicaciones f y g tales que

f(a) = a, f(b) = c, f(c) = bg(a) = b, g(b) = a, g(c) = c

y que dejan fijos los demas elementos de X , si los hubiere. Observese que

(g f)(a) = b , mientras que (f g)(a) = c

(vease tambien el ejercicio 15.1.1). Como hemos indicado, el conjunto X desempenara unpapel menor en las aplicaciones, y sus elementos seran tan solo etiquetas que usaremos paradesignar ciertos objetos; lo unico importante sera el numero de elementos de X . En esos casossera conveniente restringirse al ejemplo habitual de X = 1, 2, . . . , n.

Permutaciones y simetrıas

Recordemos que las permutaciones del conjunto X = 1, 2, . . . , n son las listas sinrepeticion con los sımbolos 1, 2 . . . , n, es decir, las (re)ordenaciones de los elementos de X .Al conjunto de las permutaciones de X lo denotamos por Perm(X ). Pero, en realidad, aplica-ciones biyectivas de un conjunto en sı mismo, simetrıas y permutaciones de un conjunto sonla misma cosa. Es el punto de vista de estudio lo que nos hace adoptar un lenguaje u otro:

aplicaciones biyectivas X → X ←→ simetrıas de X ←→ permutaciones de X

Podemos interpretar una permutacion de X como una aplicacion biyectiva de X en sı mis-mo con la siguiente correspondencia:

(2, 7, 5, 1, . . . , 6) ←→(

1 2 3 4 · · · n2 7 5 1 · · · 6

)(version preliminar 14 de diciembre de 2008)


A la izquierda exhibimos la permutacion como una lista, y a la derecha aparece su interpreta-cion como aplicacion biyectiva. De esta manera estamos identificando Perm(X ) con S(X )(observese que usamos una ordenacion, la natural, de X = 1, 2, . . . , n para esta identifica-cion. Esta identificacion sera muy util en lo que sigue y para estudiar simetrıas nos serviremosde lo que ya sabemos de permutaciones, en particular, de la descomposicion en ciclos. Porcierto, al conjunto de las simetrıas de 1, . . . , n lo denotaremos habitualmente por Sn, enlugar de S(1, . . . , n).

15.1.1. Grupos de simetrıas

Normalmente, en cada aplicacion concreta no intervendran todas las simetrıas de unconjunto, sino solo algunas que son relevantes al problema en cuestion.

Supongamos que tenemos un subconjunto G de S(X ). Decimos que G es un grupo desimetrıas de X si se cumple que:

1) si f, g ∈ G, entonces f g ∈ G;

2) si f ∈ G, entonces f−1 ∈ G.

Esto es, el subconjuntoG ha de ser cerrado bajo la operacion (la composicion de dos elementosde G ha de seguir estando en G) y contener a los inversos. Ası que G, con la operacion decomponer simetrıas, es por derecho propio un grupo8.

El orden de un grupo de simetrıas es, simplemente, el numero de elementos queincluye; ası, por ejemplo, el orden de S(X ) = n! si |X | = n.

Por supuesto, tanto G = id como G = S(X ) son grupos de simetrıas. El siguienteejemplo exhibe un caso de particular importancia:

Ejemplo 15.1.1 Grupo de simetrıas generado por un elemento g. Sea g una simetrıade orden k. Esto es, k es el menor entero positivo para el que gk = id. El conjunto < g >=id, g, g2 , . . . , gk−1 es un grupo de simetrıas de X .

La comprobacion es directa: por un lado, todas las gj son simetrıas de X , y la composicionde dos cualesquiera de ellas es otra del conjunto (basta utilizar que gk = id). Por ultimo,para cada j = 0, . . . , k, el inverso de gj es gk−j, que es una simetrıa de las del conjunto. Porcierto, < g > es un grupo conmutativo.

Hacemos notar que aquı estamos utilizando la palabra “orden” en un doble sentido: porun lado, k es el orden de g como permutacion. Pero tambien k tambien es el orden delgrupo < g >, pues este consta de exactamente k elementos. Basta comprobar que todas lasgj son permutaciones distintas. Pero es que si gs = gt, con, digamos, s > t, entonces gs−t = id,con s− t < k, lo que contradice la suposicion de que k era el orden de la permutacion g. ♣

8Se dice que G es subgrupo de S(X ). No hace falta comprobar la asociatividad, pues G es un subconjuntode S(X ). Vease tambien el ejercicio 15.6.4.



15.1.2. Algunos ejemplos de grupos de simetrıas

Empezamos con unos cuantos ejemplos que iremos empleando, a modo de ilustracion, a lolargo del capıtulo, acompanados de una interpretacion geometrica (sobre cuadrados, romboso tetraedros) que nos ayudara a entenderlos, recordarlos e identificarlos en lo que sigue.

Ejemplo 15.1.2 Rotaciones del cuadrado. Consideremos el siguiente conjunto de si-metrıas en X = 1, 2, 3, 4:

σ0 =(

1 2 3 41 2 3 4

)= 4(1) 4(2) 4(3) 4(4)

σ1 =(

1 2 3 44 1 2 3

)= 4(1 4 3 2)

σ2 =(

1 2 3 43 4 1 2

)= 4(1 3) 4(2 4)

σ3 =(

1 2 3 42 3 4 1

)= 4(1 2 3 4)

(hemos escrito a la derecha la descomposicion en ciclos de cada simetrıa/permutacion). Porrazones que se veran mas adelante, llamaremos C4 a este grupo.

C4 es un grupo de simetrıas de X , pues la composicion de cualesquiera dos elementos de C4es un elemento de C4 y los inversos son σ−1

0 = σ0, σ−11 = σ3, σ−1

2 = σ2 y σ−13 = σ1. Como

permutaciones, σ2 tiene orden 2, mientras que σ1 y σ3 tienen orden 4.

4 3

1 2 Ayuda, y mucho, considerar la siguiente interpretacion geometrica: los elemen-tos de 1, 2, 3, 4 son los vertices de un cuadrado. Y las simetrıas consideradasse corresponden con ciertos movimientos de la figura (rotaciones, en este caso).Por ejemplo, σ0 (que es la identidad en el grupo de permutaciones) se corres-

ponde con la operacion que deja el cuadrado como esta. Analicemos, por ejemplo, σ1. Comoσ1(1) = 4, moveremos el vertice 1 a la posicion del vertice 4; como σ(2) = 1, moveremos el 2al 1, etc. Es decir, σ1 es la operacion de rotar la figura 90 en sentido antihorario:

σ1

⎛⎜⎝ 1 2

34

⎞⎟⎠ =

σ1(2) σ1(3)

σ1(4)σ1(1)

De la misma manera, σ2 se corresponde con la operacion de rotar 180 en sentido antihorario,y σ3, con la de rotar 270 (que equivale a rotar 90 en sentido horario). El grupo C4 se puedeescribir como < σ1 >, es decir, es el grupo generado por σ1, la rotacion de 90 (notese queσ2

1 = σ2, σ31 = σ3 y σ4

1 = σ0 ). Y por tanto es conmutativo.Se trata de rotaciones en el plano de la figura: el eje de giro es perpendicular a ese plano,

pasa por el centro del cuadrado y los angulos de giro son antihorarios (mirando la figuradesde arriba). Las rotaciones preservan rıgidamente el cuadrado y permutan sus vertices(notese, por ejemplo, que una rotacion de angulo 60 no preserva la figura, no lleva verticesen vertices). ♣



Ejemplo 15.1.3 Isometrıas del cuadrado. El conjunto D4 = σ0, σ1, σ2, σ3, η0, η1, η2, η3,donde las σj son las simetrıas del ejemplo anterior y las ηj vienen dadas por:

η0 =(

1 2 3 44 3 2 1

)= 4(1 4) 4(2 3)

η1 = η0 σ1 =(

1 2 3 41 4 3 2

)= 4(1) 4(2 4) 4(3)

η2 = η0 σ2 =(

1 2 3 42 1 4 3

)= 4(1 2) 4(3 4)

η3 = η0 σ3 =(

1 2 3 43 2 1 4

)= 4(1 3) 4(2) 4(4)

es tambien un grupo de simetrıas de 1, 2, 3, 4.Geometricamente, η0 es la reflexion de la figura en el eje horizontal E que corta al cuadradopor la mitad. La simetrıa η1 consiste en rotar 90 antihorario y luego reflejar en E. Elefecto conjunto de estas dos operaciones es la reflexion en el eje que se senala en la figuracorrespondiente. Las otras dos simetrıas son tambien reflexiones en ejes:

E

1 2

4 3

η0 1

4 3

2η1 1

34 4

η2

3

1 2η32

Notese, por cierto, que este grupo, a diferencia de C4, ya no es conmutativo (por ejemplo,no da igual aplicar primero σ1 y luego η2 que hacerlo al reves).

De las 4! = 24 simetrıas del conjunto 1, 2, 3, 4, podemos interpretar a 4 de ellas comorotaciones del cuadrado; las 8 simetrıas del conjunto D4 son, como comprobaremos en elejemplo 15.2.5, todas las isometrıas de los vertices del cuadrado. Una isometrıa, como sunombre indica, ha de conservar las distancias entre los vertices (es decir, si x e y son vertices yγ es una isometrıa, entonces dist(γ(x), γ(y)) = dist(x, y)). Las rotaciones σi se correspondencon movimientos en el plano del papel, mientras que las ηj requieren sacar la figura del plano.Las simetrıas de 1, 2, 3, 4 no incluidas en D4 ya no conservan las distancias. Por ejemplo,

α =(

1 2 3 41 2 4 3

)= 4(1) 4(2) (3 4)

“tuerce” y deforma la figura.

1 2

4 3

α(1) α(2)

α(3) α(4)

α

Observese que α no es una isometrıa porque, por ejemplo, ladistancia entre α(2) y α(3) no coincide con la distancia entre 2 y 3. ♣

Ejemplo 15.1.4 Isometrıas del rombo.

Comenzamos ahora geometricamente. Consideremos el rombo 1

2

3

4

de la figura. A dife-rencia de lo que ocurrıa en el cuadrado, ahora la distancia entre 1 y 3 no coincidecon la distancia entre 2 y 4. El conjunto de las isometrıas del rombo (simetrıasde 1, 2, 3, 4 que preservan la estructura de distancias de la figura) tiene cuatroelementos: V = id, γ1, γ2, γ3.



Geometricamente, γ1 es la reflexion en el ejehorizontal, y γ2 la reflexion en el eje vertical.La simetrıa γ3, que es la composicion de las dosanteriores, resulta ser una rotacion de 180 gra-dos. Observese que ahora una rotacion de 90

no preserva la figura.

1

2

3

4

11

2

3

4

2

3

4

γ1 γ2

γ3

Tres operaciones que, en terminos de permutaciones, se escriben:

γ1 =(

1 2 3 43 2 1 4

)= 4(1 3) 4(2) 4(4) ,

γ2 =(

1 2 3 41 4 3 2

)= 4(1) 4(2 4) 4(3) ,

γ3 =(

1 2 3 43 4 1 2

)= 4(1 3) 4(2 4) .

Figura 15.1: Klein

El conjunto V es, efectivamente, un grupo9 de simetrıas de 1, 2, 3, 4,pues γ1 γ2 = γ3; y como las γj solo tienen ciclos de orden 1 y 2,cumplen que γ2

j = id, por lo que cada elemento es su propio inverso. Ellector podra verificar que se trata de un grupo conmutativo (aunque noesta generado por un unico elemento, pues no hay elementos de orden 4).La comprobacion de que estas son todas las isometrıas del rombo (noteseque hay menos que en el cuadrado) es directa: si g es una isometrıa delrombo, como g(1) y g(3) han de estar a la misma distancia que 1 y 3,necesariamente tendran que estar en la diagonal mayor. Es decir, o bieng deja fijos 1 y 3, o bien los intercambia. Lo mismo ocurre con 2 y 4. Lascuatro posibles combinaciones de dejar fijo o permutar los dos pares devertices se corresponden con los cuatro elementos de V.

Es instructivo considerar ahora un grupo de simetrıas V = γ0, γ1, γ2, γ3 del conjuntoX = 1, 2, . . . , 8, los vertices del cubo. Las simetrıas son las siguientes: γ0 es la identidad;γ1 es la reflexion en un plano horizontal que corta la figura por la mitad, γ2 la reflexion enun plano vertical; y γ3 = γ1 γ2, la composicion de las dos anteriores, resulta ser un giro de180 grados en torno al eje de la figura:

1

2 3

4

5

6 7

8

1

2 3

4

5

6 7

8

1

2 3

4

5

6 7

8

γ1 γ2 γ3

9La “V” del nombre del grupo proviene de Vierergruppe, 4-grupo en aleman. Habitual-mente se le conoce como grupo de Klein, en honor del matematico aleman Felix Klein(1849-1925), que desde Leipzig y Gottingen establecio conexiones fundamentales entre laGeometrıa y la Teorıa de grupos, arrancando el programa de Erlangen. El extrano objetoque reproducimos a la derecha lleva tambien su nombre: es la botella de Klein, que sepuede formar uniendo los extremos de un cilindro con un giro un tanto especial.



Tal y como se han etiquetado los vertices del cubo, las simetrıas se escriben

γ1 =(

1 2 3 4 5 6 7 85 6 7 8 1 2 3 4

)= 8(1 5) 8(2 6) 8(3 7) 8(4 8) ,

γ2 =(

1 2 3 4 5 6 7 84 3 2 1 8 7 6 5

)= 8(1 4) 8(2 3) 8(5 8) 8(6 7) ,

γ3 =(

1 2 3 4 5 6 7 88 7 6 5 4 3 2 1

)= 8(1 8) 8(2 7) 8(3 6) 8(4 5) .

Veamos: son grupos de simetrıa distintos, pues V es de 1, 2, 3, 4, mientras que V esde 1, 2, . . . , 8. Ahora bien, si unicamente nos fijamos en los elementos del grupo y suscomposiciones, esto es, si miramos las tablas de composiciones de los dos grupos:

V id γ1 γ2 γ3

id id γ1 γ2 γ3

γ1 γ1 id γ3 γ2

γ2 γ2 γ3 id γ1

γ3 γ3 γ2 γ1 id

V id γ1 γ2 γ3

id id γ1 γ2 γ3

γ1 γ1 id γ3 γ2

γ2 γ2 γ3 id γ1

γ3 γ3 γ2 γ1 id

descubrimos que ambas son, esencialmente, la misma: un simple cambio de nombres γi ←→ γi

nos lleva una en otra. Decimos entonces que estos dos grupos de simetrıas son isomorfos,es decir, son “iguales” salvo un cambio de nombres de los elementos. En el apendice 15.6elaboraremos con algo mas de detalle este concepto. ♣

Ejemplo 15.1.5 El conjunto J = id, η0, donde η0 = 4(1 4) 4(2 3).

Como en el ejemplo 15.1.3, podemos interpretar la permutacion η0 como lareflexion el eje horizontal del cuadrado. La tabla del grupo J aparece a la iz-quierda;

id η0

id id η0

η0 η0 id en ella, lo unico relevante es que hay dos elementos con los productosque allı aparecen, cuyos productos son los que se indican la tabla. ♣

Ejemplo 15.1.6 El grupo de rotaciones del tetraedro.

Tratamos ahora una figura tridimensional, como es el tetraedro quedibujamos a la derecha. Las rotaciones a las que nos referimos sonrotaciones en el espacio R3 alrededor del origen, sobre las que habla-remos largo y tendido en el apendice 15.7. Describir una tal rotacionen R3 requiere fijar un eje que pase por el origen y un angulo degiro en torno al mismo.

1

2

3

4

Ahora situamos el centro geometrico deltetraedro (el baricentro) en el origen de coordenadas (0, 0, 0) y consideramos rotaciones delespacio que preservan la figura. Por ejemplo, una clase de ellas tienen como eje el que une elvertice 1 con el origen y, como angulos, 120 y 240 (por ejemplo, en sentido horario). Comopermutaciones, estas operaciones se escriben(

1 2 3 41 3 4 2

)= 4(1) 4(2 3 4)

(1 2 3 41 4 2 3

)= 4(1) 4(4 3 2)



(basta seguir la pista a los vertices por las operaciones). Analogamente, encontramos paresde rotaciones con ejes que pasan por los vertices 2, 3 y 4. Ocho, en total.

1

2

3

4

π

Pero hay otras rotaciones, quizas no tan evidentes a primera vista.Por ejemplo, la que tiene como eje la recta que pasa por los puntosmedios de aristas opuestas y, como angulo, π. La rotacion que dibu-jamos a la izquierda intercambia los vertices 1 y 2 y los vertices 3y 4, ası que se escribe, como permutacion, de la siguiente manera:(

1 2 3 42 1 4 3

)= 4(1 2) 4(3 4) .

De estas hay tres rotaciones (los tres posibles ejes); unidas a las ocho que describıamos antesy a la identidad, hacen un total de doce simetrıas. Quizas el lector quiera cerciorarse de que,efectivamente, estas 12 permutaciones forman un grupo de simetrıas de 1, 2, 3, 4, algo nadaobvio, comprobando a mano que los inversos estan en el conjunto y que la composicion decada dos de ellas es otra del conjunto. Aunque quizas prefiera consultar la discusion del finalde la subseccion 15.1.3 y/o esperar al ejemplo 15.2.3, cuando comprobaremos que solo las 12rotaciones que hemos exhibido preservan el tetraedro. ♣

Podrıa parecer que todo subconjunto mas o menos razonable del grupo simetrico es ungrupo de simetrıas, pero no es ası.

Ejemplo 15.1.7 El subconjunto In de Sn esta formado por las involuciones10 de 1, . . . , n,es decir, las aplicaciones biyectivas f de 1, . . . , n en sı mismo tales que f2 = id (las apli-caciones que son su propio inverso). Pues bien, el conjunto In no es un grupo de simetrıas.

En realidad, sı que lo es para n = 1, 2, pues I1 = id e I2 = S2, que son grupos de simetrıas.Pero para n ≥ 3, ya no es un grupo de simetrıas. Analizaremos el caso n = 4, que es con elque hemos estado tratando en paginas anteriores, y dejamos al lector que se convenza11 porsı mismo de lo que ocurre en el caso n = 3. Tomemos, por ejemplo, las permutaciones

η0 =(

1 2 3 44 3 2 1

)= 4(1 4)4(2 3) y α =

(1 2 3 41 2 4 3

)= 4(1)4(2)(3 4) ,

que veıamos en el ejemplo 15.1.3. Como ambas constan unicamente de ciclos de longitud 1o 2, son obviamente involuciones. Sin embargo, la composicion η0 α no esta en I4; es decir,su cuadrado no es la identidad:

η0 α =

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩1 α−→ 1

η0−→ 4

2 α−→ 2η0−→ 3

3 α−→ 4η0−→ 1

4 α−→ 3η0−→ 2

=(

1 2 3 44 3 1 2

)= 4(1 4 2 3)

Como η0 α consta de un unico ciclo de orden cuatro, no puede ser una involucion (losciclos habrıan de ser de orden 1 y/o 2). De hecho, (η0 α)2 = 4(1 2) 4(3 4) = id, como

10En el ejercicio 3.2.4 pedıamos calcular el numero de involuciones de 1, . . . , n, es decir, el tamano de In.11¿Y el caso n ≥ 5? Siga leyendo, por favor.



podra comprobar el lector. Por supuesto, una vez que hemos visto que I4 no es un grupode simetrıas, lo tenemos probado para todo In, n ≥ 4, pues podrıamos argumentar con loselementos de In que son como η0 y α sobre los elementos 1, 2, 3 y 4 y que fijan el resto12.

Si el lector tuviera a bien entretenerse con los detalles del ejercicio 15.1.3, descubrirıaotro conjunto de permutaciones muy natural, las permutaciones impares, que no forman ungrupo de simetrıas (aunque las pares sı). ♣Ejemplo 15.1.8 Las rotaciones del prisma del ciclopropano C3H6.

Consideremos el grafo que dibujamos a la izquier-da, que consideramos como un objeto rıgido de R3.Hay tres vertices de grado 4 y seis de grado 1. Estegrafo codifica la estructura de enlaces de la molecu-la del ciclopropano si en los nodos de grado 4 pone-mos atomos de carbono, y en los de grado 1, atomosde hidrogeno, como en el otro dibujo.

Es de sumo interes para los quımicos analizar la equivalencia de lasestructuras que se obtienen al reemplazar los atomos de hidrogeno porotros tipos de atomos (recuerdese la discusion sobre el benceno del ejem-plo 15.0.4). Para ello, sera conveniente considerar el prisma recto, conbase un triangulo equilatero, que tiene seis vertices, como en la figura.

a

b cEl

baricentro de la figura se situa en el origen de R3 y el triangulo marcadocon a, b y c esta justamente a mitad del prisma. Consideramos las seisrotaciones (en torno al origen) en el espacio siguientes: la identidad, losgiros alrededor del eje OZ y angulos 2π/3 y 4π/3, y los giros de angulo πde ejes que pasan (en el triangulo abc) por cada vertice y por el centro de cada lado opuesto.Estas seis rotaciones son permutaciones de 1, 2, . . . , 6, los vertices del prisma, y forman ungrupo, lo que no es del todo obvio (vease el ejemplo 15.2.7). De hecho, son justamente lasrotaciones de R3 alrededor del origen que preservan los 6 vertices del prisma. ♣

15.1.3. Acciones inducidas sobre subconjuntos

Digamos que tenemos un grupo de simetrıas G de X . Una situacion especialmente rele-vante es aquella en la que G preserva un cierto subconjunto Y ⊂ X (o, en pasiva, que Y esestable bajo G). Es decir,

g(y) ∈ Y para todo g ∈ G y todo y ∈ Y.

Por ejemplo, en la figura del hexagono,

1 2

3

45

6

podemos considerar el grupo Gformado por la identidad y las rotaciones de angulos 2π/3 y 4π/3, ope-raciones que, escritas como permutaciones de X = 1, 2, 3, 4, 5, 6, son:(

1 2 3 4 5 61 2 3 4 5 6

),

(1 2 3 4 5 65 6 1 2 3 4

),

(1 2 3 4 5 63 4 5 6 1 2

).

12¡Atencion!, el conjunto de todas las involuciones no es un grupo de simetrıas. Pero puede haber grupos desimetrıas G tales que g2 = id para todo g ∈ G: por ejemplo, el grupo V del ejemplo 15.1.4.



Compruebe el lector que, efectivamente, se trata de un grupo de simetrıas. Observe tambienque G preserva el subconjunto Y = 2, 4, 6. Y tambien el 1, 3, 5, pero no, por ejemplo, elconjunto 1, 2, 3.

Si G preserva Y, entonces podemos tambien entender G (su restriccion sobre los elementosde Y, en realidad) como permutaciones de Y, elementos de S(Y). En el ejemplo del hexagono,con Y = 2, 4, 6, estas permutaciones serıan(

2 4 62 4 6

),

(2 4 66 2 4

),

(2 4 64 6 2

).

Pero mas aun, G (o, mas bien, su restriccion a Y) es un grupo de simetrıas de Y, comopodra comprobar el lector (basta convencerse de que g h, g−1 y h−1 preservaran Y sitanto g como h lo hacen).

Nos referiremos a esta situacion como la “accion inducida” de G sobre Y. Se trata de uncaso particular de una nocion mas general (acciones de grupos sobre conjuntos), que volvera aaparecer en las siguientes paginas, y que trataremos con mas profundidad en la seccion 15.6.1.

Pero ¡atencion!, la cuestion es algo mas sutil de lo que pudiera parecer. Digamos queX = 1, 2, . . . , 6 y que G es el conjunto de permutaciones con la siguiente estructura:(

1 2 3 4 5 6− − − ∗ ∗ ∗

).

donde en −−− ponemos cualquier permutacion de 1, 2, 3 y en ∗∗∗, cualquiera de 4, 5, 6.Se trata de un grupo de simetrıas de X con 6 × 6 = 36 elementos. El grupo G preserva1, 2, 3, desde luego. Y, por tanto, G se puede entender como grupo de simetrıas de 1, 2, 3.Pero ahora solo tiene 6 elementos (cada seis simetrıas originales se agrupan para dar una).

Digamos que G es un grupo de simetrıas de X que preserva un cierto Y ⊂ X . Decimosque la accion inducida sobre Y es fiel si, dadas cualesquiera g1, g2 ∈ G distintas, ocurre queg1 y g2, como simetrıas de Y, siguen siendo distintas. Como aquı se trata de Combinatoria,de contar, las acciones fieles son muy relevantes, pues en ese caso, al considerar G como grupode simetrıas de Y, no hay duplicidades.

Lema 15.1 Sea G un grupo de simetrıas de X que preserva un subconjunto Y ⊂ X . Laaccion de G sobre Y es fiel si la unica g ∈ G tal que

g(y) = y para todo y ∈ Y (es decir, fija todos los elementos de Y)

es la identidad (de G).

Demostracion. Supongamos que dos permutaciones g1 y g2 coinciden en Y. Es decir,g1(y) = g2(y) para todo y ∈ Y. Entonces g−1

2 g1(y) = y para todo y ∈ Y. Pero enton-ces, por hipotesis, g−1

2 g1 = idG. Ası que g1 = g2 como permutaciones de X . Y la accion esfiel.



Estabilizador de un (sub)conjunto

La situacion mas habitual con la que nos encontraremos es la siguiente: G es un grupo desimetrıas de X y tenemos un cierto subconjunto Y ⊂ X . Definimos el conjunto de simetrıas

EG(Y) = g ∈ G : g(y) ∈ Y para toda y ∈ Y ,

es decir, el conjunto de todas las simetrıas de G que preservan Y. A este conjunto le llama-remos el estabilizador de Y por G (lo que explica, en cierta medida, el aparatoso sımboloelegido, EG(Y)).

En muchas ocasiones, el estabilizador puede ser simplemente la identidad. Por ejemplo, siinterpretamos X = 1, 2, 3, 4 como los vertices del cuadrado y consideramos las rotaciones,solo la identidad preserva el subconjunto Y = 1, 2.

Este estabilizador es, primero, un grupo de simetrıas de X . Pero, al restringirlo a Y, estambien un grupo de simetrıas de Y (vease el ejercicio 15.1.2). Aunque de nuevo podemosencontrarnos con que EG(Y) tenga mas elementos visto como grupo de simetrıas de X quecomo grupo de simetrıas de Y. Siguiendo en el cuadrado con las rotaciones, consideremos elgrupo formado por la identidad y la reflexion en un eje diagonal (por ejemplo, la diagonalentre los vertices 2 y 4). El grupo G preserva tanto el subconjunto 1, 3 como el 2, 4. Pero

EG(1, 3) = G mientras que EG(2, 4) = id

En el primer caso, la accion es fiel, pero en el segundo no.Un caso que sera especialmente interesante es aquel en el que Y consta unicamente de

un elemento, Y = x0. Hablaremos en este caso del estabilizador del elemento x0 por Gy usaremos, por sencillez, la notacion EG(x0) (en lugar de la mas correcta, aunque masaparatosa, EG(x0)).

Grupo de rotaciones de una figura

A lo largo del capıtulo trataremos rotaciones en el espacio R3 en torno al origen. Estasrotaciones forman un grupo (lo que no es ni mucho menos obvio) que va por la vida con elcurioso nombre de SO(3). El lector interesado podra encontrar un analisis detallado de estasrotaciones en el apendice 15.7, aunque por ahora apelaremos solo a la intuicion, que nos diceque una rotacion esta determinada por un eje (de giro) y un angulo.

Observese que se trata de un grupo infinito, que actua sobre todo R3, tambien un conjuntoinfinito. Esto se sale del marco que estamos considerando hasta ahora, pero apelamos al lectorcompasivo a que acepte los argumentos que proponemos a continuacion.

Consideremos ahora una figura, es decir, un conjunto finito X de R3 con al menos treselementos no alineados (esto es, no estan en una misma recta que pasa por el origen). Podrıanser los vertices de un solido platonico, los de un pentagono, los del prisma del ciclopropano ocualquier otra cosa que se le pueda ocurrir. Definimos G como el conjunto de las rotacionesdel espacio que preservan X , el estabilizador de X por G. Normalmente, este conjunto cons-tara unicamente de la identidad, pues para que el conjunto sea preservado por una rotacion,como imaginara el lector, los puntos deberan formar una configuracion muy especial. Pero,



en todo caso, G es un grupo de simetrıas de X , al que nos referiremos como el grupo derotaciones de X (o del nombre de la figura que estemos considerando).

Como una rotacion que fija tres puntos no alineados es necesariamente la identidad, ape-lando al lema 15.1, la accion del grupo de rotaciones sobre X sera fiel: si g1 y g2 son dosrotaciones distintas, tambien lo seran como biyecciones de X . Observese que G es necesaria-mente finito (de hecho, |G| ≤ |X |!).

EJERCICIOS DE LA SECCION 15.1

15.1.1 El grupo simetrico completo Sn, con n ≥ 3, no solo no es conmutativo, sino que si g ∈ Snno es la identidad, entonces hay alguna h ∈ Sn que no conmuta con g, es decir, g h = h g. (En lanotacion que aparecera en el apendice 15.6, el centro del grupo simetrico Sn, n ≥ 3, solo contiene ala identidad). Compruebese.

15.1.2 Sea G un grupo de simetrıas de X y sea Y un subconjunto de X . Compruebese que elestabilizador de Y por G, EG(Y), es un grupo de simetrıas (tanto de X como de Y).

15.1.3 En Sn, n ≥ 2, se define el subconjunto de permutaciones

An = g ∈ Sn : signo(g) = 1 ,

es decir, el conjunto de las permutaciones pares. Sabemos (vease el ejercicio 3.2.8) que |An| = n!/2.Demuestrese que An es un grupo de simetrıas de 1, . . . , n, el llamado grupo alternado. Com-pruebese que, sin embargo, el conjunto de las permutaciones impares no es un grupo de simetrıas.

15.1.4 G es un grupo de simetrıas de X = x1, . . . , xn y H es un grupo de simetrıas de Y =y1, . . . , ym. Los conjuntos X e Y son disjuntos. Para cada g ∈ G y h ∈ H, definimos una simetrıadel conjunto X ∪ Y con la siguiente regla:

(g, h)(t) =g(t) , si t ∈ X ,h(t) , si t ∈ Y.

Llamemos G×H al conjunto de todas las simetrıas (g, h). Compruebese que es un grupo de simetrıasde X ∪ Y (el llamado grupo producto).

15.1.5 En el tetraedro que dibujamos en el ejemplo 15.1.6, si situamos el baricentro en el ori-gen (0, 0, 0) del espacio, ¿cuales son las coordenadas cartesianas de los vertices?



15.2. Orbitas y puntos fijos. Lema cuenta-orbitas de Burnside

Sea G un grupo de simetrıas de un conjunto X . Para abordar los problemas que anun-ciabamos al principio de este capıtulo, nos va a interesar entender G como un grupo desimetrıas de un conjunto Y de asignaciones de sımbolos a los elementos de X . Pero antessera conveniente analizar como mueve G los propios elementos del conjunto X .

15.2.1. Orbitas y puntos fijos

Empezamos fijando un elemento x ∈ X y siguiendo la pista que deja por la accion detodas las simetrıas de G. Para cada x ∈ X , la orbita de x por G, a la que nos referiremos13

como OG(x), es el conjunto de las imagenes de x mediante G:

OG(x) = g(x) : g ∈ G .Observese que el propio elemento x siempre pertenece a OG(x), pues x = id(x) (y la identidadesta en G, que es un grupo de simetrıas).

Si el lector analiza los grupos de simetrıas que hemos definido antes en el conjunto X =1, 2, 3, 4, descubrira que, por ejemplo, las orbitas de los elementos 1 y 2 son, para cada unode los grupos en cuestion,

OI(1) = 1 , OJ (1) = 1, 4 , OV(1) = 1, 3 , OC4(1) = OD4(1) = OS4(1) = 1, 2, 3, 4 .OI(2) = 2 , OJ (2) = 2, 3 , OV(2) = 2, 4 , OC4(2) = OD4(2) = OS4(2) = 1, 2, 3, 4 .Ası que el tamano de una orbita puede oscilar entre 1 (como ocurre, por ejemplo, para elgrupo I) y el numero total de elementos de X (como sucede con C4, D4 y, por supuesto, S4).Como veremos mas adelante (en el lema 15.4), el tamano de cualquier orbita divide al ordendel grupo que estemos considerando. Pero ahora no es el tamano de las orbitas lo que importa,sino la estructura que determinan. Fijemonos, por ejemplo, en el grupo V = id, γ1, γ2, γ3de simetrıas de X = 1, 2, 3, 4, donde

γ1 =(

1 2 3 43 2 1 4

), γ2 =

(1 2 3 41 4 3 2

), γ3 =

(1 2 3 43 4 1 2

)La orbita del 1 es 1, 3, la del 2 es 2, 4, la del 3 vuelve a ser 1, 3, mientras que la del 4es otra vez 2, 4. En este caso, las orbitas, o son iguales, o son disjuntas.

yz

x

OG(x)

OG(y)

No es una casualidad. Argumentemos en general: tenemos unconjunto X y un grupo G de simetrıas de X . Consideremos doselementos x, y ∈ X y sus orbitas respectivas, OG(x) y OG(y).Afirmamos que si las dos orbitas tienen interseccion, entoncesson la misma. Lo “vemos” graficamente: supongamos que uncierto z ∈ X esta en la interseccion de las dos orbitas, como enel dibujo. En OG(x) estan todos los elementos de X a los quese puede “ir” desde x mediante una simetrıa de G; entre ellos

esta z. Pero a z tambien se puede llegar desde y, ası que va a existir una manera de ir de xa y mediante alguna simetrıa de G; y esto supone que y ha de pertenecer a OG(x).

13Algunos textos utilizan el sımbolo G(x) para describir la orbita de un elemento x por la accion de G.


15.2. Orbitas y puntos fijos. Lema cuenta-orbitas de Burnside 1045

Mas formalmente, probemos, por ejemplo, que OG(x) ⊆ OG(y). Como z esta en ambasorbitas, existiran g1, g2 ∈ G tales que z = g1(x) = g2(y). Ahora tomemos un w ∈ OG(x)cualquiera y probemos que pertenece tambien a OG(y). Se tendra que w = g3(x), para ciertog3 ∈ G. Y entonces

w = g3(x) = g3 g−11 (z) = g3 g−1

1 g2(y) .Ya lo tenemos: como G es un grupo de simetrıas, la composicion g3 g−1

1 g2 es otro elementode G, el que permite “llegar” a w desde y. Ası que w tambien esta en la orbita de y. El lectorpodra probar sin dificultad la otra inclusion14.

Las orbitas (distintas) por G son una particion en bloques del conjunto X . Es decir, Gdetermina una relacion de equivalencia R en el conjunto X , cuyas clases de equivalenciason las distintas orbitas, y que viene dada por

xR y ⇐⇒ existe algun g ∈ G tal que y = g(x).

Es decir, dos elementos de X estan relacionados si hay alguna simetrıa en G que lleve unoen otro. Compruebe el lector que se trata de una relacion de equivalencia y que las clases deequivalencia son, precisamente, las distintas orbitas.

Figura 15.2: Burnside

Como los ejemplos del principio del capıtulo sugieren, mas ade-lante identificaremos todos los elementos de una misma orbita (puesestaran relacionados mediante simetrıas de G). Ası que interesa calcu-lar el numero de orbitas (o clases de equivalencia) que G determinaen X . Un resultado de Burnside, al que nos referiremos como15 el le-ma cuenta-orbitas y que presentaremos a continuacion, nos dara unprocedimiento para calcular ese numero de orbitas.

Para enunciarlo necesitamos definir un nuevo concepto, el de puntofijo de una simetrıa: dada una simetrıa g y un elemento x ∈ X ,diremos que x es un punto fijo de g si g(x) = x.

Denotemos por F (g) al conjunto de todos los puntos fijos deuna simetrıa g; |F (g)| sera el numero de puntos fijos de la simetrıa g.

Por ejemplo, en el caso del cuadrado, la simetrıa η0, la reflexion en el eje horizontal, no tienepuntos fijos, mientras que η1, la reflexion en el eje que pasa por 1 y 3, fija, precisamente,estos dos elementos: F (η1) = 1, 3. Si X = 1, . . . , n y pensamos en las simetrıas comopermutaciones de 1, . . . , n, entonces el numero de puntos fijos de una permutacion es elnumero de ciclos de orden 1 que tiene. Los desbarajustes son, simplemente, las simetrıas sinpuntos fijos.

14O, si tiene la suficiente soltura, intentar un argumento directo: si z = g1(x) = g2(y), entonces

OG(x) = g(x) : g ∈ G = g g−11 (z) : g ∈ G = g g−1

1 g2(y) : g ∈ G .

Basta comprobar que, cuando g recorre G, h = g g−11 g2 tambien lo hace, para deducir que el ultimo

conjunto es, simplemente, OG(y).15Solo una denominacion, porque en realidad no es al ingles William Burnside (1852-1927) a quien ha de

atribuirse su paternidad. Frobenius y Cauchy, anos antes, ya eran conscientes de el. Burnside incluyo esteresultado en 1897 en su libro Theory of Groups of Finite Order, que tuvo una influencia considerable en eldesarrollo del area. Por cierto: ¡quiero un lema! ¡Cuantos lemas famosos, tan utiles, hay en Matematicas! Noson teoremas, pero. . .



Hemos cambiado el punto de vista: en las orbitas interesaba seguir la pista de cadaelemento x ∈ X por las simetrıas de G; ahora miramos, dada una simetrıa, cuantos elementosde X fija. Pronto veremos como conciliar estos dos puntos de vista, aparentemente dispares.

15.2.2. El lema cuenta-orbitas de Burnside

Con estas definiciones ya podemos enunciar el siguiente resultado, que relaciona, quizassorprendentemente, los dos conceptos explicados antes.

Lema 15.2 (Burnside) Si G es un grupo de simetrıas de un conjunto X , el numero deorbitas distintas de G viene dado por

# orbitas distintas =1|G|

∑g∈G

|F (g)|

En palabras, el lema de Burnside afirma que

el numero de orbitas distintas que G determina en X coincide con el numeromedio de puntos fijos de las simetrıas en G.

Elegante, a la par que sencillo y sugerente: para contar lo distinto (a la izquierda), debemoscentrarnos en lo inmutable16 (derecha). Para demostrar este resultado (lo que haremos enla subseccion 15.2.3), necesitamos un concepto adicional, que ya adelantamos en la subsec-cion 15.1.3, y que sirve de puente entre las orbitas y los puntos fijos.

Dado un elemento x de X , el estabilizador de x por G es el conjunto de las simetrıasde G que fijan el elemento x; lo denotaremos17 por EG(x). En formula,

EG(x) = g ∈ G : g(x) = x .

¡Atencion!, la orbita de un elemento x, OG(x), es un subconjunto de X . Pero el estabilizadorde x, EG(x), es un subconjunto del grupo de simetrıas G (y, como ya sabemos, es un grupo desimetrıas de X ). Por ejemplo, si G = D4, las unicas simetrıas que fijan el elemento 1 son σ0 yη1 (que forman tambien un grupo de simetrıas). Como veremos en el lema 15.4, los tamanosde la orbita OG(x) y del estabilizador EG(x) estan muy relacionados. Empezamos con:

Lema 15.3 Dado x ∈ X , para cualquier y ∈ X ,

#h ∈ G : h(x) = y =|EG(x)| si y ∈ OG(x);

0 si y /∈ OG(x);

Es decir, el numero de simetrıas que envıan x a y es, o bien 0 (si y no esta en la orbitade x), o bien coincide con el numero de simetrıas que fijan el elemento x (el tamano desu estabilizador). Quizas pueda sorprender que a la derecha aparezca una cantidad que nodepende de y. Pero es que si x e y pertenecen a la misma orbita, entonces, cambiando los

16¡Que filosofico! Puro Zen.17Otra notacion habitual para el estabilizador de un elemento x por G es Gx.



papeles de x e y en el lema anterior y comprobando que, por cada simetrıa que envıa x en yhay una que envıa y en x, deducimos que los tamanos de sus estabilizadores coinciden. Esdecir, que

OG(x) = OG(y) =⇒ |EG(x)| = |EG(y)| .

Demostracion. Tenemos x ∈ X fijo y nos dan un y ∈ OG(x). Existira entonces ciertog1 ∈ G tal que y = g1(x). Ahora escribimos los dos conjuntos de simetrıas que nos interesan:

A = h ∈ G : h(x) = y y EG(x) = g ∈ G : g(x) = x .

Queremos comprobar que ambos conjuntos tienen el mismo cardinal, y para ellos construi-remos una biyeccion entre ambos. Esa biyeccion asocia a cada h ∈ A la simetrıa g = g−1

1 h,que cumple que

g(x) = (g−11 h)(x) = g−1

1 (h(x)) = g−11 (y) = x ,

y, por tanto, es una simetrıa de EG(x). El lector podra comprobar sin dificultad que se tratade una biyeccion entre los dos conjuntos (la asociacion inversa es g → h = g1 g).

La clave de la demostracion del lema de Burnside es el resultado siguiente, en el que seprofundiza en la relacion entre la orbita y el estabilizador de un elemento.

Lema 15.4 Para cualquier x ∈ X ,

|G| = |EG(x)||OG(x)|

En particular, |OG(x)| = |OG(y)| si y solo si |EG(x)| = |EG(y)|.

Notese que en el lema anterior exigıamos que OG(x) = OG(y) para poder concluir que|EG(x)| = |EG(y)|; ahora vemos que basta con que |OG(x)| = |OG(y)|.Demostracion. Vamos a proceder por doble conteo. Fijemos un elemento x de X . Formamosuna matriz M de ceros y unos que tiene las filas etiquetadas por las simetrıas de G y lascolumnas etiquetadas por los elementos de X . Ası que M tiene |G| filas y |X | columnas. Paracada g ∈ G e y ∈ X , en la posicion (g, y) ponemos un 1 si g(x) = y, y un 0 en caso contrario.

Contamos primero, por filas, el numero de unos que hay en M . En la fila correspondientea la simetrıa g hay exactamente un 1, justo en la columna etiquetada con el elemento g(x).Por tanto, el numero total de unos en la matriz M es |G|.

Ahora contamos por columnas. Digamos que y es la etiqueta de una cierta columna.

Si y esta en la orbita de x, entonces en esa columna hay tantos unos como simetrıas ghaya en G tales que g(x) = y. Por el lema 15.3, habra |EG(x)| unos. Y esto se cum-plira para cada y que este en la orbita de x.

si y /∈ OG(x), entonces solo habra ceros en su columna.

Ası que, contando por columnas, el numero de unos en la matriz M es |OG(x)| (el numero deelementos en la orbita de x) por |EG(x)| (el numero de unos que aporta cada fila etiquetadacon un elemento de la orbita de x).



Para completar la preparacion para la prueba del lema cuenta-orbitas, falta un ultimoingrediente: la relacion entre estabilizadores y puntos fijos:

Lema 15.5 Sea un conjunto X y sea G un grupo de simetrıas. Entonces,∑g∈G

|F (g)| =∑x∈X|EG(x)| .

Demostracion. Es, de nuevo, un argumento de doble conteo: formamos una matriz M conlas filas etiquetadas por los elementos de G y las columnas etiquetadas por los de X . En laposicion (g, x) ponemos un 1 si g(x) = x y un 0 en caso contrario. El numero total de unos,contando primero por filas, es ∑

g∈G

|F (g)| ,

porque la fila etiquetada con g aporta tantos unos como puntos fijos tenga g. Y si contamospor columnas obtenemos que ∑

x∈X|EG(x)| ,

porque la columna etiquetada con x aporta tantos unos como simetrıas haya que lo dejenfijo, esto es, tantos como el tamano de su estabilizador.

15.2.3. Demostracion del lema de Burnside

Completamos la maquinaria que necesitamos para probar el lema de Burnside con unresultado (casi obvio) sobre particiones de conjuntos: supongamos que partimos el conjuntoX = 1, 2, 3, . . . , 10 en tres conjuntos no vacıos, A1 = 1, 2, 3, 4, 5, A2 = 6, 7, y A3 =8, 9, 10. Llamemos a(x) al tamano del bloque de la particion en el que x esta incluido. Ennuestro ejemplo,

a(1) = a(2) = a(3) = a(4) = a(5) = 5 ,a(6) = a(7) = 2 ,a(8) = a(9) = a(10) = 3 .

La observacion (casi trivial) es que si sumamos los inversos de todos estos numeros (eso suponesumar 5 veces 1/5, dos veces 1/2 y 3 veces 1/3) obtenemos 3, el numero de subconjuntos dela particion. Elevemos esta observacion a la categorıa de lema:

Lema 15.6 Sea A1, A2, . . . , An una particion de un conjunto X , donde cada conjunto Ai esno-vacıo. Para cada x ∈ X , denotemos por a(x) el tamano del bloque de la particion quecontiene a x. Entonces,∑

x∈X

1a(x)

= n = Numero de subconjuntos en la particion.

Demostracion. Basta con escribir∑x∈X

1a(x)

=n∑

i=1

∑x∈Ai

1a(x)

=n∑

i=1

( ∑x∈Ai

1|Ai|

)=

n∑i=1

1 = n .



Si aplicamos ahora este lema al caso de la particion en orbitas de un grupo de simetrıas Gactuando sobre un conjunto X , podemos concluir que∑

x∈X

1|OG(x)| = # orbitas distintas de G .

¡Por fin!, tras tantos lemas previos, podemos rematar la prueba del lema de Burnside, queafirma que

# orbitas distintas de G =1|G|

∑g∈G

|F (g)| .

Demostracion (del lema de Burnside). Utilizamos primero el lema 15.5 para escri-bir que

1|G|

∑g∈G

|F (g)| = 1|G|

∑x∈X|EG(x)| .

Ahora utilizamos que, segun el lema 15.4, para todo x ∈ X , |EG(x)||OG(x)| = |G|:

1|G|

∑g∈G

|F (g)| = 1|G|

∑x∈X

|G||OG(x)| =

∑x∈X

1|OG(x)| .

Finalmente, con la observacion que seguıa al lema 15.6, terminamos la demostracion, porque

1|G|

∑g∈G

|F (g)| =∑x∈X

1|OG(x)| = # orbitas distintas de G .

15.2.4. Version ponderada del lema de Burnside

La siguiente generalizacion del lema de Burnside sera muy util mas adelante, cuandotratemos la Teorıa de Polya (capitulo 16).

Lema 15.7 (Burnside ponderado) G un grupo de simetrıas de un conjunto X . Sea p unafuncion real (el peso o ponderacion) definida en X y constante sobre cada orbita de G.Es decir, dado x ∈ X ,

p(x) = p(g(x)), para cada g ∈ G.

Digamos que hay l orbitas. Entonces, si escogemos un elemento de cada una de las orbitas,digamos x1, x2, . . . , xl,

l∑j=1

p(xj) =1|G|

∑g∈G

( ∑x∈F (g)

p(x)

)

Si tomamos como funcion de ponderacion la funcion que vale 1 para cada elemento de Xrecuperamos el enunciado usual del lema de Burnside, pues l es el numero de orbitas. Losvalores de la funcion de ponderacion pueden ser numeros enteros o reales, pero tambien otrotipo de objetos18 (vease el ejemplo 15.3.5).

18Nota para el lector informado: basta con que p : X → U , donde U es un anillo con unidad. Por ejemplo,el anillo de los polinomios.



Demostracion. La demostracion es una adaptacion directa de la demostracion que acaba-mos de ver del lema de Burnside: formamos una matriz M donde las filas estan etiquetadascon las simetrıas del grupo G y las columnas con los elementos del conjunto X . En la posicion(g, x) ponemos p(x) si es que g(x) = x y en caso contrario ponemos 0. El resultado se obtiene,como el lector imaginara, por doble conteo: si sumamos por filas obtenemos que∑

g∈G

( ∑x∈F (g)

p(x)).

Sumando por columnas obtenemos∑x∈X

p(x) · |EG(x)| = |G|∑x∈X

p(x)|OG(x)| = |G|

l∑j=1

|OG(xj)|(

p(xj)|OG(xj)|

)= |G|

l∑j=1

p(xj) ,

donde la segunda igualdad se sigue de partir X en orbitas y observar que p(x)/|OG(x)| esconstante en cada orbita.

15.2.5. Contando el numero de orbitas

Dedicaremos esta subseccion y la siguiente a describir algunas aplicaciones directas dellema cuenta-orbitas, que, recordemos, relaciona el numero de orbitas que determina un grupode simetrıas con el numero de puntos que fija cada una de las simetrıas. En ocasiones, una deestas dos cantidades es especialmente sencilla de calcular y el lema permite calcular la otra.

Ejemplo 15.2.1 ¿Cuantos elementos fija, en media, una permutacion?

Consideremos el conjunto X = 1, . . . , n y el grupo simetrico Sn. Hay una unica orbita19,pues, por ejemplo, las trasposiciones permiten llevar cada elemento de X en cualquier otro,ası que

1 =1n!

∑g∈Sn

|F (g)| ,

segun el lema de Burnside. La conclusion, algo sorprendente, es que una permutacion tiene,en media, un punto fijo, sea cual sea n. Quizas quiera el lector revisar el ejercicio 3.2.14. ♣Ejemplo 15.2.2 Calculemos el numero de orbitas que definen los grupos de simetrıas desimetrıas de X = 1, 2, 3, 4 que presentabamos en la subseccion 15.1.2: J , C4 y D4.

simetrıa g |F (g)|σ0 4 (fija los 4 vertices)σ1 0σ2 0σ3 0η0 0η1 2 (fija vertices 1 y 3)η2 0η3 2 (fija vertices 2 y 4)

En la tabla de la derecha exhibimos todas las simetrıasque forman parte de estos grupos, junto con la informa-cion de los puntos que fijan cada una de ellas. Observe-se que las rotaciones σ1, σ2 y σ3 no fijan punto alguno.Para el analisis de las simetrıas ηj , animamos al lec-tor a que consulte los dibujos del ejemplo 15.1.3. Si elgrupo es J = σ0, η0, el lema de Burnside nos dicehay dos orbitas, pues (0+4)/2 = 2 (las dos orbitas son1, 4 y 2, 3, como ya sabıamos).

19Los grupos de simetrıas con una unica orbita se suelen llamar transitivos.



En el caso de C4 = σ0, σ1, σ2, σ3, las rotaciones, la formula de Burnside nos da (4 +0 + 0 + 0)/4 = 1. Ası que C4 tiene una unica orbita, que incluye a todos los elementos delconjunto. Esto es algo que el lector ya deberıa haber sospechado, pues, por ejemplo, podemosllevar el elemento 1 a cualquier otro: 1 = σ0(1), 2 = σ3(1), 3 = σ2(1) y 4 = σ1(1).

Finalmente, consideremos el grupo D4 = σ0, σ1, σ2, σ3, η0, η1, η2, η3. Como D4 contienea C4, tendra tambien una unica orbita. Dejamos que el lector obtenga este resultado aplicandoel lema de Burnside. Ya de paso, le animamos a que analice las simetrıas del grupo V delejemplo 15.1.4 y que concluya que da lugar a dos orbitas. ♣

15.2.6. Contando el numero de simetrıas en un grupo

El tıtulo de esta subseccion quizas sorprenda. Hasta ahora hemos considerado al grupo Gcomo un dato. Pero, con frecuencia, aunque el grupo G se describa de manera muy sencilla,no es inmediato saber cuantos elementos tiene; ni siquiera si una supuesta lista de elementosde G los incluye todos. Y para ello saber que tamano tiene G es esencial. Usaremos la relacion

|G| = |OG(x)||EG(x)| , para todo x ∈ X ,

que nos resultara de utilidad porque es frecuente que para ciertos elementos x ∈ X sea facilcalcular los tamanos de la orbita y del estabilizador. Lo ilustramos con unos cuantos ejemplos.

Ejemplo 15.2.3 El grupo de rotaciones del tetraedro, segunda parte.

......................................

...........

1

2

34

2π/3

σ =

1 2 3 41 3 4 2

Se trata, como ya comentamos en el ejemplo 15.1.6, de rotacionesen R3 por el origen (que se ubica en el baricentro del tetraedro) yque llevan vertices del tetraedro en sı mismos. Por ejemplo, la quemostramos en la figura de la derecha, o las rotaciones de angulo π quedibujabamos en el ejemplo 15.1.6. Estas rotaciones forman un grupo,y en el citado ejemplo exhibimos 12 de ellas. Pero, ¿como saber sison 12 realmente, o si nos falta alguna?

Nos fijamos en el elemento 1. Por un lado, OG(1) = 1, 2, 3, 4,pues hay rotaciones que llevan el 1 en cualquiera de los restantesvertices. Por otra parte, EG(1) tiene tres elementos: la identidad y las rotaciones (con el ejedel dibujo) de angulos 2π/3 y 4π/3. Ası que |G| = |OG(1)| |EG(1)| = 4× 3 = 12. ♣

Ejemplo 15.2.4 Las rotaciones del cubo.

1

2 3

4

5

6 7

8

Etiquetamos los vertices del cubo de lado 1 con los elementos delconjunto X = 1, 2, . . . , 8, como en la figura de la izquierda. Nosinteresan las rotaciones de R3 alrededor del origen (ahora situado enel centro del cubo) que llevan los vertices del cubo en sı mismos. Denuevo, un grupo. Pero, ¿de que tamano?

Para empezar, es geometricamente claro que OG(1) = X . Con rotaciones en torno al ejeque pasa por el centro de las caras superior e inferior, podemos llevar el 1 al 2, al 3 o al 4.Con una rotacion en el eje que pasa por el centro de las caras izquierda y derecha podemosllevar el 1 al 5; y, de este, con las rotaciones de antes, a todos los demas.



Analicemos el estabilizador

1

2 3

4

5

6 7

8

...............................................................................................

.............................

del vertice 1, EG(1). Para empezar, siuna rotacion σ fija el vertice 1, tambien fijara el 7, pues el eje degiro debe pasar por 1 y 7. De estas rotaciones hay exactamentetres: la identidad y los giros 2π/3 y 4π/3. Ası que |EG(1)| = 3.Por tanto, |G| = |EG(1)||OG(1)| = 3 × 8 = 24. Notese que elgrupo de simetrıas de X tiene 8! = 40320 elementos, de los que

unicamente 24 son rotaciones del cubo. ♣

Ejemplo 15.2.5 Las isometrıas del cuadrado.

1 2

34

Una isometrıa conserva las distancias entre los vertices. El conjunto de lasisometrıas es un grupo G de simetrıas de X = 1, 2, 3, 4. Como G contienea las rotaciones, OG(1) = X . Por otro lado, EG(1) tiene solo dos elementos:la identidad y la simetrıa que deja fijos 1 y 3 y que intercambia 2 y 4. Demanera que |G| = |EG(1)| |OG(1)| = 2 × 4 = 8. Concluimos que G es elgrupo D4 del ejemplo 15.1.3, pues los elementos de D4 son isometrıas. ♣

Ejemplo 15.2.6 Las isometrıas del tetraedro.

La respuesta es aquı todavıa mas facil. Como en el tetraedro cada par de vertices estan adistancia 1, ¡todas las simetrıas de 1, 2, 3, 4 son isometrıas del tetraedro! Ası que es ungrupo con 24 elementos (12 de ellas, rotaciones). ♣

Ejemplo 15.2.7 Las rotaciones del prisma del ciclopropano.

Se trata de comprobar que las 6 rotaciones que hemos exhibido en el ejem-plo 15.1.8 son todo el grupo de rotaciones del prisma.

1

2 3

4

5 6

Es claro que OG(1) =1, 2, 3, 4, 5, 6. Veamos que el estabilizador EG(1) solo esta formado por laidentidad, para concluir que |G| = 6. Si una rotacion de R3 fija el 1, su eje degiro debera pasar por el 1 y por el origen. Si el prisma es “largo”, como el dela figura, y el vertice 4 esta mas lejos de de 1 de lo que lo estan 2 y 3, entoncesla rotacion habra de fijar tambien el 4 (y entonces es la identidad). Dejamos al lector quereflexione sobre el caso en el que esas tres distancias (de 1 a 2, 3 y 4) son iguales. ♣


15.2.1 Sea G un grupo de simetrıas de un conjunto X . Recordemos que un subconjunto Y ⊂ X esestable si g(y) ∈ Y para todo g ∈ G y todo y ∈ Y. Si G tiene k orbitas, ¿cuantos conjuntos establesdistintos tiene?

15.2.2 Un grupo G de simetrıas de un conjunto X tiene k orbitas, de las cuales l son de tamano 1.Compruebese que k ≤ |G|+l

2 .

15.2.3 Tenemos un grupo G de simetrıas de un conjunto X . Consideremos la union Z de los con-juntos de puntos fijos: Z = ∪g∈GF (g) . Compruebese que Z es estable por G.

15.2.4 Sea X un conjunto con n ≥ 2 elementos. Y sea G un grupo de simetrıas de X transitivo(es decir, con una unica orbita). Compruebese que en G hay, al menos, un desbarajuste (esto es, unasimetrıa sin puntos fijos).



15.2.5 Sea D(n) el numero de formas de distribuir n fichasblancas de domino para cubrir un rectangulo 2× n. Por ejem-plo, las dos configuraciones de la derecha son de las que dacuenta D(7): Observese que D(n) coincide con el numero de composiciones de n en las que soloutilizamos unos y doses. Compruebese que D(1) = 1 y D(2) = 2, mientras que, para n ≥ 3,D(n) = D(n − 1) + D(n − 2) . Ahora identificaremos dos de estas configuraciones si son la mis-ma cuando la primera se lee de derecha a izquierda y la segunda, de izquierda a derecha; llamemosd(n) al numero de configuraciones que quedan tras estas identificaciones. Pruebese que

d(n) =

12 (D(n) +D(k)) , si n = 2k + 1,12 (D(n) +D(k) +D(k − 1)) , si n = 2k,

primero, con argumentos de tipo combinatorio, y luego utilizando el lema de Burnside.

15.2.6 Retomamos la nomenclatura del ejercicio 15.1.4. G es un grupo de simetrıas de X y H, ungrupo de simetrıas de Y, donde X e Y son disjuntos. El grupo producto L = G × H es un grupode simetrıas de X ∪ Y. Recuerdese que (g, h)(t) viene dado por g(t) si t ∈ X , y por h(t) si t ∈ Y.Compruebese que el numero de puntos fijos de L es la suma del numero de puntos fijos de G y de H.Verifıquese tambien que el numero de orbitas de L es la suma de las de G y las de H.

15.2.7 Las isometrıas del tetraedro son 24, de las que 12 son rotaciones. Algunas otras son reflexio-nes. ¿Hay alguna isometrıa que no sea ni reflexion ni rotacion?

15.2.8 Determınese el numero de isometrıas del cubo.



15.3. ¿Como contar coloraciones cuando hay simetrıas?

Ya hemos aprendido a contar orbitas de grupos de simetrıas. De acuerdo, pero el lectorno habra olvidado nuestro declarado objetivo: ser capaces de abordar la combinatoria delistas circulares, como la del ejemplo 15.0.2, o cuestiones mas generales de combinatoria consimetrıas. El analisis general que queremos presentar en esta seccion precisa de algo masde andamiaje teorico. El caso de las listas circulares, que revisamos a continuacion, nospreparara el camino para el caso general.

Ejemplo 15.3.1 Tenemos un conjunto X = 1, 2, 3, 4, que interpretamos como los verticesdel cuadrado. El grupo de simetrıas que nos interesa considerar son las rotaciones, es decir,el grupo C4 = σ0, σ1, σ2, σ3.Pero ahora, y este es el ingrediente nuevo que desarrollaremos sistematicamente en lo quesigue, queremos entender los elementos de G, no como simetrıas de X = 1, 2, 3, 4, losvertices del cuadrado, sino como simetrıas de las asignaciones de sımbolos a y b a esosvertices o posiciones.

1 2

34

−→

b a

ba

Estas asignaciones son listas de longitud cuatro con lossımbolos a, b. Por ejemplo, la asignacion que presentamos ala derecha se corresponde con la lista (b, a, b, a). Llamemos Yal conjunto de esas listas. Mientras que X tiene 4 elementos,Y tiene 24 = 16 elementos.

Las rotaciones σ0, σ1, σ2, σ3 tambien son (o podemos interpretarlas como) simetrıas delconjunto Y, de la manera que sigue: si (x1, x2, x3, x4) es una de estas listas, entonces

σ0(x1, x2, x3, x4) = (x1, x2, x3, x4), σ2(x1, x2, x3, x4) = (x3, x4, x1, x2),σ1(x1, x2, x3, x4) = (x2, x3, x4, x1), σ3(x1, x2, x3, x4) = (x4, x1, x2, x3).

Es decir, rotamos la figura y leemos la lista a que da lugar este giro.La cosa, sin duda, requiere cierta formalizacion. Pero sigamos adelante. Queremos contar

cuantas listas son realmente “no equivalentes” por estas rotaciones. Para esto, parece que(una suerte de) lema de Burnside puede ser de ayuda. Porque, al fin y al cabo, todas las listasque esten en la misma orbita (de las que determine el grupo en el conjunto de asignaciones desımbolos; ay, la cosa se complica) seran “equivalentes”. Ası que necesitamos contar el numerode orbitas, o equivalentemente (vıa Burnside), el numero de puntos fijos, que ahora son lasasignaciones de sımbolos que quedan fijas por las rotaciones.

Ni cortos ni perezosos, nos ponemos a contar las listas que fija cada σj. La identidad, σ0,fija todas las listas, claro. Ya van 16. Un momento de reflexion nos lleva a concluir que σ1

y σ3 fijan, cada una de ellas, unicamente las listas que solo tienen un sımbolo: (a, a, a, a) y(b, b, b, b). Finalmente, σ2, algo mas punetera, fija no solo las dos configuraciones anteriores,sino ademas (a, b, a, b) y (b, a, b, a). Ahora calculamos el numero medio de listas que fija elgrupo:

14(16 + 2 + 2 + 4) = 6.

Uy, 6. Justo el numero de listas no equivalentes que descubrimos, tras paciente observacion,en el ejemplo 15.0.2. ¡Esto promete!


15.3. ¿Como contar coloraciones cuando hay simetrıas? 1055

Animemonos: ¿que tal si consideramos la misma cuestion, pero ahora con un cierto numerom ≥ 2 de sımbolos? Ahora el conjunto Y consta de m4 listas. La identidad, de nuevo, fijatodas ellas. Las rotaciones σ1 y σ3 fijan, cada una de ellas, las m listas de Y que consten deun unico sımbolo. Por ultimo, σ2 fija m+m(m− 1) = m2 listas: las citadas anteriormente ylas que constan de dos unicos sımbolos, situados alternadamente. De manera que el numerode medio de configuraciones que fijan las rotaciones es

m4 +m2 + 2m4

.

Como veremos, este es justo el numero de listas circulares (no equivalentes por rotaciones)de cuatro posiciones y con m sımbolos que hay20. La cosa, como decıamos, promete, perorequiere una cierta formalizacion. ♣

15.3.1. Acciones abducidas en el conjunto de coloraciones

Consideremos un conjunto X = 1, . . . , n y un conjunto de r sımbolos, a1, . . . , ar, alos que a partir de ahora denominaremos colores. Una coloracion21 de X con los coloresa1, . . . , ar es una aplicacion de X en a1, . . . , ar. Llamaremos Colr(X ) al conjunto de estascoloraciones:

Colr(X ) =

maneras distintas de asignar uno delos r colores a cada elemento de X

= aplicacionesX −→ a1, . . . , ar

O tambien, las n-listas que podemos formar con los sımbolos del conjunto de colores. Comotenemos r posibilidades para cada elemento de X (o posicion de la lista),

|Colr(X )| = rn.

Si r = 1, solo tenemos una coloracion, claro. En lo sucesivo supondremos que r ≥ 2. En lanotacion Colr(X ) solo hacemos explıcito el numero de colores; y es que, para todo lo quevamos a ver, solo este numero, y no que colores, resultara relevante.

Ademas, tenemos un cierto grupo de simetrıas G del conjunto X . Pero lo que nos interesaes entender G como grupo de simetrıas del conjunto Colr(X ).

Sea ω una coloracion de X . Para una simetrıa g ∈ G, definimos una nueva coloraciong(ω) de X mediante la siguiente receta:

g(ω)(x) = ω(g−1(x)

), para cada x ∈ X .

O, equivalentemente, g(ω) (g(x)) = ω(x), para cada x ∈ X . En palabras, el color que le asignala coloracion g(ω) al elemento x es el mismo que la coloracion ω asigna al elemento g−1(x).Repetimos este proceso para cada simetrıa g ∈ G y cada coloracion ω ∈ Colr(X ).

20Notese, de paso, que hemos probado que m4 + m2 + 2 m es siempre divisible por 4; algo obvio si m espar, pero no tanto si m es impar. Aunque se hace evidente si escribimos el numerador como m4 + m2 + 2m =(m2 + 1)2 − (m − 1)2.

21Conviene senalar, para evitar confusiones, que el concepto de coloracion que utilizamos aquı no es elmismo que el que empleamos en la Teorıa de Grafos (vease la seccion 9.3). Aquı no hay ninguna prohibicion,todas las coloraciones, es decir, todas las asignaciones de colores, estan permitidas.



Por ejemplo, supongamos que X = 1, 2, 3, 4 y consideremos la simetrıa g que gira lafigura 90 en sentido antihorario:

g =(

1 2 3 44 1 2 3

), g

( 1 2

34

)=

g(2) g(3)

g(4)g(1)

Tomemos ahora la coloracion ω dada por ω(1) = a, ω(2) = b, ω(3) = c y ω(4) = d. Cons-truimos la nueva coloracion g(ω) con la regla anterior. Por ejemplo, g(ω)(1) = ω(g−1(1)) =ω(2) = b. Procediendo ası, nos damos cuenta de que, simplemente, estamos rotando la asig-nacion de colores de la misma manera que lo hacıamos con los vertices:

g

( a b

cd

)=

b c

da

Decoramos a g con una tilde para recalcar que en realidad g y g son dos objetos distintos:g mueve elementos de X y g mueve coloraciones de estos elementos. Tras unas observacionesque haremos a continuacion, en las cuales esta distincion resultara conveniente, manteneruna notacion adicional para distinguir la accion sobre Colr(X ) solo recargarıa la notacion sinaportar claridad, y por tanto obviaremos enseguida la diferencia.1.- Para empezar, g(ω) es, por supuesto, una coloracion de X . Ası que g es una aplicaciondel conjunto de coloraciones en sı mismo,

g : Colr(X )→ Colr(X ) .

2.- Pero ademas es una aplicacion biyectiva. Basta comprobar la inyectividad: si hubierados coloraciones ω1 y ω2 que dieran lugar a la misma coloracion tras aplicarles g, es decir,g(ω1) = g(ω2), entonces tendrıamos que

g(ω1)(x) = g(ω2)(x) para todo x ∈ X .

Esto es,ω1(g−1(x)) = ω2(g−1(x)) para todo x ∈ X .

Y como g es una simetrıa de X , esto supondrıa que ω1 y ω2 eran, en realidad, la mismacoloracion. Ası que las g son aplicaciones biyectivas de Colr(X ) en sı mismo, esto es, si-metrıas del conjunto de las coloraciones, elementos de S(Colr(X )). Atencion, Colr(X ) tienern elementos. Y el grupo simetrico correspondiente tiene (rn)! elementos. Si r = 2 y n = 10,hay. . . 1024! simetrıas22.3.- Pero, mas aun, las g forman un grupo de simetrıas. Esto se sigue de observar la siguienteregla de composicion: si h, g son simetrıas en G, entonces

[h g](ω)(x) = ω([h g]−1(x)

)= ω

((g−1 h−1

)(x)

)= ω

(g−1(h−1(x))

)= g(ω)

(h−1(x)

)= h(g(ω))(x) =

[h g

](ω)(x) .

221024! tiene 2640 cifras decimales. . . ¡viva el razonamiento abstracto!



Como esto ocurre para todo x ∈ X y para todo ω ∈ Colr(X ), tenemos que

[h g] = h g

Ası que, dadas dos simetrıas g y h del conjunto de coloraciones, su composicion h g esta biendefinida y es otra simetrıa del conjunto de coloraciones (la que se obtiene “tildando” lasimetrıa h g de X ).

Esta regla de composicion no es una tautologıa. Si hubieramos definido g usando g enlugar de g−1, esta relacion no se hubiera cumplido, como el lector comprobara sin dificultad.Si ahora tomamos como h a g−1 obtenemos que

id = g−1 g = g g−1 = id .

4.- Pero aun no hemos acabado con estos preliminares, cuyo objetivo es concretar el significadode estas g. Ya tenemos que las g son simetrıas de Colr(X ). Pero, ¿son todas distintas?Esto es importante: queremos utilizar el lema de Burnside para ver cuantas orbitas distintasdeterminan estas g en Colr(X ), y cuantas simetrıas intervienen desempena un papel esencial.

Recordemos que r ≥ 2 (hay al menos dos colores). Queremos ver que si g = h entoncesg = h. Para comprobarlo, fijemos x ∈ X y definamos una coloracion particular asociada aeste x: una que asigna a x el color ω(x) = a1, mientras que asigna ω(y) = a2 a todo y = x(a1 y a2 son dos colores distintos). Ahora, por una parte, como h = g,

h(ω)(g(x)) = g(ω)(g(x)) = ω(g−1(g(x))) = ω(x) = a1 ;

y por otra,h(ω)(g(x)) = ω(h−1(g(x))) ,

de manera que ω(h−1(g(x))) = a1. Pero como x es el unico elemento de X que recibe elcolor a1, debemos concluir que h−1(g(x)) = x; es decir, que g(x) = h(x). Como el mismoargumento vale para cualquier x, la conclusion es que h = g, como querıamos comprobar.En resumen, cuando “abducimos”23 G para que actue sobre Colr(X ), la accion es fiel, en laterminologıa de la subseccion 15.1.3 y del apendice 15.6. Como ya hemos avisado, a partirde ahora no distinguiremos entre las simetrıas g (de X ) y las g (de Colr(X )).

Ejemplo 15.3.2 Sea ahora X = 1, 2, 3, que representamos con los verticesde un triangulo equilatero.

3 2

1Tenemos dos colores a, b a nuestra disposicion.Consideramos el grupo G de simetrıas de X dado por G = σ0, σ1, σ2, donde

σ0 =(

1 2 31 2 3

), σ1 =

(1 2 33 1 2

), σ2 =

(1 2 32 3 1

).

Es decir, σ0 es la identidad, σ1 representa un giro (antihorario) de 120 y σ2, el de 240.Nos interesa entender G como grupo de simetrıas del conjunto de las coloraciones de X conlos dos colores.

23No es induccion, ¡es abduccion!, que nos elevamos.



El conjunto de posibles coloraciones Y = Col2(X ) tiene 23 = 8 elementos. Ahı van algunosejemplos de la accion de los elementos de G:

σ1

(a a

a )=

a a

a

σ1

(a b

b )=

b a

b

σ2

(b a

a )=

a a

b

Hay coloraciones que se obtienen una de otra mediante la accion de elementos del grupo desimetrıa. Dejamos que el lector se entretenga en descubrir, enumerando y comparando, las 4coloraciones “no equivalentes”. Y que incluya, ya puestos, las posibles reflexiones. ♣

15.3.2. Lema de Burnside para coloraciones

Sea G un grupo de simetrıas G de X . Ya hemos visto que podemos abducir G y entenderlocomo un grupo de simetrıas de Y = Colr(X ). Al ser grupo de simetrıas, partira el conjuntoY = Colr(X ) en una serie de clases (de equivalencia), las orbitas.

Dos coloraciones ω1 y ω2 de Y = Colr(X ) seran no equivalentes por la accion de Gsi no existe g ∈ G tal que g(ω1) = ω2. Observese que todas las coloraciones que esten enuna las orbitas antes citadas seran equivalentes (pues elementos del grupo llevan unas enotras). Ası que contar coloraciones no equivalentes por G es lo mismo que contar el numerode orbitas que G determina en Y = Colr(X ). Y, vıa la siguiente version del lema de Burnside,la cuestion se reduce a contar las coloraciones que fija cada simetrıa:

Lema 15.8 (Burnside para coloraciones) Dados un conjunto X , un grupo de simetrıas Gy un conjunto de r colores,

#

Coloraciones en Colr(X )no equivalentes por G

=

1|G|

∑g∈G

#

Coloraciones en Colr(X )que quedan fijas por g

Ilustramos el uso de este lema en un par de ejemplos:

Ejemplo 15.3.3 Volvamos al caso del triangulo (ejemplo 15.3.2): X = 1, 2, 3, con elgrupo de simetrıa G = σ0, σ1, σ2 y dos colores a, b a nuestra disposicion.

La identidad, por supuesto, fija las 8 posibles coloraciones. Mientras que σ1 y σ2 solo fijanlas coloraciones que llevan un unico color (y hay dos de estas). Como |G| = 3, el lema deBurnside nos permite concluir que, como senalabamos en su momento,

#

Coloraciones en Col2(X )no equivalentes por G

=

13

(8 + 2 + 2) = 4 .

Las cuatro coloraciones no equivalentes por rotaciones aparecen ala izquierda.

a a

a

b b

b

a a

b

b a

bEs buen momento para senalar que el lema de Burnsi-

de nos permite calcular cuantas configuraciones distintas hay, perono cuales son. Este nivel mayor de detalle es el que proporcionala Teorıa de Polya, que desarrollaremos en el capıtulo 16. ♣



Ejemplo 15.3.4 ¿Cuantos collares de siete cuentas que se pueden formar con tres colores?

Sea X = 1, . . . , 7 y sea a, b, c el conjunto de los tres colores. Llamemos Y al conjunto delas coloraciones de X con esos tres colores: |Y| = 37 = 2187. Hablar de “collares” sugiere quedebemos considerar el grupo de rotaciones C7 = σ0, σ1, σ2, σ3, σ4, σ5, σ6, donde, para cadaj = 0, 1, . . . , 6, la simetrıa σj representa un giro en sentido antihorario de 2πj/7 radianes. Ellema de Burnside nos da directamente que

#collares distintos =17

6∑i=0

# Puntos fijos de Col3(X ) por σi

=17

(37︸︷︷︸

de σ0

+ 3︸︷︷︸σ1

+ 3︸︷︷︸σ2

+ 3︸︷︷︸σ3

+ 3︸︷︷︸σ4

+ 3︸︷︷︸σ5

+ 3︸︷︷︸σ6

)= 315 ,

porque, como es facil verificar, la identidad fija todas las coloraciones posibles, mientras que elresto de los giros solo fijan las coloraciones que asignan el mismo color a todas las posiciones(y hay tres coloraciones de estas, tantas como colores).

Esta cuestion, estara pensando el lector memorioso, ya se ha visto antes. Y efectivamente,ası es: en la subseccion 4.3.1 ya analizamos el caso en el que el numero de cuentas es unnumero primo (como el 7 del ejemplo). Y en la subseccion 4.3.4 resolvimos la cuestion general.Redescubriremos ambos resultados usando el lema de Burnisde en la subseccion 15.4, dondeiremos mas alla y consideraremos la accion de otros grupos, como por ejemplo el diedrico. ♣

Version ponderada del lema de Burnside para coloraciones

Digamos que G determina l orbitas en Colr(X ). Escogemos una coloracion en cada orbita,digamos que y1, . . . , yl. Por ultimo, seleccionamos una funcion p de ponderacion que tomacoloraciones y devuelve, por ejemplo, enteros (o quizas otro tipo de objetos). Exigimos tansolo que p sea constante en cada orbita. En estas condiciones, el lector podra obtener sindificultad, por analogıa con lo que se hizo para el lema 15.7, que

Lema 15.9 (Burnside con pesos para coloraciones)

l∑j=1

p(yj) =1|G|

∑g∈G

( ∑coloraciones y∈F (g)

p(y)),

donde F (g) son las coloraciones que fija g.

Si la funcion de ponderacion vale identicamente 1, recuperamos el lema 15.8. Veamos unejemplo especialmente interesante.

Ejemplo 15.3.5 Consideramos las listas circulares de 4 posiciones con sımbolos a y b.

Hay 6, ya lo sabemos (ejemplos 15.0.2 y 15.3.1). Pero ahora introducimos un ingredientenuevo: consideramos la funcion de ponderacion p que asigna a cada lista la siguiente expresion:

p(coloracion) = u# de aes en la coloracion × v# de bes en la coloracion ,



el producto de dos monomios en las variables u y v, donde las potencias dependen de lacoloracion en cuestion. Es una funcion constante en cada orbita, porque las rotaciones nocambian el numero de aes o de bes. Calculemos ahora la suma que aparece en el lema deBurnside ponderado, para lo que necesitamos saber cuantas coloraciones fija cada simetrıa.

El termino correspondiente a la identidad (que fija todas las coloraciones) es

∑coloraciones y∈F (id)

p(y) =∑

todas las listas

p(lista) =4∑

k=0

(4k

)uk v4−k = (u+ v)4 ;

en esta cuenta estamos agrupando las listas segun el valor que la funcion de ponderaciontenga sobre ellas: para cada k, hay

(4k

)listas con k aes y 4 − k bes. En la ultima igualdad

hemos utilizado el binomio de Newton.Las rotaciones de 90 y 270 fijan solo las listas con un unico sımbolo, ası que obtenemos

una contribucion

2∑

listas con 1 unico sımbolo

p(lista) = 2 (u4 + v4) = 2u4 + 2 v4 .

Por ultimo, la rotacion de angulo 180 fija las coloraciones formadas con un unico color; peroademas aquellas en las que los vertices 1 y 4 llevan el mismo color, mientras que los vertices 2y 3 llevan tambien el mismo color, pero distinto del anterior. Obtenemos ası una contribuciondel tipo u4 + v4 + 2u2 v2. Reuniendo todo esto,

l∑j=1

p(yj) =14((u+ v)4 + 3u4 + 3 v4 + 2u2 v2

)= u4 + v4 + u3 v + u v3 + 2u2 v2 .

Expresion que, leıda adecuadamente, codifica (y muy bien clasificada) toda la informacionsobre las 6 listas circulares (no equivalentes por rotaciones) que hay: por ejemplo, el terminoen u4 (o, mas bien, su coeficiente) nos dice que hay 1 lista circular formada unicamente conaes; el v4 nos informa de que hay 1 lista con todo bes; el termino 2u2 v2, que hay 2 listas condos aes y dos bes, etc. Observese que, tomando u = v = 1, obtenemos 6, el numero total dellistas circulares. Volveremos a este objeto (el “inventario de coloraciones”) cuando tratemosla Teorıa de Polya (capıtulo 16). ♣

15.3.3. Numero de ciclos y lema de Burnside

En los ejemplos tratados hasta ahora, hemos conseguido aplicar el lema de Burnside acoloraciones porque era relativamente sencillo contar los puntos fijos de cada simetrıa. Peroserıa conveniente disponer de un procedimiento general y efectivo para esta tarea. Desarro-llaremos la tecnica en el siguiente ejemplo, para luego abstraerla y enunciarla de manerageneral.

Ejemplo 15.3.6 Consideremos la figura que aparece a la derecha. 1 2 3

456

Tene-mos dos colores, a, b, y queremos contar cuantas coloraciones podemosformar que no sean equivalentes por el grupo de isometrıas de la figura.

El citado grupo esta formado por las siguientes operaciones:



La identidad

β0 =(

1 2 3 4 5 61 2 3 4 5 6

).

La reflexion en el eje vertical de la figura:

β1 =(

1 2 3 4 5 63 2 1 6 5 4

)= 6(1 3) 6(2) 6(4 6) 6(5) .

La reflexion en el eje horizontal que corta por la mitad a la figura,

β2 =(

1 2 3 4 5 66 5 4 3 2 1

)= 6(1 6) 6(2 5) 6(3 4) .

Y, por ultimo, la combinacion β2 β1 = β1 β2 de las dos anteriores,

β3 =(

1 2 3 4 5 64 5 6 1 2 3

)= 6(1 4) 6(2 5) 6(3 6)

(geometricamente, un giro de 180 de la figura).

Hay |Col2(X )| = 26 = 64 posibles coloraciones. Las coloraciones que quedan fijas por laaccion de β1 (la reflexion en el eje vertical) son aquellas en las que los vertices 1 y 3 llevan elmismo color y los vertices 4 y 6 tambien llevan el mismo color (aunque no necesariamente elcolor de 1 y 3). Para contar cuantas hay, basta determinar el color en los vertices 1, 2, 4 y 5(el color en 3 y 6 queda determinado por los utilizados en 1 y 4, respectivamente). Por tanto,

# coloraciones fijas por β1 = 24 .

Observese que β1 tiene, justamente, 4 ciclos. ¿Es esto una regla general? Veamos que pasapara β2, la reflexion en el eje horizontal, que tiene 3 ciclos. Las coloraciones fijas por la accionde β2 son aquellas que llevan el mismo color en 1 y 6, en 2 y 5 y en 3 y 4. Solo hay que fijarentonces los colores que utilizamos en tres vertices, por lo que

#

coloraciones fijas por β2

= 23 = (#colores)#ciclos de β2 .

Dejamos que el lector se entretenga comprobando que lo mismo ocurre con β3 y que, aplicandoel lema de Burnisde, concluya que

#

Col2 de X noequivalentes por G

=

14

3∑j=0

# fijos de Col2(X ) por βj =14

3∑j=0

2(#ciclos de βj)

=14

(26︸︷︷︸

de β0

+ 24︸︷︷︸de β1

+ 23︸︷︷︸de β2

+ 23︸︷︷︸de β3

)= 24 .

♣

Ya podemos enunciar el resultado general. Consideremos un conjunto X , un grupo G desimetrıas de X y r colores. Si una simetrıa g ∈ G tiene k ciclos en su accion sobre X , entonces

# puntos fijos de Colr(X ) por g = rk ,

pues g fija una coloracion de X si y solo si esa coloracion asigna a los elementos de cada ciclocolores iguales. Por tanto, contar el numero de coloraciones que fija g es equivalente a decidirel color que lleva cada ciclo; y hay rk posibles formas de hacer esto. Es decir,



Lema 15.10 (Burnside para coloraciones, version 2)

#

coloraciones en Colr(X )no equivalentes por G

=

1|G|

∑g∈G

r#ciclos de g =1|G|

∞∑k=1

#

elementos de Gcon k ciclos

rk

Notese que la serie de la derecha acaba, en realidad, en |X |. Ademas, aunque se haya argu-mentado con r ≥ 2, la formula es obviamente cierta tambien para r = 1. Se trata de unaexpresion elegante, desde luego, que ademas permite contar de manera efectiva el numerode coloraciones no equivalentes por la accion de un grupo de simetrıas, pues basta para elloobtener la descomposicion en ciclos de las distintas simetrıas del grupo. Lo vemos en un parde ejemplos que habıamos planteado anteriormente, y reservamos las secciones 15.4 y 15.5para el estudio de unas familias de grupos de simetrıas especialmente relevantes.

Ejemplo 15.3.7 Volvamos a las tarjetas con codigos del ejemplo 15.0.3, en las que noqueremos que influya la posicion en que se introduzcan en el lector24.

1 2 3 4

5 6 7 89 10 11 12

13 14 15 16

Sea X = 1, 2 . . . , 16 el conjunto de casillas de la tarjeta. Suponemosprimero que la tarjeta se introduce siempre boca arriba, por lo que solohabra que considerar simetrıa por rotaciones. El codigo se escribe mar-cando o no cada casilla (estos serıan los dos colores, r = 2), ası quehay 216 codigos posibles. Pero para contar cuantas coloraciones (codi-gos) validas hay realmente, debemos considerar el conjunto de simetrıas

G = σ0, σ1, σ2, σ3, donde σj representa una rotacion (antihoraria) de angulo 2πj/4.La identidad tiene 16 ciclos, claro. Las descomposicion en ciclos de las restantes es

σ1 = 16(1 13 16 4) 16(2 9 15 8) 16(3 5 14 12) 16(6 10 11 7) ,σ2 = 16(1 16) 16(2 15) 16(3 14) 16(4 13) 16(5 12)

16(6 11) 16(7 10) 16(8 9) ,σ3 = 16(1 4 16 13) 16(2 8 15 9) 16(3 12 14 5) 16(6 7 11 10) .

Tenemos 4 ciclos de orden 4 para σ1 y σ3, 8 de orden 2 para σ2 y 16 ciclos de orden 1 paraσ0. Por tanto, concluimos que, de las 216 = 65536 tarjetas posibles a priori, solo nos quedan

#

coloraciones de X con dos coloresno equivalentes por G

=

14[216 + 24 + 28 + 24

]= 16456 .

Observese lo sencillo y directo del calculo. Si dispusieramos de tres colores a, b y c, entoncestendrıamos el siguiente (descomunal) numero de tarjetas no equivalentes por rotaciones:

#

coloraciones de X con tres coloresno equivalentes por G

=

14[316 + 34 + 38 + 34

]= 10763361 ,

(¡atencion!, de las 316, mas de 40 millones, tarjetas posibles). Dejamos al lector que se ejercitecon esta tecnica en el ejercicio 15.3.2 anadiendo la posibilidad de voltear la tarjeta. ♣

24No, no usted, amable lector, sino en el de tarjetas.




15.3.1 Coloreamos el conjunto X con r colores. G es un grupo de simetrıas de X . Pruebese que

(a) lımr→∞

#coloraciones no equivalentes por G#total de coloraciones

=1|G| ;

(b) #coloraciones no equivalentes por G ≥ r1

|G|

g∈G |F (g)|

15.3.2 Calculese el numero de tarjetas (con las mismas caracterısticas del ejemplo 15.3.7) que sepueden construir de manera que no sean equivalentes por el grupo de isometrıas de la figura. Hay queincluir, ademas de las rotaciones, la posibilidad de voltear la figura. Esto supone considerar tambienlas reflexiones en los ejes vertical y horizontal, y la combinacion de las operaciones (que resultan serreflexiones en los ejes que pasan por las diagonales de la figura).

15.3.3 Las tarjetas en las que ahora estamos interesados estan formadas por m×m casillas.

(a) Repıtanse los calculos del ejercicio 15.3.2 para el grupo de rotaciones de la figura y para el grupode isometrıas.

(b) ¿Que valor mınimo de m habremos de tomar para que tengamos a nuestra disposicion 10000tarjetas no equivalentes por la accion del grupo de rotaciones? ¿Y si incluimos los volteos?

15.3.4 G es un grupo de simetrıas de X y H, uno de Y, donde X e Y son disjuntos. Definimosel grupo producto L = G ×H como en los ejercicios 15.1.4 y 15.2.6. Coloreamos ahora X ∪ Y con rcolores. Compruebese que

#

coloraciones en Colr(X ∪ Y)no equivalentes por G×H

= #

coloraciones en Colr(X )no equivalentes por G

×#

coloraciones en Colr(Y)no equivalentes por H

.

15.3.5 Tenemos a nuestra disposicion bolas de billar, blancas y negras. Situamos quincede ellas sobre el tapete en una configuracion triangular, como la de la derecha.

(a) Si los movimientos permitidos han de realizarse sobre la mesa, ¿cuantas con-figuraciones puede haber?

(b) ¿Y si las bolas estan “pegadas” y es factible, por tanto, tambien reflejar una configuracion?

(c) Ahora consideramos configuraciones en las que una bola especial (distinta de las blancas y lasnegras) siempre esta situada en la posicion “central” de la configuracion (en mitad de la tercera fila).¿Cuantas disposiciones de bolas blancas y negras distintas podremos tener?

15.3.6 ¿De cuantas maneras no equivalentes se pueden colorear con dos colores los verti-ces de la figura de derecha •

•

•

•

•si consideramos como equivalentes las coloraciones que se ob-

tienen una de otra por una isometrıa del espacio tridimensional?

15.3.7 Generalizamos el ejemplo 15.0.1 que abrıa este capıtulo. Consideramos las listas de longitud nque se pueden formar con r ≥ 2 sımbolos. Identificamos dos listas si al leer la primera en orden inversose obtiene la segunda. ¿Cuantas listas no equivalentes hay?

15.3.8 Queremos asociar r sımbolos a los nodos de la figura de la derecha.

1

2

3

4

5

6

7

Pero los nodos son articulados, de manera que podemos intercambiar entre sı losvertices 2 y 3; los vertices 4 y 5; y los vertices 6 y 7. ¿Cuantas asignaciones desımbolos esencialmente distintas habra?



15.3.9 Reinterpretacion del lema cuenta orbitas para el grupo simetrico. Tenemos unconjunto X de n elementos y disponemos de r colores, con r ≥ 1. Denotamos por R al conjunto decolores disponibles. Vamos a considerar el conjunto Colr(X ) de todas las coloraciones de X con los rcolores. Las coloraciones no son sino las listas (con repeticion permitida) de longitud n con elementosextraıdos de los r colores. Observese que Colr(X ) tiene rn. Tenemos ademas un grupo de simetrıasde X .

Compruebese que el numero de puntos fijos de una simetrıa g (actuando sobre las coloraciones)es rs(g) donde s(g) es el numero de ciclos de g.

Consideremos el caso del grupo simetrico G = Sn. Verifıquese que el numero de orbitas no equi-valentes por Sn coincide con el numero de multiconjuntos de tamano n extraıdos de R, es decir,

R(r, n) =(n+ r − 1n− 1

).

Deduzcase que

R(r, n) =(r + n− 1r − 1

)=

1n!

n∑j=1

rjz(n, j)

donde z(n, j), numero de Stirling de primera especie (sin signo), cuenta el numero de permutacionesde Sn que tienen j ciclos. Recuperese ası la expresion cerrada de la funcion generatriz de los z(n, j):

n∑j=1

z(n, j)xj = x(x + 1)(x+ 2) . . . (x+ n+ 1)

15.3.10 Tenemos un conjunto X de n elementos y disponemos de r colores, con r ≥ n. Denotamospor R al conjunto de colores disponibles. Vamos a considerar el conjunto Col(X )r de coloraciones deX con los r colores pero, ¡atencion!, exigimos que los colores sean todos distintos (por eso el ).Estas coloraciones no son sino las listas sin repeticion de longitud n con elementos extraıdos de los rcolores. Observese que Col(X )r tiene r(r − 1)(r − 2) . . . (r − n+ 1).

Tenemos ademas un grupo de simetrıas de X . Compruebese que, con la accion usual, una simetrıalleva coloraciones con colores distintos en coloraciones con colores distintos.

Verifıquese que cualquier g, salvo la identidad, no fija ninguna tal coloracion. Deduzcase del lemacuenta-orbitas que el numero de coloraciones no equivalentes por G es:

r(r − 1)(r − 2) . . . (r − n+ 1)|G|

Cuando G = Sn, argumentese que hay tantas coloraciones de Col(X )r no equivalentes como sub-conjuntos de R de tamano n y concluyase que C(r, n) =

(rk

).

Sean ahora k1, k2, . . . , kl todos ≥ 1 y con k1 + k2 + . . . + kl = n. Considerese el grupo productoG = Sk1 × Sk2 × . . .× Skl

, donde Sk1 actua sobre las primeras k1 posiciones, Sk2 sobre las siguientesk2, etc. Argumentese que hay tantas coloraciones en Xr como listas de subconjuntos de X , dondela primera de tamano k1, el segundo de tamano k2, etc, y que el numero total de estas listas es elcoeficiente multinomico: (

r

k1, k2, . . . , kl .

)15.3.11 Calculese el numero de coloraciones no equivalentes por rotaciones de los vertices de cadauno de los solidos platonicos con r colores si se exige que cada vertice reciba un color distinto.


15.4. Contando collares (listas circulares) 1065

15.4. Contando collares (listas circulares)

Son frecuentes los problemas en los que contamos listas circulares coloreadas (collares, enla jerga). Se plantean dos tipos de identificacion. Uno consiste en considerar como iguales lasque se obtienen por rotacion sin salirse del plano; el otro permite ademas el volteo.

15.4.1. Las rotaciones del polıgono regular: el grupo cıclico

Nos proponemos analizar sistematicamente el grupo de rotaciones

2

0

1

3 · · ·

n−1

n−2

delpolıgono regular de n lados. El conjunto X = 0, 1, . . . , n − 1 des-cribira los vertices del polıgono, por ejemplo, recorridos en el sentidocontrario a las agujas del reloj25. El grupo G = σ0, σ1, . . . , σn−1 quevamos a considerar es el de las rotaciones (en sentido antihorario) deangulos respectivos 2π j/n, para cada j = 0, 1, . . . , n − 1. Queremosaveriguar la estructura de ciclos que tienen estas rotaciones (en reali-dad, cuantas rotaciones tienen k ciclos), para luego aplicar el lema de

Burnside. Al grupo G se le conoce como Cn, el grupo cıclico de n elementos. En todo esteanalisis, como ya sospechara el lector, desempenara un papel relevante la aritmetica modu-lo n, y apelaremos repetidamente a los resultados que obtenıamos en el capıtulo 4. Observeseque, para un b ∈ X cualquiera, σj(b) ≡ b+ j (mod n) (si hubieramos etiquetado los verticesen el otro sentido, aquı aparecerıa un signo −). La accion de la rotacion de angulo 2π j/n es,simplemente, sumar j modulo n.

Las rotaciones σj tienen una estructura de ciclos muy particular. Por ejemplo, la rota-cion σ0, la identidad, tiene n ciclos. Por su parte, la rotacion σ1 tiene un unico ciclo. Pero σ2

tiene, o bien un unico ciclo (si n es impar), o bien dos ciclos, cada uno con la mitad de loselementos (en el caso en que n sea par), como podra comprobar el lector facilmente. Aunqueestos primeros casos no lo hacen del todo evidente, resulta que una rotacion de G tiene ciclosde una unica longitud. Tomemos una rotacion σj . El ciclo de σj al que pertenece el 0 sera deltipo n(0 j 2j . . .mj), con (m + 1)j ≡ 0 modulo n. Si en ese ciclo estan todos los elemen-tos, ya hemos terminado. Si, por el contrario, hay un b que no esta en ese ciclo, entoncesn(b b+j b+2j . . . b+mj) es tambien un ciclo de σj, disjunto del anterior, y de la mismalongitud (todas las operaciones anteriores son modulo n). Ası que cada σj tiene ciclos delongitud fija, digamos d, y tendra k de ellos, con kd = n (tanto k como d son divisores de n).

Fijemos un divisor k de n y sea d = n/k. Recordemos que queremos averiguar cuantassimetrıas σj tienen exactamente k ciclos (todos de longitud d). Si σj cumple estas condiciones,tendra un ciclo del tipo n(0 j 2j . . . (d−1)j), mientras que dj ≡ 0 modulo n. El lema 4.19nos dice que, entonces, d = n/mcd(n, j), es decir, k = mcd(n, j).

Ahora solo queda contar cuantos valores de j pueden cumplir esta ultima relacion:

# σ ∈ Cn con k ciclos = # 1 ≤ j ≤ n : k = mcd(n, j) = φ(nk

)25Un etiquetado en sentido horario o con los habituales 1, . . . , n no cambiarıa los resultados del analisis.

Lo hacemos ası para aplicar directamente argumentos de Aritmetica modular.



(para la ultima igualdad, revısese el ejercicio 4.3.17), donde φ es la funcion de Euler. Ensuma,

# σ ∈ Cn con k ciclos = φ(nk

)mientras que si k no divide a n, entonces no hay rotaciones σ ∈ G con exactamente k ciclos.Como conclusion, aplicando el lema de Burnside, si coloreamos X = 0, . . . , n − 1 con rcolores, entonces

#

Coloraciones en Colr(X )no equivalentes por Cn

=

1n

∑k|n

φ(nk

)rk =

1n

∑d|n

φ (d) rnd

una formula asombrosa, que ya obtuvimos con distintos argumentos en la subseccion 4.3.4,y que resuelve definitivamente el problema de contar el numero de collares (listas circulares)de longitud n que se pueden formar con cuentas de r colores.

Apliquemos la formula anterior en algunos casos particulares. Empezamos suponiendo quela longitud de los collares es p, un numero primo. Tenemos a nuestra disposicion r colores.Como los unicos divisores de p son 1 y p, y como φ(1) = 1 y φ(p) = p − 1, el numero decoloraciones con r colores no equivalentes por rotaciones resulta ser

1p

[φ(p) r + φ(1) rp

]=

1p

[(p− 1)r + rp

],

un resultado que ya obtuvimos en la subseccion 4.3.1. Recordemos que, en particular, seconcluye que, sea cual sea el entero positivo r, p divide a (p− 1)r + rp, es decir,

(p− 1) r + rp ≡ 0 (mod p).

O equivalentemente, que rp ≡ r modulo p, que es el pequeno teorema de Fermat.

Si la longitud no es un numero primo, entonces la complejidad de la formula dependera delnumero en cuestion. Por ejemplo, si los collares son de longitud 4 (n = 4, cuyos divisoresson 1, 2 y 4), tendremos (r4 + r2 + 2r)/4 collares no equivalentes (como ya vimos en elejemplo 15.3.1), puesto que φ(1) = 1, φ(2) = 1 y φ(4) = 2. Para un numero como n = 14,que tiene “pocos” divisores (el 1, el 2, el 7 y el 14), la formula es simplemente

114[φ(1) r14 + φ(2) r7 + φ(7) r2 + φ(14) r

]=

114

[r14 + r7 + 6r2 + 6r] .

Mientras que para n = 12, que tiene bastantes mas divisores (1, 2, 3, 4, 6 y 12), obtenemosuna expresion mas aparatosa:

112[φ(1) r12+φ(2)r6+φ(3) r4+φ(4) r3+φ(6) r2+φ(12) r

]=

112

[r12+r6+2r4+2r3+2r2+4r] .


15.4. Contando collares (listas circulares) 1067

15.4.2. Las isometrıas del polıgono regular: el grupo diedrico

El conjunto de las isometrıas del polıgono regular de n lados es un grupo de simetrıas deX = 1, 2, . . . , n, el llamado grupo diedrico, Dn. Por supuesto, Cn es un subgrupo de Dn.¿Cuantos elementos tiene Dn? El argumento usual nos dice que tiene 2n elementos, pues elestabilizador de cualquier vertice tiene dos elementos, a saber, la identidad y la reflexion enel eje que pasa por ese vertice y el punto diametralmente opuesto (un vertice, si n es par,o un punto medio del segmento opuesto, si n es impar). Y, por supuesto, se puede llegar alos n vertices con operaciones del grupo (las orbitas tienen n elementos). Ya conocemos n deellas (las de Cn). Vamos a describir las otras n, distinguiendo entre n par e impar.

Cuando n es impar (en la figura, n = 7), tenemos las n reflexionescuyos ejes viene dados por las rectas que pasan por un vertice y el puntodel polıgono diametralmente opuesto. Conviene observar que, en cuanto aciclos, todas estas reflexiones tiene 1 ciclo de orden 1 (el vertice que fijan)y (n− 1)/2 ciclos de orden 2; en total, (n+ 1)/2 ciclos.

..

Para n par (n = 8 en la figura), tenemos dos tipos de reflexiones: enprimer lugar, aquellas que tienen como ejes las rectas que pasan por verticesopuestos (en total n/2). Y en segundo lugar, aquellas que tienen por ejes lasrectas que pasan por puntos medios de lados opuestos, otras n/2. Las delprimer tipo tienen 2 ciclos de longitud 1 y (n− 2)/2 de longitud 2 (n/2+ 1en total), mientras que las segundas tienen n/2 ciclos de longitud 2.

Con todo esto podemos concluir que

#

Coloraciones en Colr(X )no equivalentes por Dn

=

⎧⎨⎩12n

(∑d|n φ (d) r

nd + n r

n+12

)si n impar;

12n

(∑d|n φ (d) r

nd + n

2

(rn/2+1 + rn/2

) )si n par.

Si, por ejemplo, consideramos collares de longitud n = 4 formados con cuentas de r colores,tendremos, como ya sabemos, (r4 + r2 + 2r)/4 distintos si solo consideramos rotaciones,mientras que, si ademas consideramos las reflexiones, habra 1

8

(r4 + r2 + 2r + 2(r3 + r2)

)=

18(r4 + 2r3 + 3r2 + 2r) , un numero en principio menor que el anterior. Aunque para r = 2(collares de longitud 4 con dos colores), ambos numeros coinciden: 6.


15.4.1 Contar el numero de collares de longitud n = p q (donde p y q son dos numeros primos) quepodemos formar con cuentas de r colores distintos. ¿Y si n = pr (donde p es un primo y r un enteropositivo cualquiera)?

15.4.2 Volvamos al modelo de Kekule del anillo de benceno: tenemos seis ato-mos de carbono dispuestos en los vertices de un hexagono, como en la figura dela derecha. Cada carbono tiene un enlace libre. Disponemos de r tipos de radi-cales (posiblemente hidrogenos) que se pueden asociar a los atomos de carbono.¿Cuantas moleculas esencialmente distintas podemos formar?



15.5. Coloreado en tres tridimensiones

Subimos una dimension: nos interesa ahora colorear figuras tridimensionales. En realidad,nos interesa una situacion bien concreta: queremos colorear un conjunto de puntos X en R3,que normalmente seran los vertices de un poliedro. Suponemos ya que son al menos 4 puntos(y no alineados), para que definan realmente una figura con volumen. Aunque, en ocasiones,tambien miraremos las caras o las aristas del poliedro.

¿Y que simetrıas hacemos actuar sobre el conjunto de vertices? Bueno, solo nos interesala simetrıa rotacional, es decir, restringimos nuestra atencion al grupo G de rotaciones deR3 alrededor del origen que preservan la figura. Recordemos, de la subseccion 15.1.3, que enefecto G es un grupo de simetrıas de X , lo hemos dado en llamar el grupo de rotaciones de X .Es relevante asimismo recordar que esa accion de las rotaciones sobre la figura es fiel, es decir,si dos rotaciones mueven cada vertice de la misma manera, entonces es que se trata de lamisma rotacion. Recordemos que rotacion alrededor del origen es siempre rotacion alrededorde un cierto eje y que estas rotaciones forman, asombrosamente, un grupo.

Nuestro problema por tanto es determinar el numero de coloraciones con r colores de losvertices de una figura dada que no son equivalentes por el grupo de rotaciones de esa figura.Y esto se reduce a determinar, para cada k, cuantas rotaciones de la figura tienen k ciclos.Vamos con ello, y para abrir boca26, comenzamos con el prisma del ciclopropano.

Recordemos (ejemplos 15.1.8 y 15.2.7) que este prisma

a

b c

es rectode base un triangulo equilatero y su baricentro es el origen de R3.El grupo de rotaciones de sus vertices consta de solo 6 elementos:la identidad, las rotaciones de angulos +2π/3 y −2π/3 alrededor deleje OZ y los giros de angulo π alrededor de los ejes horizontales quepasan por un vertice del triangulo medio y el punto medio del ladoopuesto de ese triangulo. La identidad tiene 6 ciclos (de orden 1), losgiros de eje horizontal tiene 3 ciclos (de orden 2), mientras que losgiros de eje vertical tienen 2 ciclos (de orden 3). En conclusion,

#

Coloraciones de Colr(X ) no equivalentes por G

=16(r6 + 3r3 + 2r2

).

Interesa calcular el numero de isomeros distintos que se obtienen al substituir los atomosde hidrogeno por, digamos, cuatro de un cierto X y 2 de un cierto Y . Esto lo podemostraducir en averiguar el numero de coloraciones con colores X e Y en las que se usa cuatroveces el color X y dos veces el color Y . Este ejemplo concreto es facil de calcular por puraenumeracion cuidadosa, pero por el momento no hemos desarrollado suficiente maquinariapara calcular tanto detalle en general. Se requiere una herramienta adicional, el “inventariode coloraciones”, que sera objeto de estudio en el capıtulo 16. Lo que sı tenemos enseguida esque el numero de moleculas quımicamente distintas que se obtiene substituyendo las H porX e Y es 1

6(26 + 3× 23 + 2× 22) = 16. El lector meticuloso no tendra dificultad en describirlos . . . 4 isomeros con 4 X y 2 Y .

26Cuidado, no abra la boca demasiado, pues el ciclopropano tiene propiedades anestesicas y querencia aexplosionar cuando se mezcla con oxıgeno a temperatura ambiente.


15.5. Coloreado en tres tridimensiones 1069

15.5.1. Coloreado de los solidos platonicos

Los efectos anestesiantes del ciclopropano no bastan pa-ra aturdir la pulsion estetica que nos predispone a preferirlos excelsos poliedros platonicos a un prismilla sin pedigrı al-guno27. Hay polıgonos regulares de cualesquiera numero delados (al menos 3, claro) o vertices. Pero, sin embargo, ycomo ya discutimos extensamente al tratar los grafos planos,solo hay cinco poliedros regulares: tetraedro, hexaedro28 y octaedro, dodecaedro e icosaedro,los solidos platonicos. Asombroso.

Nuestro plan es colorear los vertices de los solidos platonicos de todas las formas posiblesque no sean equivalentes bajo el grupo de rotaciones de sus vertices. Como producto deri-vado29 de este analisis deduciremos tambien algunos resultados sobre coloreados de caras. Ydejaremos como ejercicio para el lector interesado considerar el coloreado de aristas. Situamosel solido platonico de forma que su baricentro sea el origen del espacio. Los vertices del solidoplatonico quedan ubicados en una esfera centrada en el origen. Se trata ahora de describir,para cada k, cuantas rotaciones del solido tienen k ciclos. O, simplemente, ir considerando lalista de rotaciones del solido y describiendo su descomposicion en ciclos. Para lo que sigue,instamos al lector a que inspeccione con frecuencia los dibujos de los solidos platonicos de masarriba, o mejor, que tenga a mano su modelo tridimensional. Quizas le convenga reverdecersus conocimientos de solidos platonicos releyendo la seccion 9.5.

Los grupos de rotaciones de los solidos platonicos

Es facil dar una lista de rotaciones “naturales” de cada solido platonico. Lo interesantees que, en cada caso, esa lista natural abarca todo el grupo de rotaciones. La lista natural lacomponen, ademas de la identidad, las rotaciones

por ejes que unen vertices opuestos; y con angulos j 2πk , para j = 1, 2, . . . , k−1, donde k

es el numero de caras que comparten un vertice;por ejes que unen puntos medios de aristas opuestas; angulo de giro π;por ejes que unen puntos medios de caras opuestas; angulos: j 2π

k , para j = 1, 2, . . . , k−1,donde k es el numero de vertices una cara,

El tetraedro es un tanto especial, pues no hay ejes por vertices opuestos o por puntos mediosde caras opuestas, pero sı ejes que unen vertices con puntos medios de la cara opuesta (en elejemplo 15.1.6 analizamos con detalle su grupo de rotaciones). Tenemos entonces:

solido platonico tetraedro hexaedro octaedro dodecaedro icosaedronumero de aristas 6 12 12 30 30numero de vertices 4 8 6 20 12

numero de caras en vertice 3 3 4 3 5numero de vertices en cara 3 4 3 5 3

numeros de rotaciones naturales 12 24 24 60 60

27¡Dios, como nos hemos puesto de ciclopropano!28O cubo. Recuerde el lector sus tiempos de griego clasico: prefijos tetra-, hexa-, octa-, dodeca- e icosa-.29O dano colateral, segun se mire.



Pero, ¿cuantas rotaciones hay en cada caso? Usemos la formula |G| = |OG(x)||EG(x)| ylos argumentos de la subseccion 15.2.6. Por un lado, con rotaciones se puede ir de un verticea cualquier otro, y por tanto la orbita de cada elemento incluye a todos los vertices. Porotro lado, el estabilizador de un vertice cualquiera de un solido platonico bajo su grupo derotaciones tiene orden el numero de aristas que confluyen en el (o, lo que es lo mismo, elnumero de caras que lo comparten). Este analisis nos dice que

orden de grupo de rotacionestetraedro 3× 4 = 12

cubo 3× 8 = 24octaedro 4× 6 = 24

dodecaedro 3× 20 = 60icosaedro 5× 12 = 60

¡Voila!, justo en cada caso el numero de rotaciones naturales. Por tanto, el grupo de rota-ciones de cada solido platonico es el de las rotaciones naturales. Resta ahora describir ladecomposicion en ciclos de cada elemento del grupo de rotaciones del solido.

Para el grupo G de rotaciones de los vertices del cubo, cuyosvertices etiquetamos con los sımbolos X = 1, 2, . . . , 8 como en lafigura de la izquierda.1

2 3

4

5

6 7

8

La tabla siguiente contiene toda la informa-cion que necesitamos: en ella senalamos el angulo de giro, el eje derotacion, la estructura de ciclos (cuantos ciclos y de que longitud) dela rotacion; y, finalmente, el numero de rotaciones que tienen dichaestructura.eje angulo estructura numero

puntos medios de caras opuestas 90, 270 2 de longitud 4 6

puntos medios de caras opuestas 180 4 de longitud 2 3

puntos medios de aristas opuestas 180 4 de longitud 2 6

por vertices opuestos 120, 240 2 de longitud 3, 2 de 1 8

la identidad 8 de longitud 1 1

Como hay 17 rotaciones con 4 ciclos, 6 con 2 y 1 con 8, el lema de Burnside nos dice que

# Coloraciones en Colr(X ) no equivalentes por G =124

(r8 + 17r4 + 6r2

).

Ası, por ejemplo, hay 23 maneras (sustituir r = 2) distintas de colorear los vertices del cubocon dos colores. Y 333 formas de colorearlos con tres colores. ¡Quien lo hubiera adivinado!

El conteo de ciclos en los demas solidos platonicos se deja como ejercicio para el lectormeticuloso (veanse el ejercicio 15.5.1). Sı registramos aquı los respectivos polinomios querecogen el numero de coloraciones no equivalentes de los vertices de cada solido:

numero de coloraciones no equivalentes de los verticestetraedro 1

12(r4 + 11r2)cubo 1

24(r8 + 17r4 + 6r2)octaedro 1

24(r6 + 3r4 + 12r3 + 8r2)dodecaedro 1

60(r20 + 15r10 + 20r8 + 24r4)icosaedro 1

60(r12 + 15r6 + 44r4)


15.5. Coloreado en tres tridimensiones 1071

El cubo y el octaedro son duales en el sentido siguiente: si tomamos los puntos mediosde las caras de un cubo como vertices y conectamos con una arista los de caras contiguasobtenemos un octaedro. La misma construccion comenzado con un octaedro da lugar a uncubo. Asimismo, el dodecaedro y el icosaedro con duales. El tetraedro es autodual. Paracoloraciones, esto significa, por ejemplo, que colorear las caras de un cubo equivale a colorearlos vertices de un octaedro. Ası el numero de coloraciones de las caras de un cubo con doscolores es . . . 10 (¡a pintarlos!).

Ejemplo 15.5.1 Doble coloreado. Vamos a formar collares con cubos cuyas caras sehan coloreado con r posibles colores. Dos tales collares se consideran equivalentes si podemosir de uno a otro rotando el collar y rotando los cubos que hagan falta. Nos interesa saber,claro, cuantos collares no equivalentes se pueden formar.

Observese que podemos dividir el proceso en dos etapas. Primero obtenemos una coleccioncompleta de cubos con caras coloreadas no equivalentes por rotaciones. De estos sabemos quetenemos un total de

s =124

(r6 + 3r4 + 12r3 + 8r2

)(tantas como coloraciones de los vertices del octaedro, vease la tabla anterior). Y, en unsegundo paso, formamos collares con esos cubos, es decir, hacemos que esos s cubos desem-penen ahora el papel de colores disponibles en la coloracion de un collar. Por tanto, en sumatenemos un total de

1n

∑k|n

φ(nk

)sk =

1n

∑k|n

φ(nk

)( 124

(r6 + 3r4 + 12r3 + 8r2

))k

de collares no equivalentes formados con cubos coloreados no equivalentes.

En la situacion general tenemos un conjunto A con un grupo G de sus simetrıas y unconjunto B con un grupo de simetrıas H. Y tenemos un proceso en dos etapas: formamosprimero el conjunto Ω de coloraciones de B no equivalentes por H, y ahora asignamos esascoloraciones en Ω a los elementos de A, es decir, coloreamos A con Ω y buscamos las noequivalentes. El numero total resultante de este proceso es:

1|G|

∞∑k=1

# elementos de G

con k ciclos

⎛⎝ 1|H|

∞∑j=1

#

elementos de Hcon j ciclos

rj

⎞⎠k

que es la evaluacion de la composicion de dos polinomios en r. ♣


15.5.1 (a) El grupo de rotaciones de los vertices del dodecaedro consta de 60 elementos. Clasifıquenseestas rotaciones segun su estructura de ciclos y obtengase el numero de coloraciones con r colores delos vertices del dodecaedro (coincidira con el numero de formas de colorear las caras del icosaedro).



(b) El grupo de rotaciones de los vertices del icosaedro consta tambien de 60 elementos. Obtengase elnumero de maneras no equivalentes por rotaciones de colorear con r colores los vertices del icosaedro30

(o las caras del dodecaedro).(c) Analıcese la misma cuestion para el octaedro, cuyo grupo de rotaciones consta de 24 elementos.

15.5.2 ¿De cuantas maneras (no equivalentes por rotaciones) se pueden colorear las aristas de uncubo con r colores?

15.5.3 ¿De cuantas maneras se pueden colorear los vertices del cubo si tenemos en cuenta, ademas,las posibles reflexiones?

15.5.4 Pulseras. (a) La pulsera de la figura tiene 2n vertices. Digamos quen ≥ 6 y es un numero par. Usando los argumentos habituales (tamano deestabilizadores y orbitas), calcula el tamano del grupo de rotaciones de la figura.Halla la estructura de ciclos de estas simetrıas y calcula el numero de maneras(no equivalentes por rotaciones) de colorear los vertices con r colores.(b) El caso n = 4 requiere tratamiento especial. Compruebese que si las cuentas de la pulsera formanun paralelepıpedo con base cuadrada de lado l y altura h distinta de l, entonces el grupo de rotacionesconsta de 8 elementos. Si el paralelepıpedo tiene los tres lados de longitudes distintas, entonces solo haycuatro rotaciones. En ambos casos, los estabilizadores estan formados unicamente por la identidad.Sin embargo, ¡oh magia!, si el paralelepıpedo es un cubo, entonces los estabilizadores tienen tamano 3y el grupo de rotaciones consta de 24 elementos. Calculense, en cada caso, el numero de coloracionescon r colores (no equivalentes por rotaciones) de los vertices de las figuras.(c) QUASERAS

30Dicen las malas lenguas que esta es una pregunta que propone Google para contratar a sus empleados.¡Tome nota el lector!


15.6. Apendice: grupos y acciones de grupos (en abstracto) 1073

15.6. Apendice: grupos y acciones de grupos (en abstracto)

En este capıtulo hemos estudiado grupos de simetrıas concretos de un conjunto dado X .Pero en Matematicas hay una nocion abstracta general de grupo, del que los grupos desimetrıas son un ejemplo (el mas importante, sin duda). Estas nociones abstractas en Ma-tematicas aparecen para aportar un lenguaje y un analisis comun a distintos objetos impor-tantes que tienen la misma estructura. Estudiamos la nocion abstracta general, apartandolade sus realizaciones concretas, de manera que las propiedades que se deduzcan en la situacionabstracta sean aplicables a todos los ejemplos. Una de esas nociones es la de estructura degrupo. Hay que recalcar que la eleccion de axiomas que definen una nocion general en Ma-tematicas no es ni mucho menos arbitraria, sino que es el resultado de un proceso de destiladode la esencia comun a muchos ejemplos de interes y relevancia.

Un grupo es un conjunto G en el que hay definida una operacion binaria, es decir, unaregla que a cada par (ordenado) de elementos del grupo le asocia un elemento del conjunto(se dice que el conjunto es cerrado por la operacion). Denotaremos la operacion en G de x ey como x ·y, y hablaremos de producto, entendiendose siempre como denominacion general (aveces la operacion sera la suma, otras veces el producto, en ocasiones la composicion, etc.).Para afirmar que el conjunto G, con la operacion “·”, es un grupo se deben cumplir, ademas,las siguientes propiedades31:

la operacion es asociativa. Esto es, para cualesquiera x, y, z de G, x · (y · z) = (x ·y) · z.Hay un elemento neutro e, es decir, un elemento con la propiedad de que x · e =e · x = x para cada x de G.

Todo elemento x tiene un inverso, denotado por x−1, tal que x · (x−1) = (x−1) · x = e.

Note el lector que no incluimos la propiedad conmutativa entre estos requerimientos. Losgrupos en los que la operacion es conmutativa, es decir, en los que x · y = y · x para cadapar de elementos x e y del grupo, se llaman conmutativos o abelianos, en honor de N. H.Abel32. El orden del grupo es el numero de elementos de que consta; en el caso en que tengainfinitos elementos, diremos, claro, que el grupo es de orden infinito.

El grupo S(X ) de todas las simetrıas de un conjunto X es, por supuesto, un grupo conla operacion de composicion. Pero estructuras de grupo las encontramos por doquier:

los enteros, Z, con la operacion de la suma.

Las matrices n× n de numeros reales con la operacion de suma de matrices.

Zn con la operacion de suma modulo n. Si p es un numero primo, Z∗p = 1, 2, . . . , p−1

con la operacion de multiplicacion modulo p es tambien un grupo (y tambien lo es Z∗m,

el conjunto de los elementos invertibles modulo m).

31En el DRAE aparece la siguiente acepcion matematica de “grupo”, un tanto imprecisa: “Conjunto dotadode una operacion asociativa, con un elemento neutro, y que contiene un elemento simetrico para cada uno desus elementos”.

32Vease su nota biografica en la pagina 764.



Diversos grupos matriciales con la multiplicacion de matrices: M(n), las matrices cua-dradas n×n; S(n), las matrices cuadradas n×n con determinante 1; O(n), las matricesortogonales n×n (A es ortogonal si su traspuesta es su inversa: At ·A = I); SO(n), lasmatrices ortogonales n×n de determinante 1 (en el apendice 15.7 le dedicamos especialatencion a los grupos O(n) y SO(n), cuando n = 2 y sobre todo n = 3.)

El proceso de “destilado” de la nocion de grupo fue largo, y en el estuvieron involucra-dos grandes nombres de las Matematicas. Euler y Gauss, en sus estudios sobre la aritmeticamodulo n, consiguieron resultados que hoy sabemos son validos en grupos generales. Vander-monde y Lagrange, en torno a 1770, descubrieron la relacion entre la resolucion por radicalesde las ecuaciones de tercer y cuarto grado y ciertas propiedades de los grupos S3 y S4. Ruffini,en 1799, y Abel unos anos mas tarde, en su estudio de S5, dieron con la clave que permitioprobar que la ecuacion quıntica no sepodıa resolver por radicales. Aunqueparece que fue Galois el primero que uti-lizo el termino “grupo” (groupe de l’equa-tion), eso sı, en un sentido muy especıfico (como subgrupo del grupo de permutaciones delas raıces de un polinomio). Vease el texto de la derecha, perteneciente a su memoria “Surles conditions de resolubilite des equations para radicaux”, de 1831.

Figura 15.3: Cauchy y Cayley

Cauchy33 estudio sistematicamente el grupo de permutaciones Sn. Pero se limitaba to-davıa a exigir que el conjunto fuera cerrado para la operacion de composicion, de donde sededucıa sin dificultad la existencia del elemento neutro y de los inversos. Un argumento que,esencialmente, ya vimos en su momento (vease la pagina 142), al definir el orden de unapermutacion, y que aquı repetimos en un contexto general: sea G un grupo finito y sea f un

33Sorprende la gran cantidad de terminos matematicos que llevan el nombre del extraordinariamente prolıficoAugustin Louis Cauchy (1789-1857), y que a mas de uno le resultaran familiares: la desigualdad de Cauchy-Schwartz, el teorema integral de Cauchy, las ecuaciones de Cauchy-Riemann, las sucesiones de Cauchy, elteorema de Cauchy-Kovalevskaya sobre existencia de soluciones de ecuaciones en derivadas parciales. . . Y esque, ademas de sus trabajos originales, Cauchy escribio una serie de textos, como el “Course d’analyse”, en losque organizo y formalizo muchos de los resultados conocidos en Analisis real y complejo. Al igual que Galois,su vida se vio afectada por los acontecimientos que se sucedieron tras la revolucion de 1830 que destrono aCarlos X de Borbon. Cauchy se nego a prestar juramento de obediencia al nuevo rey Luis Felipe de Orleans,lo que le hizo perder sus puestos y lo condujo al exilio.



elemento suyo. Todas las potencias f2, f3, . . . pertenecen a G. Por el principio del palomar,habra dos repetidas, digamos fn = fm, con n > m. Entonces, es facil comprobar que fn−m

es el elemento neutro de G y que fn−m−1 es el inverso de f . Fue Cayley34, alla por 1854, elprimero que considero la nocion abstracta de grupo, en la que la asociatividad habıa de serpostulada. Todavıa eran grupos finitos, ası que el que la existencia de los inversos aparecieracomo una exigencia mas hubo de esperar a que se trataran los grupos infinitos. En 1872,Klein propuso el “programa Erlangen”, con el que se proponıa entender la Geometrıa desdeel punto de vista de la Teorıa de grupos. Llegaba la mayorıa de edad para el concepto degrupo, y textos como el “Theory of groups of finite order” de Burnside en 1897 acabaron pordefinirlo completamente.

Cada grupo que uno pueda considerar tiene un contexto y un lenguaje particulares. Perolo que aquı nos interesa es verlos todos ellos desde el punto de vista que los engloba, queno es otro que el de compartir estructura de grupo. Y deducir propiedades comunes a todosellos, que luego tendran su traduccion particular en cada uno de los ejemplos.

Como ilustracion, podemos probar que, en cualquier grupo, el inverso de un elementoes unico. Es algo que podrıamos comprobar directamente en cada ejemplo. Pero el lectorsabra apreciar la ventaja que supone probarlo para un grupo general (y luego aplicar elresultado, sin mas, a cada ejemplo). Supongamos que un elemento x de un grupo tiene dosinversos, a y b. Entonces, por la propiedad asociativa, (a · x) · b = a · (x · b) . Como a esinverso de x, el termino de la izquierda es e · b = b. Y como b es inverso de x, el termino dela derecha es a · e = a, de manera que b = a. Ya esta: sencillo, directo. . . ¡y general! (veanseotras propiedades relevantes en el ejercicio 15.6.1).• Tabla del grupo. Consideremos un conjunto G = e, a, b, c, al quequeremos dotar de estructura de grupo definiendo una operacion “·”. He-mos de definir como se multiplican los elementos de G y esto lo podemoshacer mediante una tabla de operacion (ya vimos, por ejemplo, la tablaque definıa al grupo V en el ejemplo 15.1.4). Digamos que los productosson los que aparecen a la derecha.

e a b c

e e a b ca a b c eb b c e ac c e a b

Se comprueba directamente sobre latabla que e es el elemento neutro y que todo elemento tiene un inverso. Mas laborioso resultacomprobar que la tabla define una operacion asociativa, pues esto requerirıa verificar que escierto que (x · y) · z = x · (y · z) para todas las posibles elecciones de x, y y z (¿cuantas hay?).

Toda la informacion sobre el grupo esta recogida en la tabla de operacion. Si G tiene nelementos, podemos ordenarlos, digamos G = e = x0, x1, x2, . . . , xn−1, y utilizarlos paraetiquetar las filas y las columnas de una matriz, que completamos ubicando en cada posicioncorrespondiente a la fila xi y columna xj el producto xi ·xj (observese el orden). La tabla es,pues, una matriz |G| × |G|. En cada fila y en cada columna hay un unico elemento neutro,pues los inversos son unicos. Pero aun mas, la tabla es un cuadrado latino35 en los sımbolos

34El ingles Arthur Cayley (1821-1895) podrıa ser considerado como otro gran matematico aficionado, comoFermat, pues ejercio de abogado durante muchos anos, al tiempo que producıa artıculos en matematicas.A partir de 1863 se dedicarıa en exclusiva a las Matematicas, desde su puesto en Cambridge. Las mejoresaportaciones de este matematico, uno de los mas prolıficos de la Historia por cierto (quizas solo Euler y Erdosestan por delante) se produjeron en el algebra matricial, la geometrıa no euclıdea y la geometrıa n-dimensional.

35Un cuadrado latino n × n es una matriz n × n formada con n sımbolos distintos y en la que cada uno deellos aparece una unica vez por fila y columna. De ellos hablaremos en el capıtulo 17.



e, x1, x2, . . . , xn−1 (pero cuidado, no todo cuadrado latino da lugar a una operacion de grupo,vease el ejercicio 15.6.2). Ademas, en la tabla las e estan distribuidas simetricamente respectode la diagonal; es decir, si substituimos las e por 1 y los demas elementos por 0, la matriz deceros y unos ası obtenida es una matriz simetrica.

• Subgrupos. Si G es un grupo y H ⊂ G, podemos operar con los elementos de H con laoperacion de G. Pero, ¿hace eso de H un grupo?; ¿que se necesita? Es claro que se precisa que

la operacion de cualesquiera dos elementos de H sea de nuevo un elemento de H;que el inverso de cualquier elemento de H este en H;y que el elemento neutro este en H.

Pero la asociatividad, la propiedad mas laboriosa de comprobar, es ahora automatica, puesla cumplen los elementos de G y por tanto los de H.

Ası que tenemos tres requisitos, pero observese que el ultimo se deduce de los dos ante-riores: tomemos un elemento cualquiera de H, digamos h. Su inverso, digamos k, es tambiende H y el producto de h y k, es decir, e, tambien esta en H. De manera que para verificarque un subconjunto H de G es un grupo con la operacion de G, es decir, es un subgrupode G, solo hemos de comprobar36 dos cosas:

para cualesquiera h1 y h2 de H, se tiene h1 · h2 ∈ H;

para cualquier h ∈ H, se tiene que h−1 ∈ H.

Todos los grupos de simetrıa que hemos estado considerando en este capıtulo son subgruposde los correspondiente grupos completos de simetrıa.

• Isomorfismos. Recordemos la discusion del ejemplo 15.1.4: tenıamos allı dos grupos dis-tintos (uno de simetrıas del rombo y otro de simetrıas del cubo), que sin embargo tenıan lamisma tabla de productos (salvo un cambio de nombres de los elementos del grupo). Si comoafirmabamos antes un grupo (en plan abstracto) viene descrito unicamente por su tabla deproductos, estos dos grupos deberıan ser, en cierto sentido, “iguales”.

Dos grupos seran isomorfos si existe un cambio de nombres (entre los elementos res-pectivos) que preserve la tabla de productos. Formalmente, eso se traduce en la siguientedefinicion: dos grupos G y G′ seran isomorfos si existe una biyeccion φ : G→ G′ tal que

φ(x · y) = φ(x) · φ(y) para cualesquiera x e y de G.

Atencion, la operacion “·” de la izquierda es la del grupo G, mientras que la de la derecha esla de G′. Es decir, da igual multiplicar dos elementos de G y calcular la imagen del resultadopor φ que determinar primero las imagenes y luego multiplicarlas (con la operacion de G′).

Por supuesto, el que φ haya de ser una biyeccion exige que ambos grupos tengan elmismo tamano; pero no toda biyeccion sera un isomorfismo de grupos: ha de preservar losproductos, de la manera que senalabamos antes. Como es una biyeccion, la aplicacion inversaφ−1 esta bien definida, ası que da igual si partimos de G o de G′.

36Vease otra manera de caracterizar un subgrupo en el ejercicio 15.6.4.



En el ejemplo de V y V era sencillo encontrar una tal biyeccion: en la notacion que uti-lizabamos entonces, bastaba tomar γi ←→ γi. Pero en otros casos puede ser mas complicadoencontrar la biyeccion. Y aun mas puede serlo el comprobar que dos grupos no son isomorfos;por ejemplo, consideremos las tablas de productos de los grupos C4 y V:

C4 idC4 σ1 σ2 σ3

idC4 idC4 σ1 σ2 σ3

σ1 σ1 σ2 σ3 idC4

σ2 σ2 σ3 idC4 σ1

σ3 σ3 idC4 σ1 σ2

V idV γ1 γ2 γ3

idV idV γ1 γ2 γ3

γ1 γ1 idV γ3 γ2

γ2 γ2 γ3 idV γ1

γ3 γ3 γ2 γ1 idV

Por supuesto, podrıamos revisar las 4! aplicaciones biyectivas de C4 en V (o las 3! que ya llevanla identidad de C4 en la identidad de V) y comprobar que ninguna de ellas es un isomorfismoentre los dos grupos. Pero este no es un procedimiento razonable cuando el orden de losgrupos es muy grande (¡y ya ni tiene sentido si son infinitos!). Hay que buscar argumentosque nos permitan deducir la no existencia de un isomorfismo. En nuestro ejemplo, observemosque un isomorfismo φ entre C4 y V deberıa cumplir, por ejemplo, que

φ(σ1 · σ1) = φ(σ1) · φ(σ1) .

El producto de la derecha, sea cual sea φ(σ1), es la identidad de V (vease la diagonal dela tabla de V), ası que la φ(σ1 · σ1) = φ(σ2) = idV . Pero φ(idC4) = idV , y φ no serıa unabiyeccion.

• Centro de un grupo. Un subgrupo peculiar, pero que resultara de particular interes paranosotros, es el centro del grupo. Si G es un grupo, su centro se denota por Z(G) y se definecomo la coleccion de elementos de G que conmutan con todos los elementos de G. Es decir,x ∈ Z(G) si

xy = yx, para todo y ∈ G .

Es inmediato comprobar (vease el ejercicio 15.6.8) que el centro de cualquier grupo es unsubgrupo suyo. Por supuesto, Z(G) es un grupo conmutativo.

El centro del grupo de simetrıas completo en n sımbolos consiste tan solo de la identidad,salvo en el caso n = 2, para el que S2 es conmutativo (revısese el ejercicio 15.1.1). El centrodel grupo diedrico Dn, que consta de 2n simetrıas, del polıgono regular de n lados consistede (solo) la identidad si n es impar y de la identidad y la rotacion de angulo π si n es par(vease el ejercicio 15.6.8). El caso n = 4 es muy interesante: el tamano del centro del grupo(2 elementos) es exactamente la cuarta parte del tamano del grupo (8 elementos). El interesradica en que en un grupo no conmutativo no puede ocurrir que el tamano del centro seamayor que la cuarta parte del tamano del grupo. Ası que D4 es extremal para esta cuestion.Vease el lema 15.13.

15.6.1. Accion de un grupo sobre un conjunto

Es hora ya de que, una vez cumplimentado este recorrido asaz vertiginoso en el que hemosresumido los aspectos fundamentales de la nocion de grupo, nos dispongamos a discutir



abiertamente un concepto que ha estado merodeando agazapado a lo largo de todo estecapıtulo, como es el de accion de un grupo sobre un conjunto. El lector quizas nosespete alarmado: ¿como que agazapado, no era justo de eso es de lo que ha venido tratandoel capıtulo? Y no le falta razon37, pero ahora al considerar grupos abstractos podemos darun formato general a esa idea de accion y ası abordar algunas cuestiones nuevas.

Partimos de un grupo abstracto dado G y de un conjunto X . Una accion de G sobre Xes una regla que a cada elemento del grupo g le asigna una simetrıa g del conjunto X , demanera que esta asignacion preserva38 las operaciones de grupo:

g h = g h .

Se suele decir que g(x) es la accion de g sobre el elemento x. En una accion estamos in-terpretando a cada elemento del grupo G como una simetrıa de X . Por supuesto, si G espor derecho un grupo de simetrıas de X entonces claro que tenemos una accion obvia de Gsobre X : cada g ya es una simetrıa de X y g = g. Esta es la situacion basica, la que nos haocupado hasta ahora en este capıtulo.

Conviene senalar que si un grupo G actua sobre un conjunto X , la restriccion de esaaccion a un subgrupo dado H de G determina una accion del subgrupo H sobre el propio X .

Con la definicion mas amplia que ahora estamos introduciendo puede ocurrir que varioselementos g distintos de G den lugar a una misma simetrıa39. El conjunto G de las g es ungrupo de simetrıas de X aunque, de nuevo, algun elemento de G puede provenir de mas deun elemento del grupo G

Una accion de un grupo G sobre un conjunto X se dice fiel si la asignacion de simetrıa acada elementos de G es inyectiva, es decir, si g1 = g2 (son simetrıas de X ) implica que g1 = g2(son elementos de G). En el caso de accion fiel, podemos identificar40 el grupo abstracto Gcon el grupo de simetrıas G.

Consideremos, por ejemplo, el grupo G = Z, con la operacion de suma. Definimos unaaccion sobre X = 0, 1, 2, . . . , n − 1. de la siguiente manera: dado un entero z ∈ Z, leasignamos z(k) = z + k (mod) n. Observe el lector que en este caso la accion no es fiel.

Ya hemos utilizado implıcitamente el concepto de accion de un grupo sobre un conjuntoen un par de ocasiones: cuando restringıamos un grupo de simetrıas a un subconjunto estable,o cuando extendıamos un grupo de simetrıas a las coloraciones del conjunto. En el primercaso, partıamos de un grupo G de simetrıas de X . Tenıamos ademas un subconjunto Y ⊂ Xque era estable por G. Entonces, al restringir cada elemento de G a Y obtenıamos un grupode simetrıas de Y. A esta accion de G sobre Y, que en general no es fiel, nos referıamos comoaccion inducida (de un grupo G de simetrıas de X en un subconjunto Y ⊂ X ).

En el segundo, empezabamos con un grupo G de simetrıas de un conjunto X , y de-cidıamos interpretarlas como simetrıas sobre coloraciones. A esta accion, que es siempre fiel,nos referıamos como accion abducida sobre coloraciones.

37El cliente tiene siempre la razon.38Nota para el lector informado: la asignacion g → g es un homomorfismo del grupo G en el grupo S(X ).39Es decir, que el homomorfismo de G en S(X ) no sea inyectivo.40G y G son isomorfos.



En ocasiones resulta util considerar acciones de un grupo abstracto sobre sı mismo.Partimos de un grupo abstracto G y queremos hacerlo actuar sobre sı mismo. Esto es, ahora Xes tambien G. Insistimos: de partida G es un grupo abstracto cualquiera, no un grupo desimetrıas. Denotamos la operacion del grupo, como es costumbre, como producto.

Una posible accion, que llamaremos accion por producto, viene dada por la siguienteregla: a cada g ∈ G le asignamos la simetrıa g dada por

g(f) = g · f, para cada f ∈ G .

Se trata de una accion fiel. Si H es un subgrupo de G, la misma receta, h(f) = h · f , nos dauna accion por producto de H sobre todo G. Utilizaremos esta accion en la demostracion delllamado teorema de Lagrange (vease la subseccion 15.6.3).

Hay otra accion relevante: la accion por conjugacion. Ahora asociamos a cada g ∈ Gla simetrıa g dada por

g(f) = gfg−1, para cada f ∈ G .Cada g es una biyeccion de G sobre G. La accion no es fiel, en general; si, por ejemplo, elgrupo es conmutativo, entonces todas las g son la identidad.

15.6.2. Orbitas, estabilizadores y puntos fijos de la accion de un gruposobre un conjunto. Lema de Burnside

Vamos directo a las definiciones. La orbita de x por la accion de G es el conjunto detodas las imagenes de x por la accion de G, es decir,

OG(x) = g(x) : g ∈ G

Observese que la orbita OG(x) por G es asimismo la orbita O G(x) bajo G. Las distintasorbitas bajo G dan una particion de X . El estabilizador de x ∈ X , que denotamos porEG(x), es el subconjunto de G de aquellas g ∈ G (no de G) que fijan x:

EG(x) = g ∈ G : g(x) = x .

Los puntos fijos de g ∈ G son los x ∈ X tales que g(x) = x. Denotamos por F (g) a eseconjunto de puntos fijos. Pues bien, ¡voila!, tenemos un lema cuenta-orbitas de Burnside.

Lema 15.11 (Burnside para acciones) Si el grupo G actua sobre el conjunto X , entonces

# orbitas distintas =1|G|

∑g∈G

|F (g)| .

Es el mismo enunciado que el Burnside para grupos de simetrıas, . . . y la misma demostracion,tal cual, por doble conteo. Instamos al lector a que se cerciore. Tras la insistencia en observarque considerar acciones va mas alla de los grupos de simetrıas por derecho, quizas sorprendaque el lema de Burnside valga sin mas. Observe el lector que el grupo de simetrıas G tienelas mismas orbitas que G, de manera que el lema de Burnside usual nos da el enunciado dearriba con G en lugar de G. Al pasar de G a G se repiten elementos de G, en efecto, peroesto sucede tanto en el numerador como en el denominador y resulta que esa repeticion acabacancelandose. Veamos varias aplicaciones de esta version del lema de Burnside para acciones.



15.6.3. Accion de producto. El Teorema de Lagrange

Consideremos un grupo G abstracto, un subgrupo suyo H (que pudiera ser el mismo G)y la accion de H sobre G por producto. Aquı G desempena41 el papel de X .

La orbita de un elemento cualquiera g de G (recuerdese que es H quien actua sobre G)es el conjunto h · g : h ∈ H, que nombraremos como H · g. El grupo G, en su papel de X ,se parte en orbitas disjuntas, digamos

G = H ∪ (H · g2) ∪ (H · g3) ∪ · · · ∪ (H · gr) .

Observese que una de las orbitas de esta accion es la del elemento neutro: H = H ·e (que serıae = g1). Ahora bien, todas las orbitas tienen el mismo tamano, |H|, porque cada aplicacion

h ∈ H −→ h · gj ∈ (H · gj)

es biyectiva. De manera que |G| = |H| × r. En particular vemos que |H| divide a |G|.

Figura 15.4: Lagrange

Alternativamente, podemos emplear el lema de Burnside anterior.El estabilizador de un elemento g bajo la accion de H esta compuestopor los h ∈ H tal que hg = g, es decir, solo la identidad.

¿Y los puntos fijos? Si h ∈ H el conjunto de puntos fijos es elconjunto de g tales que hg = g; de manera que si h no es la identidadF (h) es vacıo, y para la identidad F (e) = G. Usando Burnside,

r =1|H|

(∑h∈H

F (h))

=1|H|

(|G|+

∑h∈H\e

F (h))

=|G||H| ,

y volvemos a obtener que |H| divide a |G|, que es el contenido delteorema de Lagrange42, que enunciamos a continuacion:

Teorema 15.12 (Lagrange) Sea G un grupo y H un subgrupo suyo.Entonces |H| divide a |G|.

La version de este teorema para grupos de simetrıa reza ası: sean G y H dos grupos desimetrıas de X . Si H ⊂ G, entonces |H| divide a |G|. En particular, el orden de todo grupode simetrıas de un conjunto X de n elementos divide a n!, el orden de Sn. Lo que quizas lepueda parecer obvio o natural43 al lector. Pero, en todo caso, permite descartar posibilidades.

41Y, claro, para acabar de confundir H hace de G.42De nuevo, solo una denominacion, no una atribucion. Porque aunque fue Lagrange, en sus “Reflexions

sur la resolution algebrique des equations”, quien inicio en 1771 el estudio de lo que hoy conocemos como lateorıa de grupos finitos, es mas adecuado atribuir el resultado que nos ocupa a Galois. Joseph Louis Lagrange(1736-1813), trabajo en Turın (su lugar de nacimiento), en Berlın tras la marcha de Euler, al que sustituyo, yfinalmente en Parıs. Son notables sus aportaciones al Analisis y al Calculo de Variaciones. Dos de sus obrasmas destacadas son la “Mecanique analytique” de 1788 y el “Traite des fonctions analytiques” de 1797.

43Aunque el recıproco del Teorema de Lagrange no es cierto: dado un grupo G y un entero positivo k quedivida a |G|, no siempre hay un subgrupo de G de orden k. El contraejemplo mas pequeno es el siguiente: elgrupo alternado A4, que tiene 12 elementos, no tiene ningun subgrupo de orden 6 (vease el ejercicio 15.6.9).



Ası, por ejemplo, en el conjunto 1, 2, 3, 4 no hay grupos de simetrıas con (exactamente) 5elementos, pues 5 no divide a 4! = 24.

Para el teorema de los 5/8 de la seccion siguiente, nos interesara estudiar la accion porproducto del centro Z(G) de G. El centro de G, recordemos, es el conjunto de elementos de Gque conmutan con todos los elementos del grupo, es decir, los z ∈ G tales que zg = gz, paratodo g ∈ G. Observese que si z ∈ Z(G), g−1zg = z para todo g ∈ G. El centro de G es unsubgrupo, por supuesto conmutativo.

La accion de Z(G) sobre G parte G en, digamos, r orbitas:

G = Z(G) ∪ (Z(G) · g2) ∪ (Z(G) · g3) ∪ · · · ∪ (Z(G) · gr) .

Cuando r = 1, entonces G = Z(G) y G es conmutativo; y recıprocamente. La observacioncasi mıstica que nos concierne ahora es que r no puede ser ni 2 ni 3. En otros terminos,

Lema 15.13 Si G no es conmutativo, entonces r ≥ 4 y |Z(G)| ≤ 14|G|.

Demostracion. Procederemos por reduccion al absurdo. Supondremos r = 3 y llegaremosa una contradiccion. El caso r = 2 queda como ejercicio 15.6.11 para el lector concienzudo.Ya hemos comentado que el centro del grupo D4 del cuadrado tiene tan solo dos elementos,a saber, la identidad y la rotacion de angulo π, y desde luego no es conmutativo. Ası que laconstante 1

4 del lema no se puede mejorar.Escribamos las orbitas disjuntas:

G = Z(G) ∪ (Z(G)ω) ∪ (Z(G)η)

Aligeramos ası la notacion general de mas arriba: ω = g2 y η = g3. La clave es localizar enque orbita estan ω2 y η2. Supongamos que ya sabemos (lo veremos mas abajo) que ω2 ∈(Z(G)η) –analogamente nos valdrıa con saber que η2 ∈ (Z(G)ω)–. Veamos que entonces Gha de ser conmutativo. Tomemos a y b dos elementos de G y comprobemos, mediante unanalisis por casos, que ab = ba. Los casos dependen de en que orbitas estan a y b, un total de9 posibilidades, o por simetrıa, 6. Veamos aquı uno solo de estos, por ejemplo a ∈ (Z(G)ω)y b ∈ (Z(G)ω). El resto de casos quedan para el lector concienzudo.

Escribimos: a = sω, b = tη, con s, t ∈ Z(G). Como ω2 ∈ (Z(G)η), podemos escribirb = uω2, con u ∈ Z(G). Pero entonces, usando repetidamente que los elementos de Z(G)conmutan con todos los elementos de G:

ab = sωuω2 = sωω2u = sω3u = sω2ωu = . . . = uω2sω = ba

Nos resta en esta demostracion ubicar ω2 o η2. Supongamos que44 no fuera que ω2 ∈(Z(G)η) o η2 ∈ (Z(G)ω). Observese que ω2 no puede estar en Z(G)ω porque entoncesω ∈ Z(G). Por tanto tendrıamos que ω2 ∈ Z(G) y η2 ∈ Z(G). Y, ¿ηω? Se sigue enseguida45

que ηω ∈ Z(G). Y ahora, por fin, la anorada contradiccion: como ηω ∈ Z(G), ηω2 = ηωω ∈Z(G)ω, pero como ω2 ∈ Z(G), se deduce que η ∈ Z(G), ¡contradiccion!

44De nuevo, reduccion al absurdo: ¡cuanta contradiccion!45¡Cuanto trabajo le estamos dejando, lector concienzudo!



15.6.4. Accion de conjugacion. Los 5/8 de Abel

Los 5/8 de Abel hacen referencia al teorema 15.14. Consideremos la accion por conjugacionde un grupo G sobre sı mismo. Recordemos que cada g actua por conjugacion:

x ∈ G −→ gxg−1 ∈ G .

Pongamos que hay un total de k orbitas distintas. Entre ellas hay unas especiales, las quetienen un solo elemento: si x ∈ G y la orbita de x bajo esta accion de G tiene un solo elemento,entonces gxg−1 tiene que ser x para todo g. Es decir, la orbita tiene un solo elemento si ysolo si x ∈ Z(G).

La otras orbitas tiene al menos dos elementos, ası que como G se parte en orbitas deconjugacion, tenemos que

|G| ≥ |Z(G)| + 2(k − |Z(G)|) ,de donde

|G|+ |Z(G)| ≥ 2k .

Si combinamos ahora esta desigualdad con el lema 15.13, obtenemos que si G no es conmu-tativo, entonces

# orbitas de conjugacion = k ≤ 58|G| .

Mientras que si el grupo es conmutativo, entonces

# orbitas de conjugacion = |G| .

Usemos el lema cuenta-orbitas para . . . contar el numero de orbitas. Para ello tomemos g ∈ Gy preguntemonos por los puntos que deja fijos por conjugacion. Seran los x ∈ G tales quegxg−1 = x. Es decir, los x que conmutan con g. Ahora el lema de Burnside nos dice que

# orbitas de conjugacion =1|G|

∑g∈G

# elementos que conmutan con g .

En otros terminos, el numero medio de elementos que conmutan con un elemento dado es elnumero de orbitas de conjugacion. Pero hay una interpretacion mas rica:

Teorema 15.14 Si G es un grupo no conmutativo, la probabilidad de que un par de elemen-tos conmuten es a lo sumo 5/8. Mientras que si G es conmutativo esa probabilidad es 1.

Asombroso, ¿verdad?: esa probabilidad no puede ser un numero entre 5/8 y 1. Precisemos. Seescogen dos elementos del grupo al azar equiprobablemente, con reemplazamiento. Es decir,cada par (x, y) de G×G tiene probabilidad 1/|G|2 de aparecer.

Doble conteo; matriz M con |G| filas y |G| columnas, que etiquetamos con los elementosde G. Ponemos un 1 o un 0 en el registro (x, y) segun conmuten x e y o no. Sea S la sumade los elementos de la matriz M . La probabilidad P buscada46 es

P =S

|G|2 .

46Admırese el lector de la habilidad nominativa de los autores: matriz M , suma S, probabilidad P . . .



La suma de los elementos de la fila etiquetada con x es el numero de elementos que conmutancon x. Por tanto, sumando por filas,

S =∑g∈G

# elementos que conmutan con g .

Y, por consiguiente, usando Burnside,

P =S

|G|2 =1|G||S||G| =

1|G| ×# orbitas de conjugacion ≤ 5

8,

donde (solo) en el ultimo paso hemos usado que el grupo es no conmutativo.

¿Y el mıstico factor 5/8? Pues no se puede mejorar. Es decir, hay un grupo no conmutativopara el que P es exactamente 5/8. De hecho, como pedimos verificar en el ejercicio 15.6.15,el grupo diedrico D4 tiene 5 orbitas al actuar por conjugacion sobre sı mismo.

15.6.5. Los grupos finitos de rotaciones de R3

Quizas el lector pudiera pensar que hay muchos grupos (finitos) de simetrıas rotacionalesen el espacio. Hemos visto ya los grupos de rotaciones de los solidos platonicos: el del tetraedro(con 12 elementos), los del cubo y el octaedro (con 24) y los del dodecaedro y el icosaedro(ambos con 60). Ademas, los grupos cıclicos Cn y Dn son tambien grupos de rotaciones en elespacio (asociados al prisma recto cuya base es un polıgono de n lados). Lo sorprendente delcaso es que no hay ninguno mas, como la numerologıa que presentamos en esta subseccionnos va a revelar. Pretendemos probar el siguiente resultado:

Teorema 15.15 Un grupo finito de rotaciones en el espacio es isomorfo a un grupo cıclico,a un grupo diedrico o a un grupo rotacional de uno de los solidos platonicos.

Demostracion. Supongamos que G es un grupo finito de rotacio-nes en el espacio. Un elemento g ∈ G (distinto de la identidad) esun giro de cierto angulo en torno a un eje E que pasa por el origen.Centraremos nuestra atencion en la accion sobre la esfera de radio 1de R3, que todas las rotaciones preservan, es decir, consideramosla accion del grupo finito dado a esa esfera unidad. Cada una deestas rotaciones fija dos (unicos) puntos de la esfera de radio 1, lospolos de la rotacion, salvo la identidad que fija todos los puntos.

E

Llamemos X al conjunto (finito) de todos los polos de las distintasrotaciones de G \ e.

El grupo G preserva la coleccion de puntos fijos X , vease el ejercicio 15.2.3, y es que six es polo de una rotacion h ∈ G, h = id y g es cualquier elemento del grupo G, entoncesg(x) es polo de (g h g−1) que es elemento de G. De manera que el grupo G actua sobre elconjunto de polos X y podemos aplicar el lema cuenta orbitas.

Cuando X tiene 2 elementos, que, como veremos, es un caso relevante, la accion de Gsobre X no es fiel, pues todos los elementos de G fijan de hecho esos dos elementos. Pero



vamos a aplicar el lema cuenta orbitas para acciones de grupos, ası que no nos preocupa sila accion es fiel o no. Cuando |X | ≥ 3, la accion sı es fiel.

Supongamos que la accion de G sobre X define r orbitas (disjuntas, claro), y tomemosun representante de cada una de ellas, digamos x1, x2, . . . , xr. El lema cuenta-orbitas nosdice que el numero de orbitas coincide con el numero medio de puntos de X que fijan loselementos de G:

r =1|G|

∑g∈G

|F (g)| .

La identidad, claro, fija todos los elementos de X . Si g no es la identidad (hay |G| − 1 deestas rotaciones), entonces fijara exactamente sus dos polos. Ası que

() r =1|G|

[|F (e)| +

∑g =e

|F (g)|]

=1|G|

[|X |+ 2 (|G| − 1)

].

Como los elementos de X se reparten entre las orbitas,

|X | =r∑

i=1

|OG(xi)| .

Sustituyendo en la expresion () y reordenando los terminos, llegamos a que

2(

1− 1|G|

)= r − 1

|G|

r∑i=1

|OG(xi)| = r −r∑

i=1

1|EG(xi)|

=r∑

i=1

(1− 1|EG(xi)|

)(en el penultimo paso utilizamos la relacion habitual |G| = |OG(xi)| |EG(xi)|). Ya estamosdonde querıamos; ahora solo hay que hacer cierta numerologıa. Si |G| ≥ 2 (esto es, G noconst unicamente de la identidad), el numero de la izquierda esta entre

1 ≤ 2(

1− 1|G|

)< 2 .

Mientras que cada uno de los sumandos de la derecha (observese que cada EG(xi) tiene almenos dos elementos, la identidad y la rotacion de la que xi es polo) cumple que

12≤ 1− 1

|EG(xi)|< 1 .

Ası que estamos sumando r numeros del intervalo [1/2, 1) para obtener uno de [1, 2). Conun solo sumando (r = 1) no basta, y con cuatro sumandos o mas nos pasamos, sin duda.Ası que solo nos queda la posibilidad de que, o bien r = 2, o bien r = 3.

Comencemos con el caso r = 2. Tenemos solo dos orbitas y dos representantes suyos, x1

y x2. El lema cuenta-orbitas nos dice que

2(

1− 1|G|

)= 2− 1

|G|

[|OG(x1)|+ |OG(x2)|

]y, por tanto, 2 = |OG(x1)|+ |OG(x2)| .



Las dos orbitas constan de un unico elemento, es decir, OG(xj) = xj, j = 1, 2. De maneraque todos los elementos fijan x1 y x2 y por tanto todas las rotaciones de G tienen, como ejede giro, el determinado por x1 y x2. Esto es, G es un grupo finito de rotaciones en un plano(el perpendicular al eje que pasa por el origen). Esto supone (vıa un resultado que pedimosprobar en el ejercicio 15.7.1) que G ha de ser cıclico.

El caso r = 3 requiere mas analisis: solo hay tres orbitas, cuyos representantes son x1, x2

y x3. El lema de Burnside nos dice que, en este caso,

1 +2|G| =

1|EG(x1)|

+1

|EG(x3)|+

1|EG(x3)|

.

Los tres numeros de la derecha han de sumar algo que es mayor que 1 (el miembro dela izquierda). Fijemonos en que al menos uno de los estabilizadores ha de tener tamano 2(pues tres numeros menores o iguales que 1/3 suman menos de 1). Y esto nos deja pocasposibilidades. Concretamente,

que con dos de estos numeros ya sumemos 1. Esto es, que sean 1/2, 1/2 y 1/n, conn ≥ 2. Si n = 2, G es un grupo de orden 4. Y se puede ver que es isomorfo al 4-grupode Klein (visto como el grupo diedrico de 4 elementos). Para n ≥ 3, el grupo tiene 2nelementos, y se puede comprobar que es isomorfo a Dn.

Que los numeros sean 1/2, 1/3 y 1/3, en cuyo caso el orden de G es 12. Aquı nosencontraremos con el grupo de rotaciones del tetraedro.

Si los numeros son 1/2, 1/3 y 1/4, el orden del grupo es 24, y llegamos al grupo derotaciones del cubo o del octaedro.

Por ultimo, si tenemos 1/2, 1/3 y 1/5, el orden es 60 y el grupo correspondiente es elde las rotaciones del dodecaedro o del icosaedro.

Observara el lector que hemos omitido el detalle de los argumentos que permiten concluirque, efectivamente, en cada uno de los casos nos encontramos con el grupo rotacional delsolido platonico correspondiente, pues nuestro interes era comprobar como la aplicacion dellema de Burnside conducıa a esta fascinante numerologıa.


15.6.1 (a) Demuestrese que, en todo grupo, el elemento neutro es unico.(b) Pruebese que para cualesquiera dos elementos x e y de un grupo, (x · y)−1 = y−1 · x−1.

15.6.2 (a) ¿Que propiedades tiene la tabla de productos de un grupo abeliano?(b) Pruebese que no todo cuadrado latino en n sımbolos se corresponde con la tabla de un grupo conesos elementos.(c) Considerese la tabla de productos de la derecha. e a b

e e a ba a a ab b a a

Compruebese que esteproducto es asociativo. Sin embargo, claramente el conjunto e, a, b, conesta operacion de producto, no es un grupo.

15.6.3 Compruebese que SO(n), el conjunto de las matrices n × n con entradas reales tales queAAt = I y det(A) = 1 es un grupo con la operacion de producto de matrices.



15.6.4 Sea G un grupo y sea H un subconjunto de G. Pruebese que H es un subgrupo si y solo sixy−1 ∈ H para todo x, y ∈ H.

15.6.5 Supongamos que un grupo G esta formado unicamente por involuciones. Es decir, g2 = idpara todo g ∈ G. Compruebese que G es conmutativo.

15.6.6 Sea G un grupo cualquiera. Supongamos que, para un cierto numero natural k, k ≥ 1,se cumple que para cualesquiera g, h ∈ G y para las tres potencias sucesivas n = k, k + 1, k + 2,(gh)n = gnhn . Se trata de comprobar que entonces el grupo G es conmutativo.

15.6.7 (a) Sea G un grupo de simetrıas de 1, 2, 3, 4 de orden 4. Compruebese que G es isomorfoa C4 o a V4. Compruebese que, si tiene orden 8, entonces es isomorfo a D4.(b) Compruebese que todo grupo de orden 3 es isomorfo al C3.15.6.8 (a) Compruebese que el centro de G,

Z(G) = g ∈ G : zg = gz para todo z ∈ G

es un subgrupo (abeliano) de G.(b) ¿Es Z(G) el mayor subgrupo conmutativo de un grupo dado?(c) Compruebese que el centro del grupo diedrico Dn (las 2n isometrıas del n-gono regular) esta for-mado (solo) por la identidad (n impar) y por la identidad y la rotacion de angulo π (n par).

15.6.9 Compruebese que el grupo alternado A4 no tiene subgrupos de orden 6.

15.6.10 El grupo simetrico S4 tiene 4! = 24 elementos. Esto nos dice que los posibles grupos desimetrıa de 1, 2, 3, 4 pueden tener 1, 2, 3, 4, 6, 8, 12 y 24 elementos. Identifıquense grupos de simetrıasde 1, 2, 3, 4 con esos tamanos.

15.6.11 Compruebese que el numero de orbitas de la accion por producto de su centro sobre un grupono conmutativo no puede ser 2. Tampoco puede ser 3, pero eso ya lo vimos en el lema 15.13.

15.6.12 Sea G ⊂ Sn. Compruebese que si G es cerrado para la composicion, entonces G es subgrupo.

15.6.13 Tenemos dos conjuntos A y B y consideramos el conjunto Z de aplicaciones de A en B.Sea ahora G un grupo de simetrıas de A. Comprobar que si a cada g de G le asignamos g dada porser la biyeccion de Z en sı, que a f ∈ Z le asocia g(f) definida por

g(f)(a) = f(g−1(a)), para cada a ∈ A .

Compruebese que esto define una accion de G sobre Z.

15.6.14 Compruebese que si escogen dos elementos de un grupo no conmutativo al azar (equiproba-blemente) pero sin reemplazamiento la probabilidad Q de que estos dos elementos conmuten cumple

Q ≤ (5/8)|G| − 1|G| − 1

15.6.15 Compruebese que el grupo diedrico D4 tiene cinco orbitas al actuar por conjugacion sobresı mismo, bien directamente, calculando las orbitas, bien calculando el numero de puntos fijados porcada elemento del grupo y aplicando Burnside.

15.6.16 Considerese el grupo de rotaciones del cubo, entendido como grupo de rotaciones de la esferaunidad. Lo hacemos actuar ahora sobre X , el conjunto de los polos de las rotaciones. Determınenselas tres orbitas. Hagase lo mismo para los restantes solidos platonicos.


combinatoria con simetr´ıas - uamverso.mat.uam.es/~pablo.fernandez/cap15-burnside.pdf2 grupos de 1...

Documents