---
tags: combinatorics, polya-enumeration-theorem, burnside-lemma, group-theory, cycle-index, permutations
---

# Pólya enumeration theorem
Es una generalización de Burnside's lemma que nos permite tener mayor "control" sobre lo que estamos contando. De esa forma podemos agregar más restricciones a los objetos de interés.

## Cycle index notation
Sea $\sigma$ una permutación de $k$ elementos. Sea $c_i(\sigma)$ el número de ciclos de tamaño $i$ que contiene $\sigma$ (de aquí en adelante los llamaremos $i$-ciclos). Definimos el **cycle index monomial** de $\sigma$ como $\displaystyle \prod_{i=1}^{k} {z_i}^{c_i(\sigma)}$, es decir, es un monomio en $k$ variables, donde $z_i$ es la variable asociada a los ciclos de tamaño $i$.

De forma similar, definimos al **cycle index** de un grupo $G$ de permutaciones de $k$ elementos como:
$$
Z_G(z_1, \ldots, z_k) = \displaystyle \dfrac{1}{|G|} \sum_{\sigma \in G} \prod_{i=1}^{k} {z_i}^{c_i(\sigma)}
$$

Esta definición es muy útil, ya que nos permite capturar la esencia de las permutaciones de cualquier grupo.

**Ejemplo:** Si $\sigma = (1 \quad 2)(3 \quad 4)(5)(6 \quad 7 \quad 8 \quad 9)(10 \quad 11 \quad 12 \quad 13)(14)(15)$, entonces el cycle index monomial de $\sigma$ es ${z_1}^3 {z_2}^2 {z_4}^2$. Notemos que si un ciclo de cierta longitud no aparece, podemos omitir esa variable, ya que ${z_i}^0 = 1$.

### Representación en código
Una forma de representar un polinomio de cycle index de un grupo $G$ es usando un $\texttt{map<vector<int>, int>}$. Es decir, es un diccionario en donde las llaves son los vectores de frecuencias de longitudes de los ciclos, o sea, el monomio $[c_1, c_2, \ldots, c_n]$; y los valores son los coeficientes de dichos monomios.

### Cycle index del grupo cíclico
**Ejemplo:** Si $G=C_k$, sabemos que para cada divisor $d$ de $k$, existen $\varphi(k/d)$ permutaciones con $d$ $k/d$-ciclos. Entonces:
$$
\begin{align}
Z_{C_k}(z_1, \ldots, z_k) &= \dfrac{1}{k} \sum_{d | k} \varphi(k/d) {z_{k/d}}^d \\
&= \dfrac{1}{k} \sum_{d | k} \varphi(d) {z_{d}}^{k/d}
\end{align}
$$

### Cycle index del grupo diedral
**Ejemplo:** Si $G=D_k$, ya sabemos la estructura de las rotaciones, y habíamos visto que para las reflexiones hay dos casos:
- Cuando $k$ es par:
- $k/2$ reflexiones tienen $2$ 1-ciclo y $k/2-1$ 2-ciclos.
- $k/2$ reflexiones tienen $k/2$ 2-ciclos.
Por lo tanto:
$$
Z_{D_k}(z_1, \ldots, z_k) = \dfrac{1}{2k} \left( \sum_{d | k} \varphi(d) {z_{d}}^{k/d} + \dfrac{k}{2} \left( {z_1}^2 {z_2}^{k/2-1} + {z_2}^{k/2} \right) \right)
$$
- Cuando $k$ es impar, kay $k$ reflexiones con $1$ 1-ciclo y $(k-1)/2$ 2-ciclos. Por lo tanto:
$$
Z_{D_k}(z_1, \ldots, z_k) = \dfrac{1}{2k} \left( \sum_{d | k} \varphi(d) {z_{d}}^{k/d} + k {z_1} {z_2}^{(k-1)/2} \right)
$$

