---
tags: combinatorics, burnside-lemma, group-theory
---

# Burnside's lemma
Este teorema es una herramienta muy poderosa para contar y distinguir objetos bajo ciertas simetrías.

## Permutaciones
Una permutación es una función biyectiva $f$ de un conjunto $S$ a sí mismo. Es decir, $f : S \to S$. Usualmente el conjunto $S$ es el conjunto $\{1, 2, \ldots, n\}$.

Usualmente se denota una permutación con la notación de dos columnas. Ejemplo, si $n=4$:
$$
\begin{pmatrix}
1 && 2 && 3 && 4 \\
3 && 2 && 4 && 1
\end{pmatrix}
$$

También podemos descomponer cualquier permutación como una unión de ciclos disjuntos, por ejemplo: $f = (1 \quad 3 \quad 4)(2)$.

## Grupos
Un grupo es un conjunto $G$ equipado con una operación $\cdot$ que combina a dos elementos $a, b \in G$ para formar un nuevo elemento $a \cdot b \in G$. Además, debe cumplir las siguientes propiedades:
- Asociatividad: Para cada $a, b, c \in G$, se cumple que $(a \cdot b) \cdot c = a \cdot (b \cdot c)$. Entonces, podemos decir que $(a \cdot b) \cdot c = a \cdot (b \cdot c) = a \cdot b \cdot c$.
- Elemento identidad: existe un elemento $e \in G$ tal que para todo $a \in G$, se cumple que $e \cdot a = a \cdot e = a$.
- Elemento inverso: para cada elemento $a \in G$, existe un $a^{-1} \in G$ tal que $a \cdot a^{-1} = a^{-1} \cdot a = e$, donde $e$ es la identidad.

Para definir el lema, estaremos usando en su mayoría grupos cuyos elementos son permutaciones y la operación $\cdot$ es la composición de funciones.

De esa forma, vemos que las tres propiedades se cumplen:
- La identidad sería la permutación
$$ \begin{pmatrix}
1 && 2 && \ldots && n \\
1 && 2 && \ldots && n
\end{pmatrix}
$$
- Para calcular la inversa de una permutación $f$, solo necesitamos calcular $f^{-1}$.

Ejemplo: sea $G$ un grupo con todas las permutaciones de $4$ elementos. Si tenemos las siguientes dos permutaciones:
$$
f = \begin{pmatrix}
1 && 2 && 3 && 4 \\
3 && 2 && 4 && 1
\end{pmatrix}
$$
$$
g = \begin{pmatrix}
1 && 2 && 3 && 4 \\
2 && 1 && 4 && 3
\end{pmatrix}
$$

Entonces $f \cdot g = (g \circ f)$:
$$
f \cdot g = \begin{pmatrix}
1 && 2 && 3 && 4 \\
4 && 1 && 3 && 2
\end{pmatrix}
$$

$$
(f \cdot g)^{-1} = \begin{pmatrix}
1 && 2 && 3 && 4 \\
2 && 4 && 3 && 1
\end{pmatrix}
$$

## Algunos grupos comunes
- $S_n$: es el **grupo simétrico**, contiene todas las $n!$ permutaciones de $n$ elementos.
- $C_n$: es el **grupo cíclico**, contiene todas las $n$ permutaciones de $n$ elementos donde dichos elementos se van *rotando* a la izquierda. Es decir, contiene a:
$$
\begin{pmatrix}
1 && 2 && \ldots && n-1 && n \\
1 && 2 && \ldots && n-1 && n
\end{pmatrix}
$$
$$
\begin{pmatrix}
1 && 2 && \ldots && n-1 && n \\
2 && 3 && \ldots && n && 1
\end{pmatrix}
$$
$$
\begin{pmatrix}
1 && 2 && \ldots && n-1 && n \\
3 && 4 && \ldots && 1 && 2
\end{pmatrix}
$$
$$
\cdots
$$
$$
\begin{pmatrix}
1 && 2 && \ldots && n-1 && n \\
n && 1 && \ldots && n-2 && n-1
\end{pmatrix}
$$

