§ 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
$\sum_{O \in Orb(Y)} wt(O) \equiv 1/|G| \sum_{g \in G} \sum_{y \in Fix(g)} wt(y)$
- 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$.