Pólya enumeration theorem
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.
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.
The Pólya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula: where
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: 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.
The theorem states that the generating function F of the number of colored arrangements by weight is given by: or in the multivariate case: To reduce to the simplified version given earlier, if there are m colors and all have weight 0, then f(t) = m and In the celebrated application of counting trees (see below) and acyclic molecules, an arrangement of "colored beads" is actually an arrangement of arrangements, such as branches of a rooted tree.
Its cycle index is which is obtained by analyzing the action of each of the 24 elements of C on the 6 sides of the cube, see here for the details.
A graph on m vertices can be interpreted as an arrangement of colored beads.
With these definitions, an isomorphism class of graphs with m vertices is the same as an orbit of the action of G on the set YX of colored arrangements; the number of edges of the graph equals the weight of the arrangement.
The cycle index of the group S3 acting on the set of three edges is (obtained by inspecting the cycle structure of the action of the group elements; see here).
The cycle index of the group S4 acting on the set of 6 edges is (see here.)
The set T3 of rooted ternary trees consists of rooted trees where every node (or non-leaf vertex) has exactly three children (leaves or subtrees).
In general, two rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes.
We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).
One can view a rooted, ternary tree as a recursive object which is either a leaf or a node with three children which are themselves rooted ternary trees.
These children are equivalent to beads; the cycle index of the symmetric group S3 that acts on them is The Polya enumeration theorem translates the recursive structure of rooted ternary trees into a functional equation for the generating function F(t) of rooted ternary trees by number of nodes.
which by the enumeration theorem gives as the generating function for rooted ternary trees, weighted by one less than the node number (since the sum of the children weights does not take the root into account), so that This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes: where a, b and c are nonnegative integers.
are The simplified form of the Pólya enumeration theorem follows from Burnside's lemma, which says that the number of orbits of colorings is the average of the number of elements of
fixed by the permutation g of G over all permutations g. The weighted version of the theorem has essentially the same proof, but with a refined form of Burnside's lemma for weighted enumeration.
It is equivalent to apply Burnside's lemma separately to orbits of different weight.
denote the corresponding monomial term of f. Applying Burnside's lemma to orbits of weight
that are also fixed by g. If we then sum over all possible weights, we obtain Meanwhile a group element g with cycle structure
if and only if the function φ is constant on every cycle q of g. For every such cycle q, the generating function by weight of |q| identical colors from the set enumerated by f is It follows that the generating function by weight of the points fixed by g is the product of the above term over all cycles of g, i.e.