## Acciones de un grupo
Definimos a la **acción** de un grupo $G$ sobre un conjunto de elementos $X$ como una función $\phi : G \times X \to X$, es decir, recibe un elemento del grupo $G$ y un elemento de $X$, y nos devuelve otro elemento de $X$. Debe cumplir con las siguientes propiedades:
- Elemento identidad: existe un elemento $\epsilon \in G$ tal que para todo $x \in X$, se cumple que $\phi(\epsilon, x) = x$.
- Composición: $\phi(g \cdot h, x) = \phi(g, \phi(h, x))$ para todo $g, h \in G$ y $x \in X$. Podemos simplificar la notación usando $\phi(g, x) = g \times x$, por lo tanto, esta propiedad nos dice que $(g \cdot h) \times x = g \times (h \times x)$.

### Puntos fijos
Para un elemento $g \in G$, decimos que $x \in X$ es un punto fijo de $g$ si $g \times x = x$. Es decir, $x$ es invariante bajo la acción de $g$.

Denotamos como $X^g = \{x \in X \mid g \times x = x\}$ al conjunto de todos los elementos $x$ que son invariantes bajo la acción de $g$.

### Órbitas
Dado un elemento $x \in X$, definimos a la órbita de $x$ como $G \times x = \{g \times x \mid g \in G\}$. Es decir, es el conjunto de aplicarle a $x$ todas las acciones del grupo $G$.

## Ejemplo
Sea $G$ el grupo definido por los siguientes 4 elementos:
- $a$: rotar $0^\circ$ a la izquierda.
- $b$: rotar $90^\circ$ a la izquierda.
- $c$: rotar $180^\circ$ a la izquierda.
- $d$: rotar $270^\circ$ a la izquierda.

Donde la operación $\cdot$ del grupo es la composición de rotaciones, es decir, si $g_m$ rota $m^\circ$ y $g_n$ rota $n^\circ$, entonces la composición $g_m \cdot g_n$ rota $(m+n)^\circ$.

Vemos que $a$ es la identidad de $G$ y los inversos quedan de la siguiente manera:
- $a^{-1} = a$
- $b^{-1} = d$
- $c^{-1} = c$
- $d^{-1} = b$

También vemos que este grupo es "prácticamente el mismo" que el grupo cíclico $C_4$. De forma más precisa, decimos que es *isomorfo*.

Sea $X$ el conjunto de cuadrados con vértices etiquetados del $1$ al $4$, donde cada vértice tiene un color de $n$ posibles. Entonces $|X| = n^4$.

Sea $g \times x$ la acción de rotar el cuadrado $x$ el número de grados que indique $g$.

Ejemplo: sea $x$ el siguiente cuadrado:
Entonces, veamos cómo queda $x$ al aplicarle las acciones definidas por el grupo $G$:
- $x_0 = a \times x$:
- $x_1 = b \times x$:
- $x_2 = c \times x$:
- $x_3 = d \times x$:

Vemos que la órbita del cuadrado $x$ son todos los cuadrados que acabamos de dibujar, es decir, $G \times x = \{x_0, x_1, x_2, x_3\}$.

Ahora hallemos los puntos fijos de cada elemento de $G$:
- $a$: Tenemos que el conjunto $X^a$ contiene a exactamente todos los cuadrados de $X$. Entonces $|X^a| = n^4$.
- $b$: Tenemos que el conjunto $X^b$ contiene todos los cuadrados coloreados con el mismo color. Entonces $|X^b| = n$. Ejemplo de un elemento que pertenece a $X^b$:
- $c$: $X^c$ contiene a todos los cuadrados con el mismo color en los vértices opuestos. Entonces $|X^c| = n^2$. Ejemplo de un elemento que pertenece a $X^c$:
- $d$: $X^d$ contiene todos los cuadrados coloreados con el mismo color, de la misma forma que $b$. Entonces $|X^d| = n$. Ejemplo de un elemento que pertenece a $X^d$:

## Contando clases de equivalencia
Las órbitas particionan al conjunto $X$, es decir, si un elemento $x \in X$ tiene como órbita al conjunto $A$, entonces todos los elementos de $A$ también tienen como órbita a $A$, y por cada elemento $x' \not \in A$, la órbita de $x'$ no comparte ningún elemento con $A$.

Es decir, la relación "$x$ y $y$ tienen la misma órbita" ($x \sim y$), es una **relación de equivalencia**.
Sea $X/G = \{G \times x \mid x \in X\}$ el conjunto de todas las órbitas de $X$ bajo la acción de $G$.

