Counting and Coloring with Symmetry : A presentation of Polya's Enumeration Theorem with Applications
Amanda Noel Bjørge · BIBSYS Brage (BIBSYS (Norway)) · 2009
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. \t \tBuilding 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.