Lema de Burnside / teorema de enumeración de Pólya

Lema de Burnside

El lema de Burnside (Burnside’s lemma) fue formulado y demostrado por Burnside en 1897, pero históricamente ya lo había descubierto Frobenius en 1887, e incluso antes, en 1845, Cauchy. Por eso a veces también se lo llama lema de Cauchy-Frobenius.

El lema de Burnside permite contar el número de clases de equivalencia en conjuntos, basándose en la simetría interna.

Objetos y representaciones

Hay que distinguir claramente entre el número de objetos y el número de representaciones.

Distintas representaciones pueden corresponder a los mismos objetos, pero por supuesto cualquier representación corresponde a exactamente un objeto. En consecuencia, el conjunto de todas las representaciones se divide en clases de equivalencia. Nuestra tarea es calcular el número de objetos o, de forma equivalente, el número de clases de equivalencia. El siguiente ejemplo hará más clara la diferencia entre objeto y representación.

Ejemplo: coloreo de árboles binarios

Supongamos que tenemos el siguiente problema. Hay que contar el número de formas de colorear un árbol binario enraizado con $n$ vértices con dos colores, donde en cada vértice no distinguimos entre el hijo izquierdo y el derecho.

Aquí el conjunto de objetos es el conjunto de distintos coloreos del árbol.

Definimos ahora el conjunto de representaciones. Una representación de un coloreo es una función $f(v)$ , que asigna a cada vértice un color (aquí usamos los colores $0$ y $1$ ). El conjunto de representaciones es el conjunto que contiene todas las funciones posibles de este tipo, y su tamaño es obviamente igual a $2^n$ .

Al mismo tiempo introducimos una partición de este conjunto en clases de equivalencia.

Por ejemplo, supongamos $n = 3$ , y el árbol consiste en la raíz $1$ y sus dos hijos $2$ y $3$ . Entonces las siguientes funciones $f_1$ y $f_2$ se consideran equivalentes.

$\begin{array}{ll} f_{1} (1) = 0 & f_{2} (1) = 0 \\ f_{1} (2) = 1 & f_{2} (2) = 0 \\ f_{1} (3) = 0 & f_{2} (3) = 1 \end{array}$

Permutaciones invariantes

¿Por qué estas dos funciones $f_1$ y $f_2$ pertenecen a la misma clase de equivalencia? Intuitivamente es comprensible: podemos reordenar los hijos del vértice $1$ , los vértices $2$ y $3$ , y después de tal transformación de la función $f_1$ coincidirá con $f_2$ .

Pero formalmente esto significa que existe una permutación invariante $\pi$ (es decir, una permutación que no cambia el objeto en sí, sino solo su representación), tal que:

$f_2 \pi \equiv f_1$

Así, partiendo de la definición de los objetos, podemos hallar todas las permutaciones invariantes, es decir, todas las permutaciones que no cambian el objeto al aplicarlas a la representación. Luego podemos comprobar si dos funciones $f_1$ y $f_2$ son equivalentes (es decir, si corresponden al mismo objeto) verificando la condición $f_2 \pi \equiv f_1$ para cada permutación invariante (o equivalentemente $f_1 \pi \equiv f_2$ ). Si se encuentra al menos una permutación para la que se cumple la condición, entonces $f_1$ y $f_2$ son equivalentes; en caso contrario no lo son.

Hallar todas esas permutaciones invariantes respecto de la definición del objeto es un paso clave para la aplicación tanto del lema de Burnside como del teorema de enumeración de Pólya. Está claro que estas permutaciones invariantes dependen del problema concreto, y hallarlas es un proceso puramente heurístico basado en consideraciones intuitivas. Sin embargo, en la mayoría de los casos basta hallar a mano varias permutaciones “básicas”, con las que se pueden generar todas las demás (y esta parte del trabajo se puede delegar a una computadora).

No es difícil entender que las permutaciones invariantes forman un grupo, porque el producto (composición) de permutaciones invariantes es de nuevo una permutación invariante. Denotamos el grupo de permutaciones invariantes por $G$ .

El enunciado del lema

Para la formulación del lema necesitamos una definición más del álgebra. Un punto fijo $f$ de una permutación $\pi$ es un elemento que es invariante bajo esta permutación: $f \equiv f \pi$ . Por ejemplo, en nuestro ejemplo los puntos fijos son aquellas funciones $f$ que corresponden a coloreos que no cambian cuando se les aplica la permutación $\pi$ (es decir, no cambian en el sentido formal de igualdad de funciones). Denotamos por $I(\pi)$ el número de puntos fijos de la permutación $\pi$ .

Entonces el lema de Burnside dice lo siguiente: el número de clases de equivalencia es igual a la suma de los números de puntos fijos respecto de todas las permutaciones del grupo $G$ , dividida por el tamaño de este grupo:

$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$