Una forma de interpretar lo que nos quiere decir la cantidad de clases de equivalencia $|X/G|$ es la siguiente:
- En el ejemplo anterior, supongamos que queremos contar cuántas formas hay de colorear los vértices de un cuadrado con $n$ colores, donde todas sus rotaciones se consideran equivalentes y solo se cuentan una vez.
- Podemos ver al grupo $G$ como el grupo de *permutaciones invariantes*, pues vemos justamente que al aplicar cualquiera de sus elementos a algún cuadrado, lo deja equivalente. Eso implica que para un cuadrado $x \in X$, todos los elementos dentro de su órbita $G \times x$ son equivalentes y solo se cuentan una vez.
- Es por ello que nuestro objetivo será **contar cuántas clases de equivalencia existen**, y esa será la respuesta al problema. Aquí es donde entra Burnside's Lemma.

## Burnside's Lemma
El número de clases de equivalencia de un conjunto $X$ bajo la acción de un grupo $G$ es igual al promedio del número de puntos fijos en $X$ de cada elemento de $G$, es decir:
$$
|X/G| = \dfrac{1}{|G|} \sum_{g \in G} |X^g|
$$

Retomando el ejemplo de los cuadrados, tenemos que:
$$
\begin{align}
|X/G| &= \dfrac{1}{4} (|X^a| + |X^b| + |X^c| + |X^d|) \\
&= \dfrac{1}{4} (n^4 + n + n^2 + n) \\
&= \dfrac{n^4+n^2+2n}{4}
\end{align}
$$

La importancia de este lema es que resulta mucho más fácil contar el número de puntos fijos que contar el número de clases de equivalencia.

## Generalización del ejemplo
Vamos a generalizar el ejemplo anterior, ahora considerando polígonos de $k$ vértices donde sus rotaciones son equivalentes.

El grupo $G$ de rotaciones posibles sería $C_k$, veamos su estructura:
Tomando $k=6$, tenemos las siguientes permutaciones:
- $f_0 = (1)(2)(3)(4)(5)(6)$
- $f_1 = (1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6)$
- $f_2 = (1 \quad 3 \quad 5)(2 \quad 4 \quad 6)$
- $f_3 = (1 \quad 4)(2 \quad 5)(3 \quad 6)$
- $f_4 = (1 \quad 5 \quad 3)(2 \quad 6 \quad 4)$
- $f_5 = (1 \quad 6 \quad 5 \quad 4 \quad 3 \quad 2)$

Por cada permutación $a$, lo que se hace es lo siguiente:
- Descomponerla en ciclos.
- Para hallar $|X^a|$, vemos que basta con colocar los "colores" en los ciclos, de tal forma que cada ciclo quede con el mismo color.
- Sustituir en la fórmula.

Es decir, la fórmula se parece a:
$$
|X/G| = \dfrac{1}{k} \sum_{i=0}^{k-1} n^{C(f_i)}
$$
Donde $C(f)$ es el número de ciclos de la permutación $f$. Vemos que $C(f_i)=\gcd(i, k)$ y que la longitud de cada ciclo es $k/\gcd(i, k)$. Entonces la fórmula final queda como:
$$
|X/G| = \dfrac{1}{k} \sum_{i=0}^{k-1} n^{\gcd(i, k)}
$$

Podemos simplificarla aún más viendo que $\gcd(i, k)$ siempre es un divisor de $k$. Supongamos que $d | k$ y que $\gcd(i, k) = d$, entonces hay $\varphi(k/d)$ valores de $i$ tal que $\gcd(i, k) = d$, por lo que podemos reescribir la fórmula como:
$$
|X/G| = \dfrac{1}{k} \sum_{d|k} \varphi(k/d) n^d
$$

Analizándola, vemos que por cada divisor $d$ de $k$, hay $\varphi(k/d)$ permutaciones que cumplen con lo siguiente: tiene $d$ ciclos y cada uno tiene longitud $k/d$.

## Ejemplo: Lyndon words
Dada una cadena $s$ decimos que es un *Lyndon word* si es aperiódica y es la rotación lexicográfica más pequeña de todas sus rotaciones. Ejemplos:
- La cadena $s=0011$ cumple.
- La cadena $s=000$ no cumple porque es periódica.
- La cadena $s=1100$ no cumple pues no es la mínima rotación ya que puede ser rotada y así obtener $s'=0011$.

Dados $k$ y $n$, hallar el número de *Lyndon words* de tamaño $k$, tomadas del lenguaje generado por un alfabeto de tamaño $n$.