### Cycle index del grupo simétrico
**Ejemplo:** Si $G=S_k$, ahora tenemos todas las $k!$ permutaciones. Sabemos que para cualquier permutación $\sigma \in S_k$ se cumple que $\displaystyle \sum_{i=1}^{k} i \cdot c_i(\sigma) = k$. Supongamos que las variables $c_1(\sigma), \ldots, c_k(\sigma)$ son las incógnitas de la ecuación anterior, y queremos ver cuántas permutaciones $\sigma \in S_k$ la satisfacen para una solución fija, es decir, cuántas permutaciones contienen $c_i(\sigma)$ $i$-ciclos para toda $1 \leq i \leq k$. Sabemos que hay $k!$ maneras de escribir una lista de $k$ números en $\{1, \ldots, k \}$ donde cada uno aparece exactamente una vez, tomemos una y agrupémosla de la siguiente manera para encontrar la permutación $\sigma$:
- Los primeros $c_1$ elementos que sean puntos fijos.
- Los siguientes $2c_2$ elementos que sean ciclos de tamaño $2$ en pares adyacentes.
- Los siguientes $3c_3$ elementos que sean ciclos de tamaño $3$ en ternas adyacentes.
- y así sucesivamente...

Por ejemplo, si $k=8$, $c_1=1$, $c_2=2$, $c_3=1$, $c_4=\cdots=c_8=0$ y escribimos los números de esta forma: $4,7,1,8,6,3,5,2$, entonces $\sigma=(4)(7 \quad 1)(8 \quad 6)(3 \quad 5 \quad 2)$. Sin embargo, vemos que podemos reordenar los ciclos y también rotar cíclicamente los elementos dentro de cada ciclo, por lo que estamos contando cada $\sigma$ muchas veces.

Para considerar solo las permutaciones donde no importa el orden en el que coloquemos los ciclos, vemos que cada uno de los $c_i$ $i$-ciclos los podemos acomodar de $c_i!$ maneras distintas y todas reprsentan a la misma permutación, por lo tanto hay que dividir entre $c_i!$, es decir, al final dividimos entre $\displaystyle \prod_{i=1}^{k} c_i!$.

Para solo quedarnos con un representativo de cada ciclo en donde todas sus rotaciones son la misma, vemos que en un $i$-ciclo tenemos $i$ rotaciones, y como hay $c_i$ de ellos, hay que dividir entre $i^{c_i}$, es decir, al final dividimos entre $\displaystyle \prod_{i=1}^{k} i^{c_i}$.

Por lo tanto, el número de permutaciones para esa solución fija es $\displaystyle \dfrac{k!}{\prod_{i=1}^{k} c_i! \cdot i^{c_i}}$, y el cycle index de $S_k$ se halla iterando por todas las posibles soluciones de la ecuación:
$$
Z_{S_k}(z_1, \ldots, z_n) = \dfrac{1}{k!} \sum_{c_1 + 2c_2 + \ldots + kc_k = k} \dfrac{k!}{\prod_{i=1}^{k} c_i! \cdot i^{c_i}} \prod_{i=1}^{k} {z_i}^{c_i}
$$
donde la suma itera por todas las soluciones de la ecuación $c_1 + 2c_2 + \ldots + kc_k = k$, o equivalentemente, por todas las *particiones* de $k$, donde las $c_1, \ldots, c_k$ son las frecuencias de $1, \ldots, k$.

Ejemplo: $Z_{S_4} = \dfrac{1}{24}({z_1}^4 + 6{z_1}^2{z_2} + 8{z_1}{z_3} + 3{z_2}^2 + 6{z_4
})$

#### Código auxiliar para generar particiones
El siguiente método enlista todas las particiones de un entero $n$ de forma eficiente, recibe como argumentos el número $\texttt{n}$ y una función $\texttt{f}$ que se llamará con cada partición resultante representada con un arreglo:

void gen_partitions(int n, function<void(const vector<int>&)> f){
	vector<int> a(n);
	int k = 1, y = n-1;
	while(k != 0){
		int x = a[k-1] + 1;
		k--;
		while(2*x <= y){
			a[k] = x;
			y -= x;
			k++;
		}
		int l = k+1;
		while(x <= y){
			a[k] = x;
			a[l] = y;
			f(vector<int>(a.begin(), a.begin() + k+2));
			x++;
			y--;
		}
		a[k] = x+y;
		y = x+y-1;
		f(vector<int>(a.begin(), a.begin() + k+1));
	}
}