Aunque el lema de Burnside en sí no es tan conveniente de usar en la práctica (no está claro cómo buscar rápidamente el valor $I(\pi)$ ), es el que revela con más claridad la esencia matemática sobre la que se basa la idea de calcular clases de equivalencia.

Demostración del lema de Burnside

La demostración del lema de Burnside descrita aquí no es importante para las aplicaciones prácticas, así que se puede saltar en una primera lectura.

La demostración que presentamos es la más simple conocida, y no usa teoría de grupos. La publicó Kenneth P. Bogart en 1991.

Hay que demostrar el siguiente enunciado:

$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$

El valor del lado derecho no es otra cosa que el número de “pares invariantes” $(f, \pi)$ , es decir, pares tales que $f \pi \equiv f$ . Es obvio que podemos cambiar el orden de la sumatoria. Dejamos que la suma itere sobre todos los elementos $f$ y sumamos los valores $J(f)$ : el número de permutaciones para las que $f$ es un punto fijo.

$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$

Para demostrar esta fórmula construiremos una tabla con las columnas etiquetadas con todas las funciones $f_i$ y las filas etiquetadas con todas las permutaciones $\pi_j$ . Y llenamos las celdas con $f_i \pi_j$ . Si miramos las columnas de esta tabla como conjuntos, algunas coincidirán, y esto significa que las funciones $f$ correspondientes a esas columnas también son equivalentes. Así, el número de columnas distintas (como conjuntos) es igual al número de clases. De paso, desde el punto de vista de la teoría de grupos, la columna etiquetada con $f_i$ es la órbita de este elemento. Para elementos equivalentes las órbitas coinciden, y el número de órbitas da exactamente el número de clases.

Así, las columnas de la tabla se descomponen en clases de equivalencia. Fijemos una clase y miremos las columnas que hay en ella. Primero, nótese que estas columnas solo pueden contener elementos $f_i$ de la clase de equivalencia (en caso contrario alguna permutación $\pi_j$ habría llevado una de las funciones a una clase de equivalencia distinta, lo cual es imposible porque solo consideramos permutaciones invariantes). Segundo, cada elemento $f_i$ ocurrirá el mismo número de veces en cada columna (esto también se sigue del hecho de que las columnas corresponden a elementos equivalentes). De esto podemos concluir que todas las columnas dentro de la misma clase de equivalencia coinciden entre sí como multiconjuntos.

Ahora fijemos un elemento arbitrario $f$ . Por un lado, ocurre en su columna exactamente $J(f)$ veces (por definición). Por otro lado, todas las columnas dentro de la misma clase de equivalencia son iguales como multiconjuntos. Por lo tanto, dentro de cada columna de una clase de equivalencia dada cualquier elemento $g$ ocurre exactamente $J(g)$ veces.

Así, si tomamos arbitrariamente una columna de cada clase de equivalencia y sumamos el número de elementos en ellas, obtenemos por un lado $|\text{Classes}| \cdot |G|$ (simplemente multiplicando el número de columnas por el número de filas), y por otro lado la suma de las cantidades $J(f)$ para todo $f$ (esto se sigue de todos los argumentos anteriores):

$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$

Teorema de enumeración de Pólya

El teorema de enumeración de Pólya (Pólya enumeration theorem) es una generalización del lema de Burnside, y además proporciona una herramienta más conveniente para hallar el número de clases de equivalencia. Cabe señalar que este teorema ya lo había descubierto Redfield antes que Pólya, en 1927, pero su publicación pasó inadvertida para los matemáticos. Pólya llegó independientemente a los mismos resultados en 1937, y su publicación tuvo más éxito.

Aquí discutimos solo un caso especial del teorema de enumeración de Pólya, que resultará muy útil en la práctica. No se discutirá la fórmula general del teorema.

Denotamos por $C(\pi)$ el número de ciclos en la permutación $\pi$ . Entonces vale la siguiente fórmula (un caso especial del teorema de enumeración de Pólya):

$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$

$k$ es el número de valores que puede tomar cada elemento de la representación; en el caso del coloreo de un árbol binario sería $k = 2$ .

Demostración

Esta fórmula es una consecuencia directa del lema de Burnside. Para obtenerla, solo necesitamos hallar una expresión explícita para $I(\pi)$ , que aparece en el lema. Recordemos que $I(\pi)$ es el número de puntos fijos de la permutación $\pi$ .

Así, consideramos una permutación $\pi$ y algún elemento $f$ . Durante la aplicación de $\pi$ , los elementos de $f$ se mueven a través de los ciclos de la permutación. Como el resultado debe satisfacer $f \equiv f \pi$ , los elementos tocados por un mismo ciclo deben ser todos iguales. Al mismo tiempo, ciclos distintos son independientes. Así, para cada ciclo de la permutación $\pi$ podemos elegir un valor (entre $k$ posibles) y de este modo obtenemos el número de puntos fijos:

$I(\pi) = k^{C(\pi)}$

Aplicación: colorear collares

