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