**Nota:** las particiones generadas con este código representan a los sumandos que dan como resultado $n$ y no las frecuencias de cada uno. Por ejemplo, si $n=10$, una posible partición es $[1, 1, 2, 6]$. Si las queremos usar para el ejemplo anterior, simplemente hay que calcular la frecuencia de cada sumando y así hallamos el arreglo $c[]$. Ejemplo de uso para hallar $Z_{S_n}$:

int n = 4;
map<vector<int>, int> Z_Sn;
gen_partitions(n, [&](const vector<int> & part){
	vector<int> c(n+1);
	for(int p : part){
		c[p]++;
	}
	lli den = 1;
	for(int i = 1; i <= n; ++i){
		den = den * power(i, c[i]) % mod * fact[c[i]] % mod;
	}
	Z_Sn[c] = power(den, mod-2) % mod;
});

## Coloraciones
Sean $X$ y $Y$ dos conjuntos finitos. Llamaremos a $X$ al conjunto de "lugares vacíos" o de "slots", y a $Y$ como el conjunto de "colores". Sea $f : X \to Y$ una función que va de $X$ a $Y$, cuya interpretación podría ser una forma de asignarle un color de $Y$ a cada lugar vacío de $X$, es decir, $f$ es una *coloración*.

**Ejemplo:** sea $X=\{1, \ldots, 6\}$ el conjunto de los seis vértices de un hexágono y sea $Y=\{\color{blue}{\text{0}}, \color{red}{\text{1}}\}$ (el $\color{blue}{\text{0}}$ será el color $\color{blue}{\text{azul}}$ y el $\color{red}{\text{1}}$ será el $\color{red}{\text{rojo}}$). Sea $f$ la siguiente función:
$$
\begin{align}
f(1) &= \color{blue}{\text{0}} & f(4) &= \color{red}{\text{1}} \\
f(2) &= \color{red}{\text{1}} & f(5) &= \color{blue}{\text{0}} \\
f(3) &= \color{blue}{\text{0}} & f(6) &= \color{red}{\text{1}}
\end{align}
$$
Entonces $f$ nos indica una forma de asignarle colores a cada uno de los seis vértices del hexágono.

Sea $Y^X = \{f : X \to Y\}$ el conjunto de todas las posibles funciones. Vemos que $| Y^X | = |Y|^{|X|}$, pues por cada elemento de $X$ tenemos $|Y|$ opciones para asignarle un color.

## Acciones de un grupo
Sea $G$ un grupo de permutaciones tales que $\sigma : X \to X$ para $\sigma \in G$, es decir, estas permutaciones van a reacomodar todos los elementos de $X$.

Sea $\phi(\sigma, f)$ una acción del grupo $G$ sobre el conjunto $Y^X$ definida como $\phi(\sigma, f) = f \circ \sigma$, y escribimos $\sigma \times f = f \circ \sigma$. En otras palabras, $\phi$ representa a una acción que recibe una coloración $f$ y una permutación $\sigma$, y devuelve la composición de $f$ con $\sigma$, es decir, dada una $x \in X$, tenemos que $(\sigma \times f)(x) = f(\sigma(x))$.

La identidad de esta acción es justamente la permutación identidad $id$ y es fácil ver que se cumple la segunda propiedad $(\sigma_1 \circ \sigma_2) \times f = \sigma_2 \times (\sigma_1 \times f)$ (realmente esta propiedad está modificada en el orden pero para lo que haremos no importa), pues:
- $(\sigma_1 \circ \sigma_2) \times f = f \circ \sigma_1 \circ \sigma_2$
- $\sigma_2 \times (\sigma_1 \times f) = \sigma_2 \times (f \circ \sigma_1) = f \circ \sigma_1 \circ \sigma_2$

**Ejemplo:** sea $G=C_6$ y $X$, $Y$ y $f$ como en el ejemplo anterior del hexágono. Sea $\sigma=(1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6)$, entonces $g=\sigma \times f$ viene dada por:
$$
\begin{align}
g(1) &= f(\sigma(1)) = f(2) = \color{red}{\text{1}} & g(4) &= f(\sigma(4)) = f(5) = \color{blue}{\text{0}} \\
g(2) &= f(\sigma(2)) = f(3) = \color{blue}{\text{0}} & g(5) &= f(\sigma(5)) = f(6) = \color{red}{\text{1}} \\
g(3) &= f(\sigma(3)) = f(4) = \color{red}{\text{1}} & g(6) &= f(\sigma(6)) = f(1) = \color{blue}{\text{0}}
\end{align}
$$

