Pólya Enumeration Theorem

The Pólya Enumeration Theorem is a useful generalization of Burnside's Lemma in Group Theory. Published first by J. Howard Redfield in 1927 and then independently discovered by George Pólya in 1937, the theorem is also commonly used in combinatorics problems.

Background

Let $G$ be a finite group acting on some finite set $\mathcal{X}$ with $|\mathcal{X}|=N$ . To each partition $N=\sum n_j$ of $N$ we may attach the monomial $\prod_j t_{n_j}$ in the variables $t_1,t_2,t_3,...,t_N$ . The cycle type of an element $g\in G$ is the partition of $N$ given by the cycle size of the orbits of $g$ acting on $\mathcal{X}$ , which we will denote as $z_g(t_1,..., t_N)$ . Furthermore, we define the cycle index for the pair $(G,\mathcal{X})$ of $G$ acting on $\mathcal{X}$ as the generating function $Z(t_1,t_2,...,t_N)=\frac{1}{|G|}\sum_{g\in G} z_g(t_1,t_2,...,t_N)$

The Theorem

Let $G$ act on $\mathcal{X}$ with the cycle index $Z(t_1,t_2,...,t_N)$ where $|\mathcal{X}|=N$ . The generating function for the number of ways to paint $\mathcal{X}$ in colors $a_1,a_2,...,a_n$ up to $G$ symmetry is given by evaluating $Z(t_1,t_2,...,t_N)$ at the values $t_k=a_{1}^k+a_{2}^k+...+a_{n}^k.$

Page

Toolbox

Search

Pólya Enumeration Theorem

Background

The Theorem