Pólya Enumeration Theorem

The Pólya Enumeration Theorem extends Burnside's lemma to produce generating functions that count distinct colorings by weight. It is one of the most widely applied results in enumerative combinatorics.

Statement

Theorem8.2Pólya Enumeration Theorem

Let $G$ be a permutation group acting on $[n]$ , and let $R$ be a set of colors with a weight function $w: R \to \mathbb{Z}_{\geq 0}$ . Define the figure counting series $f(x) = \sum_{r \in R} x^{w(r)}$ . Then the generating function for the number of distinct colorings by total weight is: $\sum_{\text{orbits } \omega} x^{w(\omega)} = Z_G\!\left(f(x), f(x^2), \ldots, f(x^n)\right),$ where $Z_G$ is the cycle index of $G$ and $w(\omega)$ is the total weight of a representative coloring in orbit $\omega$ .

Proof Sketch

Proof

Each coloring $c: [n] \to R$ contributes weight $\prod_{i=1}^n x^{w(c(i))}$ to the weighted count. A permutation $g \in G$ with cycle structure $(c_1, c_2, \ldots, c_n)$ fixes coloring $c$ if and only if $c$ is constant on each cycle of $g$ . The contribution of colorings fixed by $g$ to the weighted sum is: $\prod_{k=1}^n \left(\sum_{r \in R} x^{k \cdot w(r)}\right)^{c_k(g)} = \prod_{k=1}^n f(x^k)^{c_k(g)}.$

Applying Burnside's lemma: $\text{weighted count} = \frac{1}{|G|} \sum_{g \in G} \prod_{k=1}^n f(x^k)^{c_k(g)} = Z_G(f(x), f(x^2), \ldots, f(x^n)). \quad \square$

■

Applications

ExampleCounting Rooted Trees

Rooted unlabeled trees can be counted using the Pólya Enumeration Theorem applied to the symmetric group acting on subtrees. If $t(x) = \sum_{n \geq 1} t_n x^n$ is the generating function for rooted trees, then: $t(x) = x \cdot Z_{S_\infty}(t(x), t(x^2), t(x^3), \ldots) = x \exp\left(\sum_{k \geq 1} \frac{t(x^k)}{k}\right).$ The first few values: $t_1 = 1, t_2 = 1, t_3 = 2, t_4 = 4, t_5 = 9$ .

RemarkDe Bruijn's Generalization

De Bruijn extended the Pólya Enumeration Theorem to handle cases where the symmetry group also acts on the colors. This power group enumeration theorem counts structures up to symmetry of both positions and colors, and has applications in coding theory and the enumeration of chemical isomers.

ExampleCounting Unlabeled Graphs

The number of non-isomorphic graphs on $n$ vertices equals $Z_{S_n^{(2)}}(2, 2, \ldots, 2)$ , where $S_n^{(2)}$ is the symmetric group acting on $\binom{n}{2}$ edges by permuting vertices. For $n = 4$ : there are exactly 11 non-isomorphic graphs, computed via the cycle index of $S_4$ acting on edge pairs.