Lema de Burnside: cómo contar órbitas con ejemplos resueltos

Actualizado el
El lema de Burnside cuenta cuántos objetos realmente distintos hay cuando dos se consideran iguales si una simetría transforma uno en otro. La receta es: para cada simetría, cuenta cuántos objetos deja exactamente igual, suma esas cantidades y divide entre el número de simetrías. Es la herramienta estándar para problemas como «¿cuántos collares distintos se pueden hacer con 4 cuentas de 2 colores?».
Enunciado
Sea G un grupo finito que actúa sobre un conjunto finito X. Para cada g ∈ G, sea Xg = {x ∈ X : g·x = x} el conjunto de elementos que g deja fijos. Entonces el número de órbitas, |X/G|, es:
|X/G| = (1/|G|) · Σg ∈ G |Xg|
Es decir, el número de órbitas es la media del número de puntos fijos de los elementos del grupo.
Vocabulario en un problema de coloraciones: X es el conjunto de todas las coloraciones «con posición» (sin tener en cuenta simetrías); G es el grupo de giros (y, si se permite, de reflexiones); una órbita es el conjunto de coloraciones que se pueden convertir unas en otras con un movimiento. Contar órbitas es contar coloraciones distintas de verdad.
Un nombre engañoso
Pese al nombre, el resultado no es de Burnside. Augustin-Louis Cauchy ya lo conocía en 1845 y Ferdinand Georg Frobenius lo publicó en 1887. William Burnside lo enunció y demostró en su libro de 1897 sobre grupos finitos, atribuyéndolo a Frobenius. Por eso también se llama lema de Cauchy-Frobenius o, en broma, «el lema que no es de Burnside». Tampoco hay que confundirlo con el teorema de Burnside de teoría de grupos (el teorema paqb, según el cual todo grupo de orden paqb con p y q primos es resoluble), que sí es suyo y lo publicó en 1904.
Demostración por doble conteo
Se cuentan de dos formas los pares (g, x) con g·x = x.
- Por elementos del grupo: para cada g hay |Xg| elementos fijos, así que el total es Σg |Xg|.
- Por elementos de X: para cada x, los g que lo fijan forman su estabilizador Gx, así que el total es Σx |Gx|.
- Por el teorema de la órbita y el estabilizador, |Gx| = |G|/|Órb(x)|. Entonces Σx |Gx| = |G| · Σx 1/|Órb(x)|.
- Agrupando los x por órbitas: cada órbita O aporta |O| sumandos iguales a 1/|O|, es decir, 1. La suma Σx 1/|Órb(x)| es, por tanto, el número de órbitas.
- Igualando las dos cuentas: Σg |Xg| = |G| · |X/G|, que es el lema.
Ejemplos resueltos
1. Collares de 4 cuentas con 2 colores (solo giros)
Hay 24 = 16 coloraciones con posición. El grupo de giros de un cuadrado tiene 4 elementos.
| Giro | Ciclos sobre las cuentas | Coloraciones fijas |
|---|---|---|
| 0° (identidad) | 4 ciclos de 1 | 24 = 16 |
| 90° | 1 ciclo de 4 | 21 = 2 |
| 180° | 2 ciclos de 2 | 22 = 4 |
| 270° | 1 ciclo de 4 | 21 = 2 |
Una coloración queda fija por un giro solo si todas las cuentas de cada ciclo tienen el mismo color; por eso cada ciclo aporta un factor 2. Total: (16 + 2 + 4 + 2)/4 = 24/4 = 6 collares distintos. Se pueden listar: todo blanco, todo negro, una negra, una blanca, dos negras juntas y dos negras opuestas.
2. Collares de 3 cuentas con 3 colores
33 = 27 coloraciones y 3 giros (0°, 120°, 240°). La identidad fija las 27; cada giro de 120° o 240° es un único ciclo de 3 y fija solo las 3 monocolores. Resultado: (27 + 3 + 3)/3 = 33/3 = 11.
3. Collares de 6 cuentas con 2 colores
Giros de 0°, 60°, 120°, 180°, 240° y 300°. Sus ciclos sobre las 6 cuentas son 6, 1, 2, 3, 2 y 1, respectivamente (el número de ciclos del giro de k posiciones es el máximo común divisor de k y 6). Coloraciones fijas: 64, 2, 4, 8, 4 y 2. Total: 84/6 = 14.
4. Caras de un cubo con 3 colores
Hay 36 = 729 coloraciones con posición y 24 giros del cubo. Se agrupan por tipos:
| Tipo de giro | Cuántos | Ciclos sobre las caras | Fijas por cada uno |
|---|---|---|---|
| Identidad | 1 | 6 | 36 = 729 |
| 90° o 270° por un eje de caras opuestas | 6 | 3 | 33 = 27 |
| 180° por un eje de caras opuestas | 3 | 4 | 34 = 81 |
| 120° o 240° por una diagonal del cubo | 8 | 2 | 32 = 9 |
| 180° por un eje de aristas opuestas | 6 | 3 | 33 = 27 |
Suma: 729 + 6·27 + 3·81 + 8·9 + 6·27 = 729 + 162 + 243 + 72 + 162 = 1 368. Número de cubos distintos: 1 368/24 = 57. Con 2 colores la misma tabla da (64 + 48 + 48 + 32 + 48)/24 = 240/24 = 10.
Todos estos resultados están comprobados contando por fuerza bruta: generando todas las coloraciones y agrupándolas por órbitas salen 6, 11, 14, 57 y 10.
Fórmula general para collares (solo giros)
Para n cuentas y k colores, el giro de j posiciones tiene mcd(j, n) ciclos y fija kmcd(j, n) coloraciones, así que
N(n, k) = (1/n) · Σj=0n−1 kmcd(j, n)
Agrupando por divisores se escribe también como (1/n)·Σd | n φ(d)·kn/d, donde φ es la función de Euler que aparece en el teorema de Euler de la aritmética modular. Con n = 6 y k = 2: (1/6)(1·64 + 1·8 + 2·4 + 2·2) = 84/6 = 14, igual que antes.
Errores habituales
- Dividir el total entre el número de simetrías. 16/4 = 4 no es el número de collares del ejemplo 1: las coloraciones simétricas tienen órbitas más pequeñas. Precisamente para eso sirve el lema.
- Olvidar la identidad. Fija todas las coloraciones y suele ser el sumando más grande.
- No decidir si se permiten reflexiones. Un collar que se puede dar la vuelta (pulsera) tiene como grupo el diédrico, con el doble de elementos, y el resultado puede cambiar.
- Contar mal los ciclos. Conviene numerar las posiciones y escribir la permutación de cada simetría.
Relación con otros resultados
El lema se apoya en el teorema de la órbita y el estabilizador, que a su vez sale del teorema de Lagrange sobre el orden de los subgrupos. Su generalización es la teoría de enumeración de Pólya, que no solo cuenta las coloraciones sino que dice cuántas hay con cada reparto de colores, mediante el índice de ciclos del grupo. Cuando todas las simetrías dejan fijo solo lo obvio, el recuento se reduce a dividir, igual que los números combinatorios del binomio de Newton se obtienen dividiendo las ordenaciones entre las permutaciones que no cambian nada.
Además de en combinatoria, se usa en química para contar isómeros y en informática para contar estructuras salvo simetría. En el plano complejo, los n giros de un collar de n cuentas se corresponden con las n raíces n-ésimas de la unidad, las n soluciones de zn = 1 cuya existencia asegura el teorema fundamental del álgebra.
Preguntas frecuentes
¿Qué dice el lema de Burnside?
Que el número de órbitas de un grupo finito que actúa sobre un conjunto finito es la media del número de elementos fijos por cada elemento del grupo: |X/G| = (1/|G|)·Σ|Xᵍ|.
¿Cuántos collares distintos hay con 4 cuentas y 2 colores?
Seis, si solo se permiten giros: (16 + 2 + 4 + 2)/4 = 6.
¿Es lo mismo el lema de Burnside que el teorema de Burnside?
No. El lema de conteo de órbitas se debe en realidad a Cauchy y Frobenius; el teorema de Burnside de teoría de grupos dice que los grupos de orden pᵃqᵇ son resolubles.
¿Cuántas formas distintas hay de pintar las caras de un cubo con 3 colores?
57, considerando iguales las que se obtienen girando el cubo.
RELACIONADOS