Pólya enumeration theorem
Encyclopedia
The Pólya enumeration theorem (PET), also known as the Redfield–Pólya Theorem, is a theorem in combinatorics
that both follows and ultimately generalizes Burnside's lemma
on the number of orbits of a group action
on a set. The theorem was first published by John 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 compound
s.
The Pólya enumeration theorem can also be incorporated into symbolic combinatorics
and the theory of combinatorial species
.
on X). The set X can be called an arrangement of beads and G is a chosen group of permutations of the beads. For example, if X is a necklace
of n beads in a circle, then G is by definition the cyclic group Cn, while if X is a bracelet of n beads in a circle, then G is by definition the dihedral group Dn. 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, and suppose that there are |Y| = t colors. (More formally, a "coloring" is a function
.) Then the Pólya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula:
Here c(g) is the number of cycles of the group element g as a permutation of X.
with finite coefficients. In the univariate case, suppose that
is the generating function of the set of colors, so that there are fn colors of weight n for each n ≥ 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(a,b,...) that tabulates the number of colors with each given vector of weights.
The enumeration theorem employs another multivariate generating function called the cycle index
:
Here the kth weight jk(g) is the number of k-cycles of g as a permutation of X. The theorem then says that the generating function F of colored arrangements is the cycle index, composed with the generating function f of the colors, composed with powers of the variables of f:
To reduce to the simplified version, if there are t colors of weight 0, then
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. Thus the generating function f for the colors is derived from the generating function F for arrangements, and the Pólya enumeration theorem becomes a recursive formula.
possible edges, while the set of colors Y = {black,white} corresponds to edges that are present (black) or absent (white). The Pólya enumeration theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices, or the generating function of these graphs according to the number of edges they have. For the latter purpose, we can say that a black or present edge has weight 1, while an absent or white edge has weight 0. Thus 
is the generating function for the set of colors. The relevant symmetry group is 
, the symmetric group
on m letters; an isomorphism class of graphs is equivalent to an orbit of graphs under this group. It acts as a subgroup of
, the group of permutations of all of the edges.
The 8 graphs on three vertices without quotienting by symmetry are shown at the right. There are four isomorphism class of graphs, also shown at the right.
The cycle index of the permutation group of the edges is
Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is
which simplifies to
Thus there is one graph each with 0 to 3 edges.
The cycle index of the edge permutation group for graphs on four vertices is:
Hence
which simplifies to
These graphs are shown at the right.
consists of rooted trees where every node has exactly three children (leaves or subtrees). Small ternary trees are shown at right. Note that ternary trees with n vertices are equivalent to trees with n vertices of degree at most 3. In general, rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. In other words, the group that acts on the children of a node is the symmetric group S3. We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).
We can view a rooted, ternary tree as a recursive object which is either a leaf or three branches which are themselves rooted ternary trees. These branches are equivalent to beads; the cycle index of the symmetric group S3 that acts on them is then
The Polya enumeration theorem then yields a functional equation for the generating function T(x) of the rooted ternary trees:
This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes:
and
where a, b and c are nonnegative integers.
The first few values of
are
Thus there are
colorings.
, 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.
For clearer notation, let
be the variables of the generating function f of 
.
Given a vector of weights
, let 
denote the corresponding monomial term of f.
Applying Burnside's lemma to orbits of weight
, the number of orbits of this weight is
where
is the set of colorings of weight 
that are also fixed by g. If we then sum over all
all possible weights, we obtain
Meanwhile g has a cycle structure
which contributes
to the cycle index of G. The element g fixes an element of
if and only if it is constant on every cycle q of g.
The generating function by weight of a cycle q of |q| identical elements from the set of objects 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.
which equals
Substituting this for
in the sum over all g yields the substituted cycle index
as claimed.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
that both follows and ultimately generalizes Burnside's lemma
Burnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy-Frobenius lemma or the orbit-counting theorem, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects. Its various eponyms include William Burnside, George...
on the number of orbits of a group action
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
on a set. The theorem was first published by John Howard Redfield in 1927. In 1937 it was independently rediscovered by George Pólya
George Pólya
George Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compound
Chemical compound
A chemical compound is a pure chemical substance consisting of two or more different chemical elements that can be separated into simpler substances by chemical reactions. Chemical compounds have a unique and defined chemical structure; they consist of a fixed ratio of atoms that are held together...
s.
The Pólya enumeration theorem can also be incorporated into symbolic combinatorics
Symbolic combinatorics
In mathematics, symbolic combinatorics is one of the many techniques of counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. This particular theory is due to Philippe Flajolet and Robert Sedgewick. This article describes...
and the theory of combinatorial species
Combinatorial species
In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are graphs, permutations, trees, and so on; each of these has an associated generating function...
.
A simplified, unweighted version
Let X be a finite set and let G be a group of permutations of X (or a finite group that actsGroup action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
on X). The set X can be called an arrangement of beads and G is a chosen group of permutations of the beads. For example, if X is a necklace
Necklace (combinatorics)
In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent...
of n beads in a circle, then G is by definition the cyclic group Cn, while if X is a bracelet of n beads in a circle, then G is by definition the dihedral group Dn. 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, and suppose that there are |Y| = t colors. (More formally, a "coloring" is a function
.) Then the Pólya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula:Here c(g) is the number of cycles of the group element g as a permutation of X.
The 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 functionGenerating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
with finite coefficients. In the univariate case, suppose that
is the generating function of the set of colors, so that there are fn colors of weight n for each n ≥ 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(a,b,...) that tabulates the number of colors with each given vector of weights.
The enumeration theorem employs another multivariate generating function called the cycle index
Cycle index
In mathematics, and in particular in the field of combinatorics, cycle indices are used in combinatorial enumeration when symmetries are to be taken into account...
:
Here the kth weight jk(g) is the number of k-cycles of g as a permutation of X. The theorem then says that the generating function F of colored arrangements is the cycle index, composed with the generating function f of the colors, composed with powers of the variables of f:
To reduce to the simplified version, if there are t colors of weight 0, then
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. Thus the generating function f for the colors is derived from the generating function F for arrangements, and the Pólya enumeration theorem becomes a recursive formula.
Graphs on three and four vertices
A graph on m vertices can be interpreted as an arrangement of colored beads. The arrangement X is the set of possible edges, while the set of colors Y = {black,white} corresponds to edges that are present (black) or absent (white). The Pólya enumeration theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices, or the generating function of these graphs according to the number of edges they have. For the latter purpose, we can say that a black or present edge has weight 1, while an absent or white edge has weight 0. Thus is the generating function for the set of colors. The relevant symmetry group is , the symmetric groupSymmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
on m letters; an isomorphism class of graphs is equivalent to an orbit of graphs under this group. It acts as a subgroup of
, the group of permutations of all of the edges.The 8 graphs on three vertices without quotienting by symmetry are shown at the right. There are four isomorphism class of graphs, also shown at the right.
The cycle index of the permutation group of the edges is
Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is
which simplifies to
Thus there is one graph each with 0 to 3 edges.
The cycle index of the edge permutation group for graphs on four vertices is:
Hence
which simplifies to
These graphs are shown at the right.
Rooted ternary trees
The set T3 of rooted ternary treesTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
consists of rooted trees where every node has exactly three children (leaves or subtrees). Small ternary trees are shown at right. Note that ternary trees with n vertices are equivalent to trees with n vertices of degree at most 3. In general, rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. In other words, the group that acts on the children of a node is the symmetric group S3. We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).
We can view a rooted, ternary tree as a recursive object which is either a leaf or three branches which are themselves rooted ternary trees. These branches are equivalent to beads; the cycle index of the symmetric group S3 that acts on them is then
The Polya enumeration theorem then yields a functional equation for the generating function T(x) of the rooted ternary trees:
This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes:
and
where a, b and c are nonnegative integers.
The first few values of
are
- 1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241
Colored cubes
How many ways are there to color the sides of a 3-dimensional cube with t colors, up to rotation of the cube? The rotation group C of the cube acts on the six sides of the cube, which are equivalent to beads. Its cycle index isThus there are
colorings.
Proof of theorem
The simplified form of the Pólya enumeration theorem follows from Burnside's lemmaBurnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy-Frobenius lemma or the orbit-counting theorem, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects. Its various eponyms include William Burnside, George...
, 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.For clearer notation, let
be the variables of the generating function f of .Given a vector of weights
, let denote the corresponding monomial term of f.Applying Burnside's lemma to orbits of weight
, the number of orbits of this weight iswhere
is the set of colorings of weight that are also fixed by g. If we then sum over allall possible weights, we obtain
Meanwhile g has a cycle structure
which contributesto the cycle index of G. The element g fixes an element of
if and only if it is constant on every cycle q of g.The generating function by weight of a cycle q of |q| identical elements from the set of objects 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.
which equals
Substituting this for
in the sum over all g yields the substituted cycle indexCycle index
In mathematics, and in particular in the field of combinatorics, cycle indices are used in combinatorial enumeration when symmetries are to be taken into account...
as claimed.
External links
- Applying the Pólya-Burnside Enumeration Theorem by Hector Zenil and Oleksandr Pavlyk, The Wolfram Demonstrations Project.
- Frederic Chyzak Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory.
- Marko Riedel, Pólya's enumeration theorem and the symbolic method.