Para resolver el problema, veamos que es muy similar al de contar collares equivalentes bajo rotaciones, con la restrición adicional de que sean aperiódicos. Sea $f_n(k)$ el número de collares de tamaño $k$ con $n$ colores disponibles y sea $g_n(k)$ la respuesta a este problema. Vemos que ahora los collares son cadenas y los posibles colores son los símbolos del alfabeto.

Vemos que cualquier cadena de tamaño $k$ se puede expresar como $s=\underbrace{t \cdots t}_\text{d veces}=t^d$, donde $t$ tiene el tamaño mínimo y $d$ es el número de veces que concatenamos $t$ con sí misma. De esta forma vemos que $t$ tiene que ser aperiódica, pues si no lo fuera, existe otra cadena $u$ tal que $t=u^r$ para $r \geq 2$, entonces $s=t^d=(u^r)^d=u^{rd}$, pero como la longitud de $u$ es más chica que la $t$, se contradice la minimalidad de $t$. Como $t$ es única, decimos que $t$ es la cadena *representante* de $s$.

Por lo tanto, dada una cadena $s$ de longitud $k$ tal que $s=t^d$, vemos que $d | k$, pues $t$ tiene longitud $k/d$. Si quisieramos contar todas las posibles cadenas $s$, otra forma de hacerlo es simplemente contar el número de cadenas representantes aperiódicas, y como sabemos que cada divisor $d$ de $k$ nos aporta cadenas aperiódicas de tamaño $k/d$, entonces se cumple que:
$$
f_n(k) = \sum_{d | k} g_n(k/d)
$$
O usando el lenguaje de las convoluciones de Dirichlet, tenemos que $f_n(k) = g_n(k) * \textbf{1}$. Para despejar $g_n(k)$ usamos inversión de Möbius, y tenemos que:
$$
\begin{align}
g_n(k) &= f_n(k) * \mu(k) \\
&= \dfrac{n^k * \varphi(k)}{k} * \mu(k) \\
&= \dfrac{n^k}{k} * \dfrac{\varphi(k)}{k} * \mu(k) \\
&= \dfrac{n^k}{k} * \dfrac{\mu(k) * k}{k} * \mu(k) \\
&= \dfrac{n^k}{k} * \dfrac{\mu(k)}{k} * \textbf{1} * \mu(k) \\
&= \dfrac{n^k}{k} * \dfrac{\mu(k)}{k} * \varepsilon \\
&= \dfrac{n^k * \mu(k)}{k} \\
&= \dfrac{1}{k} \sum_{d | k} n^d \mu \left( \dfrac{k}{d} \right)
\end{align}
$$

## Ejemplo: el problema del brazalete
Es una variante del problema anterior: queremos colorear un brazalete de $k$ cuentas con $n$ colores disponibles, pero ahora tomando en cuenta que tanto las rotaciones como las **reflexiones** son equivalentes.

El grupo que nos va a servir para resolver el problema es el grupo diedral $D_k$, contiene tanto rotaciones como reflexiones de un polígono de $k$ vértices. Por lo tanto, el número de permutaciones en este grupo será de $2k$: $k$ rotaciones y $k$ reflexiones.

Veamos cómo se ven dos reflexiones cuando $k=6$:


Vemos que podemos escoger un par de vértices opuestos que actuará como eje de simetría, y los demás se reflejan en él. Tenemos $k/2$ formas de escoger dicho eje.

Pero también podemos escoger dos puntos medios de arcos opuestos sobre la circunferencia, y esto nos da otras $k/2$ reflexiones.

Ahora veamos cómo se ve una reflexión cuando $k=5$:

Vemos que para fijar un eje de simetría, escogemos un vértice y el punto medio de la arista opuesta. Tenemos $k$ formas de hacerlo.

Para analizar la estructura de estas nuevas permutaciones reflexivas, hay que separar en casos cuando $k$ es par e impar:
- Cuando $k$ es par:
- Cuando tenemos un eje de simetría determinado por dos vértices opuestos, tenemos $2$ ciclos de tamaño $1$ y $k/2-1$ ciclos de tamaño $2$. Hay $k/2$ permutaciones con estas características.
- Cuando tenemos un eje de simetría determinado por dos arcos opuestos, tenemos $k/2$ ciclos de tamaño $2$. Hay $k/2$ permutaciones con estas características.
- Cuando $k$ es impar: tenemos $1$ ciclo de tamaño $1$ y $(k-1)/2$ ciclos de tamaño $2$. Hay $k$ permutaciones con estas características.

