Skip to main content
Logo image

Applied Combinatorics

Chapter 15 Pólya’s Enumeration Theorem

In this chapter, we introduce a powerful enumeration technique generally referred to as Pólya’s enumeration theorem 1 . Pólya’s approach to counting allows us to use symmetries (such as those of geometric objects like polygons) to form generating functions. These generating functions can then be used to answer combinatorial questions such as
  1. How many different necklaces of six beads can be formed using red, blue and green beads? What about \(500\)-bead necklaces?
  2. How many musical scales consisting of \(6\) notes are there?
  3. How many isomers of the compound xylenol, \(\text{C} _6\text{H} _3(\text{CH} _3)_2(\text{OH} )\text{,}\) are there? What about \(\text{C} _n \text{H} _{2n+2}\text{?}\) (In chemistry, isomers are chemical compounds with the same number of molecules of each element but with different arrangements of those molecules.)
  4. How many nonisomorphic graphs are there on four vertices? How many of them have three edges? What about on \(1000\) vertices with \(257,000\) edges? How many \(r\)-regular graphs are there on \(40\) vertices? (A graph is \(r\)-regular if every vertex has degree \(r\text{.}\))
To use Pólya’s techniques, we will require the idea of a permutation group. However, our treatment will be self-contained and driven by examples. We begin with a simplified version of the first question above.
Like so many results of mathematics, the crux of the result was originally discovered by someone other than the mathematician whose name is associated with it. J.H. Redfield published this result in 1927, 10 years prior to Pólya’s work. It would take until 1960 for Redfield’s work to be discovered, by which time Pólya’s name was firmly attached to the technique.