§ Polya Enumeration

• Let $X$ be a set of objects with the action of a group $G$. For example, $X$ is the configurations of a square, represented as 4-tuples by reading the vertices offin clockwise order, and let $G$ be the group of symmetries of a square.
• Let $C$ be the set of colorings $c_1, c_2, \dots c_n$.
• Let the objects of $X$ be colored . That is, we have functions $f: X \to C$ which assigns a color $C$ to each element of $X$. Let $Y$ be the set of colorings $X \to C$.
• We extend the action of the group to the colorings, given by $g (f) \equiv \lambda x. g^{-1}(x)$. This makes the action of the group consistent .
• What's this funny inverse? Well, the idea is this. We really have that $(gf)(gx) \equiv g(f(x))$, as the group must act in an invariant way on the function space and the domain space. So to definethe expression of $(gf)(x')$, we think of it as $(gf)(x') = (gf)(g(g^{-1}x')) = f(g^{-1}x')$.
• Define the weight of a coloring $h \in Y$, (ie $h: X \to C$) to be the monomial given by the product of colors; $wt(h) \equiv \prod_{x \in X} h(x)$. The weight $wt(h)$ is a monomial in the commutative ring $R[c_1, c_2, \dots, c_n]$.
• Statement of Polyma Enumeration: The weight enumerator for the action $G$ on $Y \equiv (X \to C)$ is equal to the cycle index polynomial $Z(G, X)$ with $z_i$ replaced by the power sum symmetric polynomial $P[p](\vec c) \equiv c_1^p + c_2^p + \dots + c_n^p$.

§ Proof via Weighted Burnside Lemma

• Let $g \in G$. By weighted version of Burnside Lemma, we have that

• Suppose that $g \in G$ have a cycle monomial $z_1^{k_1} \dots z_m^{k_m}$. That is, we kount such that $g$ has $k_1$ cycles of length $1$, $k_2$ cycles of length $2$, and so on upto $k_m$ cycles of length $m$. So $g$ has $k_i$ cycles of length $i$.
• We want to know which colorings $y \in Y$ are fixed by $g$.
• Suppose a coloring $y: X \to C$ is fixed by $g$, so $g(y) = y$. Since $g$ pushes things around in its cycles, for each cycle in $g$, we must use a constant color .
• Said differently, all elements in the same cycle of $g$ have the same color.
• Thus for each cycle of length $l$, We must color all of the $l$ elements (of $X$) with the same color.
• We can color distinct cycles independent of each other.
• Thus the weight of a cycle of length $1$ is given by $(c_1 + c_2 + \dots + c_n)$, since we can color the single element with either $c_1$ or $c_2$ and so on upto $c_n$.
• The weight of a cycle of length $2$ is given by $(c_1^2 + c_2^2 + \dots + c_n^2)$, since we can color the two elements in the cycle with either $c_1$ or $c_2$ and so on upto $c_i$.
• The weight of a cycle of length $l$ is given by $(c_1^l + c_2^l + \dots + c_n^l)$ since we can color the $l$ elements in the cycle.
• Since we the element $g$ has $k_1$ cycles of length $1$, the weight of all cycles of length $1$ is $(c_1 + c_2 + dots + c_n)^k_1$.
• Since we the element $g$ has $k_2$ cycles of length $2$, the weight of all cycles of length $2$ is $(c_1^2 + c_2^3 + dots + c_n^2)^k_2$.
• Since we the element $g$ has $k_l$ cycles of length $l$, the weight of all cycles of length $l$ is $(c_1^l + c_2^l + dots + c_n^l)^k_l$.
• Thus, the total weight of $g$ is given by the polynomial $cyc(g)(p_1(\vec c), p_2(\vec c), \dots, p_l(\vec c))$.

§ Example: Weight enumerator for square with $D_4$ actions.

• $G \equiv D_4$
• $X$ is the configurations of a square.
• $C$ are the colors $r, g, b$.
• $Y$ is the set of colorings of $X$ by $C$.