Simetría y conteo · Definición

Lema de Burnside

combinatoria enumerativasimetría y conteo

Antes de empezar necesitas conocer

Cuando un grupo actúa sobre un conjunto, muchas configuraciones son equivalentes entre sí. Este lema permite contar las clases de equivalencia sin listarlas una a una.

Definición

El lema de Burnside (también llamado de Cauchy-Frobenius) afirma que el número de órbitas de una acción de un grupo finito G sobre un conjunto X es el promedio del número de puntos fijos de los elementos de G.

\[|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|\]

Sea G un grupo finito que actúa sobre X. Por el teorema de órbita-estabilizador, \(|G| = |G_x|\cdot|Gx|\) para cada x, lo que lleva a contar pares (g,x) con gx = x de dos formas distintas. El resultado es \(\sum_{g}|X^g| = \sum_{x}|G_x| = |G|\cdot|X/G|\), que es la fórmula del lema.

Ejemplo guía: al colorear las caras de un cuadrado con dos colores usando las rotaciones de \(C_4\) (identidad, giros de 90°, 180° y 270°), la identidad fija 16 coloraciones, los giros de 90° y 270° fijan 2 cada uno y el giro de 180° fija 4. Así, el número de coloraciones distintas es \((16+2+4+2)/4 = 6\).

Error típico: olvidar incluir la identidad en la suma, que siempre fija todos los elementos de X. Omitirla reduce la suma y, en el ejemplo anterior, daría \((2+4+2)/4 = 2\) en lugar de 6.

Para pensar

¿Por qué la suma de puntos fijos siempre es múltiplo de \(|G|\)?

Porque \(\sum_{g}|X^g| = |G|\cdot|X/G|\) y el número de órbitas \(|X/G|\) es un entero.

Ejercicios 10

  1. Según el lema de Burnside, ¿qué cuenta la expresión \(\frac{1}{|G|}\sum_{g}|X^g|\)?
  2. ¿Cuántos elementos tiene el grupo de rotaciones del cuadrado \(C_4\)?
  3. ¿Qué elemento del grupo siempre fija todos los puntos de X?
  4. Si \(|G| = 6\) y la suma de puntos fijos es 18, ¿cuántas órbitas hay?
  5. ¿Qué nombre alternativo recibe el lema de Burnside?
  6. Un grupo de orden 4 actúa sobre un conjunto de 10 elementos. Sus puntos fijos suman \(4+2+2+0\). ¿Cuántas órbitas hay?
  7. ¿Cuántas coloraciones distintas hay al pintar un cuadrado con 3 colores, usando solo giros (grupo \(C_4\) con identidad, 90°, 180° y 270°)?
  8. Un grupo de orden 3 actúa sobre un conjunto de 7 elementos con puntos fijos 7, 1 y 1. ¿Cuántas órbitas hay?
  9. ¿Cuántos collares distintos de 4 cuentas con 2 colores hay, si se permiten giros del grupo \(C_4\)?
  10. Un grupo de 6 elementos actúa sobre un conjunto X. La suma de los puntos fijos de todos sus elementos, \(\sum_{g}|X^g|\), es 20. ¿Qué se puede concluir?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.