Pólya's Enumeration Theorem and Its Applications

This thesis presents and proves Pólya's enumeration theorem (PET) along with the necessary background knowledge. Also, applications are presented in coloring problems, graph theory, number theory and chemistry. The statement and proof of PET is preceded by detailed discussions on Burnside's lemma, the cycle index, weight functions, configurations and the configuration generating function. After the proof of PET, it is applied to the enumerations of colorings of polytopes of dimension 2 and 3, including necklaces, the cube, and the truncated icosahedron. The general formulas for the number of n-colorings of the latter two are also derived. In number theory, work by Chong-Yun Chao is presented, which uses PET to derive generalized versions of Fermat's Little Theorem and Gauss' Theorem. In graph theory, some classic graphical enumeration results of Pólya, Harary and Palmer are presented, particularly the enumeration of the isomorphism classes of unlabeled trees and (v,e)-graphs. The enumeration of all (5,e)-graphs is given as an example. The thesis is concluded with a presentation of how Pólya applied his enumeration technique to the enumeration of chemical compounds.

Grantor dc:publisher

Helsingfors universitet

Year dc:date.issued

2015

Author dc:creator

• von Bell, Matias Kaspar

Contributors dc:contributor

• Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Matematiikan ja tilastotieteen laitos
• University of Helsinki, Faculty of Science, Department of Mathematics and Statistics
• Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för matematik och statistik

Language dc:language.iso

eng

Identifier URI

URN:NBN:fi-fe2017112251184

OAI identifier oai:identifier

oai:helda.helsinki.fi:10138/159032