Counting and Coloring with Symmetry: A presentation of Polya's Enumeration Theorem with Applications

Abstract

This master's thesis explores the area of combinatorics concerned with counting mathematical objects with regards to symmetry. Two main theorems in this field are Burnside's Lemma and P'{o}lya's Enumeration Theoremfootnote{P'{o}lya's Enumeration Theorem is also known as Redfield--P'{o}lya's Theorem.}. Both theorems yield a formula that will count mathematical objects with regard to a group of symmetries. Burnside's Lemma utilizes the concept of orbits to count mathematical objects with regard to symmetry. As a result of the Burnside Lemma's reliance on orbits, implementation of the lemma can be computationally heavy. In comparison, P'{o}lya's Enumeration Theorem's use of the cycle index of a group eases the computational burden. In addition, P'{o}lya's Enumeration Theorem allows for the introduction of weights allowing the reader to tackle more complicated problems. Building from basic definitions taken from abstract algebra a presentation of the theory leading up to P'{o}lya's Enumeration Theorem is given, complete with proofs. Examples are given throughout to illustrate these concepts. Applications of this theory are present in the enumeration of graphs and chemical compounds.