El problema “Necklace” es uno de los problemas combinatorios clásicos. La tarea es contar el número de collares distintos de $n$ cuentas, cada una de las cuales se puede pintar de uno de $k$ colores. Al comparar dos collares, se pueden rotar, pero no invertir (es decir, se permite un desplazamiento cíclico).

En este problema podemos hallar de inmediato el grupo de permutaciones invariantes:

$\begin{aligned} π_{0} & = 123 \dots n \\ π_{1} & = 23 \dots n 1 \\ π_{2} & = 3 \dots n 12 \\ \dots \\ π_{n - 1} & = n 123 \dots \end{aligned}$

Hallemos una fórmula explícita para calcular $C(\pi_i)$ . Primero notamos que la permutación $\pi_i$ tiene en la $j$ -ésima posición el valor $i + j$ (tomado módulo $n$ ). Si comprobamos la estructura de ciclos de $\pi_i$ . Vemos que $1$ va a $1 + i$ , $1 + i$ va a $1 + 2i$ , que va a $1 + 3i$ , etc., hasta llegar a un número de la forma $1 + k n$ . Se pueden hacer afirmaciones similares para los restantes elementos. De ahí vemos que todos los ciclos tienen la misma longitud, a saber $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$ . Así, el número de ciclos en $\pi_i$ será igual a $\gcd(i, n)$ .

Sustituyendo estos valores en el teorema de enumeración de Pólya, obtenemos la solución:

$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$

Se puede dejar esta fórmula en esta forma, o se puede simplificar aún más. Trasladamos la suma para que itere sobre todos los divisores de $n$ . En la suma original habrá muchos términos equivalentes: si $i$ no es un divisor de $n$ , entonces tal divisor se puede hallar después de calcular $\gcd(i, n)$ . Por lo tanto, para cada divisor $d | n$ su término $k^{\gcd(d, n)} = k^d$ aparecerá en la suma varias veces, es decir, la respuesta al problema se puede reescribir como

$\frac{1}{n} \sum_{d | n} C_d k^d,$

donde $C_d$ es el número de tales números $i$ con $\gcd(i, n) = d$ . Podemos hallar una expresión explícita para este valor. Cualquier tal número $i$ tiene la forma $i = d j$ con $\gcd(j, n / d) = 1$ (en caso contrario $\gcd(i, n) > d$ ). Así que podemos contar el número de $j$ con este comportamiento. La función φ de Euler nos da el resultado $C_d = \phi(n / d)$ , y por lo tanto obtenemos la respuesta:

$\frac{1}{n} \sum_{d | n} \phi\left(\frac{n}{d}\right) k^d$

Aplicación: colorear un toro

Con bastante frecuencia no podemos obtener una fórmula explícita para el número de clases de equivalencia. En muchos problemas el número de permutaciones de un grupo puede ser demasiado grande para cálculos manuales y no es posible calcular analíticamente el número de ciclos en ellas.

En ese caso debemos hallar a mano varias permutaciones “básicas”, de modo que puedan generar todo el grupo $G$ . Luego podemos escribir un programa que genere todas las permutaciones del grupo $G$ , cuente el número de ciclos en ellas y calcule la respuesta con la fórmula.

Consideremos el ejemplo del problema de colorear un toro. Hay una hoja de papel cuadriculada $n \times m$ ( $n < m$ ), algunas de las celdas son negras. Luego se obtiene un cilindro de esta hoja pegando los dos lados de longitudes $m$ . Luego se obtiene un toro del cilindro pegando los dos círculos (superior e inferior) sin torcer. La tarea es calcular el número de toros coloreados distintos, suponiendo que no podemos ver las líneas pegadas, y que el toro se puede girar y dar vueltas.

De nuevo partimos de un trozo de papel $n \times m$ . Es fácil ver que los siguientes tipos de transformaciones preservan la clase de equivalencia: un desplazamiento cíclico de las filas, un desplazamiento cíclico de las columnas, y una rotación de la hoja de 180 grados. También es fácil ver que estas transformaciones pueden generar todo el grupo de transformaciones invariantes. Si numeramos de alguna manera las celdas del papel, entonces podemos escribir tres permutaciones $p_1$ , $p_2$ , $p_3$ correspondientes a estos tipos de transformación.

Luego solo resta generar todas las permutaciones obtenidas como producto. Es obvio que todas esas permutaciones tienen la forma $p_1^{i_1} p_2^{i_2} p_3^{i_3}$ donde $i_1 = 0 \dots m-1$ , $i_2 = 0 \dots n-1$ , $i_3 = 0 \dots 1$ .

Así podemos escribir las implementaciones de este problema.


using Permutation = vector<int>;

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation p(n*m), p1(n*m), p2(n*m), p3(n*m);
    for (int i = 0; i < n*m; i++) {
        p[i] = i;
        p1[i] = (i % n + 1) % n + i / n * n;
        p2[i] = (i / n + 1) % m * n + i % n;
        p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}