The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by J. Howard Redfield in 1927. In 1937 it was independently rediscovered by George Pólya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds. The Pólya enumeration theorem has been incorporated into symbolic combinatorics and the theory of combinatorial species.
Simplified, unweighted version Let X be a finite set and let G be a group of permutations of X (or a finite symmetry group that acts on X). The set X may represent a finite set of beads, and G may be a chosen group of permutations of the beads. For example, if X is a necklace of n beads in a circle, then rotational symmetry is relevant so G is the cyclic group Cn, while if X is a bracelet of n beads in a circle, rotations and reflections are relevant so G is the dihedral group Dn of order 2n. Suppose further that Y is a finite set of colors — the colors of the beads — so that YX is the set of colored arrangements of beads (more formally: YX is the set of functions X → Y {\displaystyle X\to Y} .) Then the group G acts on YX. The Pólya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula:
| Y X / G | = 1 | G | ∑ g ∈ G m c ( g ) {\displaystyle \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}
where m = | Y | {\displaystyle m=|Y|} is the number of colors and c(g) is the number of cycles of the group element g when considered as a permutation of X.
Full, weighted version In the more general and more important version of the theorem, the colors are also weighted in one or more ways, and there could be an infinite number of colors provided that the set of colors has a generating function with finite coefficients. In the univariate case, suppose that
f ( t ) = f 0 + f 1 t + f 2 t 2 + ⋯ {\displaystyle f(t)=f_{0}+f_{1}t+f_{2}t^{2}+\cdots }
is the generating function of the set of colors, so that there are fw colors of weight w for each integer w ≥ 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(t1, t2, ...) that tabulates the number of colors with each given vector of weights. The enumeration theorem employs another multivariate generating function called the cycle index:
Z G ( t 1 , t 2 , … , t n ) = 1 | G | ∑ g ∈ G t 1 c 1 ( g ) t 2 c 2 ( g ) ⋯ t n c n ( g ) {\displaystyle Z_{G}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}\cdots t_{n}^{c_{n}(g)}}
where n is the number of elements of X and ck(g) is the number of k-cycles of the group element g as a permutation of X. A colored arrangement is an orbit of the action of G on the set YX (where Y is the set of colors and YX denotes the set of all functions φ: X→Y). The weight of such an arrangement is defined as the sum of the weights of φ(x) over all x in X. The theorem states that the generating function F of the number of colored arrangements by weight is given by:
F ( t ) = Z G ( f ( t ) , f ( t 2 ) , f ( t 3 ) , … , f ( t n ) ) {\displaystyle F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))}
or in the multivariate case:
… excerpt ends here. Continue reading the full article.