## Puntos fijos y órbitas
Usaremos los mismos conceptos de puntos fijos y órbitas vistos anteriormente, adaptados a nuestra notación actual:
- Para una permutación $\sigma \in G$, decimos que una función $f \in Y^X$ es una función fija de $\sigma$ si $\sigma \times f = f$. Es decir, ambas coloraciones son la misma y el efecto de $\sigma$ fue nulo.
Denotamos como $F^\sigma = \{f \in Y^X \mid \sigma \times f = f\}$ como el conjunto de todas las funciones que son invariantes bajo la permutación $\sigma$.
- Dada una función $f \in Y^X$, definimos a su órbita como $G \times f = \{\sigma \times f \mid \sigma \in G\}$, es decir, el conjunto de todas las posibles coloraciones obtenidas al componer $f$ con todas las permutaciones de $G$. Decimos que dos funciones $f$ y $g$ son *equivalentes* si $f$ y $g$ tienen la misma órbita y escribimos $f \sim g$, además definimos $Y^X / G = \{G \times f \mid f \in Y^X\}$ como el conjunto de *configuraciones*.

**Ejemplo:** sean $G$, $X$, $Y$ y $f$ como en el anterior. Sea $\sigma=(1 \quad 3 \quad 5)(2 \quad 4 \quad 6)$, entonces $f$ es una función fija de $\sigma$ pues $f = \sigma \times f$.

## Burnside's Lemma
Aplicando Burnside's Lemma, podemos contar el número de clases de equivalencia o configuraciones $|Y^X/G|$ como:
$$
|Y^X/G| = \dfrac{1}{|G|} \sum_{\sigma \in G} |F^g|
$$

## Función peso
Sea $R$ un anillo conmutativo y sea $w : Y \to R$ una función que le asigna a cada color un determinado *peso*. Es decir, si $w(y)=r$, entonces $r$ es el peso del color $y$.

Definimos al **peso** de la función $f :X \to Y$ como el siguiente producto: $\displaystyle W(f) = \prod_{x \in X} w(f(x))$.

**Ejemplo:** sean $G$, $X$, $Y$ y $f$ como en el anterior. Sea $R=\{r, b\}$ y sea $w : Y \to R$ dada por $w(\color{blue}{\text{0}})=b$ y $w(\color{red}{\text{1}})=r$. Entonces:
$$
\begin{align}
W(f) &= w(f(1))w(f(2))w(f(3))w(f(4))w(f(5))w(f(6))\\
&= w(\color{blue}{\text{0}})w(\color{red}{\text{1}})w(\color{blue}{\text{0}})w(\color{red}{\text{1}})w(\color{blue}{\text{0}})w(\color{red}{\text{1}}) \\
&= brbrbr \\
&= b^3 r^3
\end{align}
$$

Un resultado impotante es que si $f \sim g$, entonces $W(f) = W(g)$. Se puede demostrar así: como $f \sim g$, entonces existe $\sigma \in G$ tal que $g = f \circ \sigma$, y luego:
$$
\begin{align}
W(g) &= \prod_{x \in X} w(g(x)) &\mbox{por definición de $W(g)$} \\
&= \prod_{x \in X} w(f(\sigma(x))) &\mbox{$g = f \circ \sigma$} \\
&= \prod_{x \in X} w(f(x)) &\mbox{como $\sigma$ es una permutación, este es el mismo producto pero en otro orden} \\
&= W(f) &\mbox{por definición de $W(f)$}
\end{align}
$$