Por lo tanto, cuando $k$ es par, la fórmula queda como:
$$
\begin{align}
|X/G| &= \dfrac{1}{2k} \left( \sum_{d|k} \varphi(k/d) n^d + \dfrac{k}{2}n^2 n^{k/2-1} + \dfrac{k}{2}n^{k/2} \right) \\
&= \dfrac{1}{2k} \left( \sum_{d|k} \varphi(k/d) n^d + \dfrac{k}{2}n^{k/2}(n+1) \right)
\end{align}
$$

Y cuando $k$ es impar:
$$
\begin{align}
|X/G| &= \dfrac{1}{2k} \left( \sum_{d|k} \varphi(k/d) n^d + kn^{1}n^{(k-1)/2} \right) \\
&= \dfrac{1}{2k} \left( \sum_{d|k} \varphi(k/d) n^d + kn^{(k+1)/2} \right)
\end{align}
$$

## Generadores de un grupo
Decimos que un conjunto $S=\{a,b,\ldots\}$ **genera** a un grupo $G$ si cada elemento $g$ de $G$ puede ser escrito como la composición finita de elementos de $S$ y $S$ tiene el tamaño mínimo.

Ejemplo: tomemos el grupo cíclico $C_k$. Si tomamos la permutación $f_1$, entonces $S=\{f_1\}$, pues $f_r=f_1^r$ para $0 \leq r \leq k-1$. Notemos que la elección del generador no es única, ya que también podemos escoger a $S=\{f_i\}$, donde $\gcd(i, k) = 1$.

En el caso de grupos que son generador por conjuntos de un solo elemento, describir sus elementos es fácil, pues si $S=\{g\}$ y el tamaño del grupo es $k$, entonces $G=\{g^0, g^1, \ldots, g^{k-1}\}$.

Pero esto se complica cuando $S$ tiene más de un elemento, pues combinarlos ya no es tan trivial. Por ejemplo, si $S=\{a,b\}$, entonces algunos posibles elementos de $G$ son $a, b, ab, ba, a^2b, aba, ab^2, ba^2, bab, b^2a, \ldots$.

## Problema del cubo de Rubik
Tenemos un cubo de Rubik de $2 \times 2 \times 2$ y queremos colorear cada uno de sus $24$ cuadraditos con $n$ colores. Hallar el número de formas de hacerlo, suponiendo que cada movimiento mecánicamente posible del cubo lo deja equivalente.

Primero hay que identificar los movimientos básicos:
- $F$: rotar la cara frontal del cubo $90^\circ$ a la derecha.
- $B$: rotar la cara trasera del cubo $90^\circ$ a la derecha.
- $L$: rotar la cara izquierda del cubo $90^\circ$ a la derecha.
- $R$: rotar la cara derecha del cubo $90^\circ$ a la derecha.
- $D$: rotar la cara de abajo del cubo $90^\circ$ a la derecha.
- $U$: rotar la cara de arriba del cubo $90^\circ$ a la derecha.

Sea $G$ el grupo generado por dichos movimientos básicos, es decir, el conjunto $\{F,B,L,R,D,U\}$ va a generar a $G$, pues de forma más intuitiva, cualquier secuencia de movimientos pertenece a $G$, y las podemos ver como strings compuestas solo por estas seis letras.

Pero como $G$ es finito, ya que es un subgrupo de $S_{24}$, ¿cómo sabemos cuántos y a cuáles elementos tiene?

Podemos realizar una BFS: comenzamos con la permutación identidad $I$, vamos guardando en un conjunto $G$ todos los elementos que vayamos encontrando y también llevaremos una cola $Q$. Al principio metemos a $I$ en $G$ y en $Q$. Después, mientras la cola no esté vacía:
- Sacar un elemento de la cola, digamos que es $g$.
- Por cada elemento de $S$, combinar $g$ con dicho elemento y meterlo a la cola solo si no está presente en $G$.

Después, por cada permutación $f$ en $G$, simplemente aplicar Burnside's Lemma. Si el problema tuviera varios casos de prueba, donde nos dan distintos valores de $n$, podemos preprocesar el conjunto $G$ antes, y como solo nos interesa el número de ciclos por cada permutación, también los podemos precalcular en un arreglo y usarlo para responder todos los casos.