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 be a finite group acting on some finite set
with
. To each partition
of
we may attach the monomial
in the variables
. The cycle type of an element
is the partition of
given by the cycle size of the orbits of
acting on
, which we will denote as
. Furthermore, we define the cycle index for the pair
of
acting on
as the generating function
The Theorem
Let act on
with the cycle index
where
. The generating function for the number of ways to paint
in colors
up to
symmetry is given by evaluating
at the values