Por lo tanto, podemos definir de manera única a $W(G \times f)$ como $W(f')$ para cualquier $f' \in G \times f$, pues todas las $f'$ tienen el mismo valor.

## Función generadora de pesos
Ahora definimos a la **función generadora** de **pesos** o **configuraciones** como:
$$
F_G = \sum_{f \in Y^X/G} W(f)
$$
**Ejemplo:** sean $G$, $X$, $Y$, $R$ y $w$ como en el anterior. Aplicando Burnside's Lemma, el número de configuraciones es $\displaystyle \frac{1}{6}\sum_{d | 6} \varphi(6/d) 2^d = \frac{1}{6}(\varphi(6)2^1 + \varphi(3)2^2 + \varphi(2)2^3 + \varphi(1)2^6) = \dfrac{1}{6}(2 \cdot 2 + 2 \cdot 4 + 1 \cdot 8 + 1 \cdot 64) = 14$, cuyos representantes de cada clase de equivalencia y sus pesos son:
1. $f_{1} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}), \quad w(f_{1}) = b^6$
2. $f_{2} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}), \quad w(f_{2}) = b^5r$
3. $f_{3} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{3}) = b^4r^2$
4. $f_{4} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}), \quad w(f_{4}) = b^4r^2$
5. $f_{5} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{5}) = b^3r^3$
6. $f_{6} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}), \quad w(f_{6}) = b^4r^2$
7. $f_{7} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{7}) = b^3r^3$
8. $f_{8} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}), \quad w(f_{8}) = b^3r^3$
9. $f_{9} : (123456) \mapsto (\color{blue}{\text{0}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{9}) = b^2r^4$
10. $f_{10} : (123456) \mapsto (\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}), \quad w(f_{10}) = b^3r^3$
11. $f_{11} : (123456) \mapsto (\color{blue}{\text{0}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{11}) = b^2r^4$
12. $f_{12} : (123456) \mapsto (\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{12}) = b^2r^4$
13. $f_{13} : (123456) \mapsto (\color{blue}{\text{0}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{13}) = br^5$
14. $f_{14} : (123456) \mapsto (\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}\color{red}{\text{1}}), \quad w(f_{14}) = r^6$

Por lo tanto: $F_G = b^6 + b^5r + 3b^4r^2 + 4b^3r^3 + 3b^2r^4 + br^5 + r^6$.

Esto nos da información adicional, por ejemplo, nos dice que hay $3$ coloraciones de los vértices de un hexágono equivalentes bajo rotaciones con dos colores, donde el color $\color{blue}{\text{0}}$ se usa 4 veces y el color $\color{red}{\text{1}}$ se usa 2 veces, pues solo tuvimos que fijarnos en el coeficiente de $b^4r^2$.

Y si hacemos que $r=b=1$, entonces $F_G=1+1+3+4+3+1+1=14$, lo que nos dice lo mismo que Burnside's Lemma.

## Pólya's enumeration theorem
Sea $\displaystyle z_p = \sum_{y \in Y} [w(y)]^p$ el resultado de elevar todos pesos de $Y$ a la $p$-ésima potencia, y sea $|X|=k$. Entonces, el teorema de enumeracion de Pólya nos dice que $F_G = Z_G(z_1, z_2, \ldots, z_k)$.

**Ejemplo:** sean $G$, $X$, $Y$, $R$ y $w$ como en el anterior. Apliquemos el teorema de enumeración de Pólya y veamos que obtenemos el mismo resultado de $F_G$:
$$
\begin{align}
z_p &= [w(\color{blue}{\text{0}})]^p + [w(\color{red}{\text{1}})]^p \\
&= b^p + r^p \\
F_G &= Z_{C_6}(z_1, z_2, z_3, z_4, z_5, z_6) \\
&= \dfrac{1}{6} \sum_{d | 6} \varphi(d) {z_d}^{6/d} \\
&= \dfrac{1}{6} ({z_1}^6 + {z_2}^3 + 2{z_3}^2 + 2{z_6}^1) \\
&= \dfrac{1}{6} [(b+r)^6 + (b^2+r^2)^3 + 2(b^3+r^3)^2 + 2(b^6+r^6)] \\
&= \dfrac{1}{6} [(b^6+6b^5r+15b^4r^2+20b^3r^3+15b^2r^4+6br^5+r^6) + (b^6+3b^4r^2+3b^2r^4+r^6) + 2(b^6+2b^3r^3+r^6)+2(b^6+r^6)] \\
&= \dfrac{1}{6} [6b^6+6b^5r+18b^4r^2+24b^3r^3+18b^2r^4+6br^5+6r^6] \\
&=b^6+b^5r+3b^4r^2+4b^3r^3+3b^2r^4+br^5+r^6
\end{align}
$$

**Observación:** Vemos que si asignamos todos los pesos $w(y)=1$ para toda $y \in Y$, entonces $\displaystyle z_p = \sum_{y \in Y} 1^p = \sum_{y \in Y} 1 = |Y|$, y sustituyendo:
$$
\begin{align}
F_G &= Z_G(|Y|, |Y|, \ldots, |Y|) \\
&= \dfrac{1}{|G|} \sum_{\sigma \in G} \prod_{i=1}^{k} |Y|^{c_i(\sigma)} \\
&= \dfrac{1}{|G|} \sum_{\sigma \in G} |Y|^{\sum_{i=1}^{k} c_i(\sigma)} \\
&= \dfrac{1}{|G|} \sum_{\sigma \in G} |Y|^{c(\sigma)}
\end{align}
$$
Obtuvimos de nuevo la fórmula de Burnside's Lemma, por lo que es un caso particular del teorema de enumeración de Pólya al asignar todos los pesos igual a $1$.

## Problema: pizzas
Tenemos $m$ ingredientes disponibles para armar una pizza circular, y queremos que cada uno de ellos aparezca exactamente $n$ veces, es decir, el tamaño de la pizza en rebanadas será de $mn$. Hallar el número de pizzas distintas que podemos armar, suponiendo que son equivalentes bajo rotaciones.

**Solución:** vemos que el tamaño de todas las pizzas es $mn$, por lo tanto, el grupo que estará actuando es $C_{mn}$. Sea $X=\{1, 2, \ldots, mn\}$ el conjunto de las $mn$ rebanadas en la pizza sin asignar y sea $Y=\{1, 2, \ldots m\}$ el conjunto de ingredientes.

Sea $w(y)=t_y$ para cada $1 \leq y \leq m$. Entonces $W(f)$ nos va a decir cuánto usé de cada ingrediente. Por ejemplo, si $m=3, n=4$, entonces un valor posible de $W(f)={t_1}^4 {t_2}^6 {t_3}^2$, pero otro también podría ser $W(f)={t_1}^4 {t_2}^4 {t_3}^4$.

Sea $F_G$ la función generadora de pesos, entonces la respuesta será el coeficiente de ${t_1}^n {t_2}^n \cdots {t_m}^n$.

Sea $\displaystyle z_p = \sum_{y \in Y} [w(y)]^p = \sum_{i=1}^{m} {t_i}^p$. Aplicando el teorema de enumeración de Pólya, tenemos que:
$$
\begin{align}
F_G &= Z_{C_{mn}}(z_1, \ldots, z_{mn}) \\
&= \dfrac{1}{mn} \sum_{d | mn} \varphi(d) {z_d}^{mn/d} \\
&= \dfrac{1}{mn}\sum_{d | mn} \varphi(d) \left( \sum_{i=1}^{m} {t_i}^d \right)^{mn/d} \\
\end{align}
$$

Por el teorema multinomial, tenemos que:
$$
\begin{align}
\left( \sum_{i=1}^{m} {t_i}^d \right)^{mn/d} &= \sum_{j_1+j_2+\ldots+j_m=mn/d} \binom{mn/d}{j_1, j_2, \ldots, j_m} {({t_1}^d)}^{j_1} {({t_2}^d)}^{j_2} \ldots {({t_m}^d)}^{j_m}
\end{align}
$$
Necesitamos que $dj_1 = dj_2 = \ldots = dj_m = n$, es decir, $j_1 = j_2 = \ldots = j_m = n/d$, es decir, $d | n$. Por lo tanto, el coeficiente de ${t_1}^n {t_2}^n \cdots {t_m}^n$ en la expresión anterior es:
$$
\begin{align}
\binom{mn/d}{\underbrace{n/d, n/d, \ldots, n/d}_\mbox{$m$ veces}} = \dfrac{(mn/d)!}{((n/d)!)^m}
\end{align}
$$
Finalmente, sustituímos en $F_G$:
$$
\begin{align}
ans &= \dfrac{1}{mn}\sum_{d | n} \varphi(d) \dfrac{(mn/d)!}{((n/d)!)^m} \\
&= \dfrac{1}{mn} \sum_{d | n} \varphi(n/d) \dfrac{(md)!}{(d!)^m}
\end{align}
$$

## Problema: contando grafos
Sea $f_{n,e}$ el número de grafos simples no dirigidos y *no etiquetados* con $n$ vértices y $e$ aristas.

Ejemplo, si $n=4$, tenemos las siguientes clases de equivalencia de grafos para $e=0, 1, \ldots, 6$:

Entonces el problema es: dada una $n$, hallar $f_{n,e}$ para toda $e$ tal que $0 \leq e \leq \binom{n}{2}$.

Si contáramos grafos *etiquetados*, la respuesta es el coeficiente de $x^e$ en $(1+x)^\binom{n}{2}$, o sea, $\displaystyle \binom{\binom{n}{2}}{e}$.

La idea de solución para grafos *no etiquetados* consiste en tratar de colorear el conjunto de todas las $\binom{n}{2}$ aristas con dos colores, digamos que blanco y azul. Una arista coloreada de blanco significa que no va a estar presente, y una coloreada de azul que sí va a estar presente.

Entonces sean $X=\{e_1, e_2, \ldots, e_\binom{n}{2}\}$ y $Y=\{0, 1\}$, donde el color 0 es blanco y el 1 es azul. Vamos a representar a cada arista no dirigida $e_i$ de la forma $(u, v)$, donde $1 \leq u < v \leq n$, y por lo tanto, la arista $(v, u)$ es la misma.

El grupo $P_n$ con todas sus permutaciones $\sigma'$ va a estar actuando en las aristas de la siguiente manera: dada una permutación $\sigma \in S_n$, tenemos que $\sigma'(u, v) = (\sigma(u), \sigma(v))$. En otras palabras, los vértices $(u, v)$ estarán conectados si y solo si también los vértices $(\sigma(u), \sigma(v))$ lo están.

Ejemplo:

Ahora asignemos un peso a cada color, de tal forma que nos permita clasificar el número de grafos de acuerdo a su número de aristas. Hagamos que $w(0)=1$ y $w(1)=x$. De esta forma, el coeficiente de $x^e$ en $F_{P_n}$ nos dirá cuántos grafos hay con exactamente $e$ aristas.

Ejemplo, tomando el grafo anterior, tenemos que $W(\sigma') = 1 \cdot 1 \cdot 1 \cdot 1 \cdot x \cdot x = x^2$, pues hay dos aristas azules.

Por lo tanto, tenemos que $z_p = [w(0)]^p + [w(1)]^p = 1^p + x^p = 1 + x^p$.

Finalmente, sustituímos todos los polinomios $z_1, \ldots, z_{\binom{n}{2}}$ en $Z_{P_n}$, es decir, $F_{P_n} = Z_{P_n}(1+x, 1+x^2, \ldots, 1+x^{\binom{n}{2}})$.

El cycle index de $P_n$ se puede encontrar [aquí](https://mathworld.wolfram.com/PairGroup.html), o se puede hallar usando fuerza bruta. Más información de este tema [aquí](https://mathworld.wolfram.com/SimpleGraph.html).

## Problema: número de matrices equivalentes
Hallar el número de matrices de $m \times n$, en donde cada casilla puede colorearse con $k$ colores, y donde las matrices obtenidas mediante el intercambio de filas y columnas son equivalentes.

Notemos que la restricción es equivalente a permutar libremente las filas y las columnas.

Sea $\sigma'(i,j)$ la función que nos devuelve la nueva casilla bajo una permutación de filas y columnas $\sigma'$. Entonces, $\sigma'(i, j) = (\sigma_1(i), \sigma_2(j))$, donde $\sigma_1 \in S_m$ permuta filas y $\sigma_2 \in S_n$ permuta columnas.

Sea $G_{m,n}$ el grupo formado por todas las permutaciones $\sigma'$. Decimos que $G_{mn}$ es el **producto directo** de $S_m$ y $S_n$. Para hallar su cycle index, es decir, $Z_{G_{mn}}$, existe una fórmula para multiplicar monomios:

$$
\begin{align}
{z_i}^{c_i} * {z_j}^{d_j} &= {z_{lcm(i, j)}}^{c_i d_j \gcd(i, j)} \\
({z_1}^{c_1}{z_2}^{c_2} \cdots {z_m}^{c_m}) * ({z_1}^{d_1}{z_2}^{d_2} \cdots {z_n}^{c_n}) &= \prod_{i=1}^{m} \prod_{j=1}^{n} {z_{lcm(i, j)}}^{c_i d_j \gcd(i, j)}
\end{align}
$$