Combinatorics, Week 9
March 22, 2017

For this meeting, we will begin the study of counting with symmetry.

Here is a representative example: There are 120 (10 choose 3) ways to mark three of ten circles. However, if the circles are arranged in a triangle as shown above, and we consider rotations and flips of a pattern to be the same pattern, then there are only 25 distinct patterns:

• Triangle Orbits

How does one count such problems, in general?

The following Wikipedia pages are of interest:

• Burnside’s lemma
• Pólya enumeration theorem
• Necklace (combinatorics)

The following textbooks cover counting with symmetry, at varying levels.

Chapter 6 Group Actions and Counting (pp 107-121):

• 2011 Camina, Lewis - An introduction to enumeration

Chapter 6 Polya’s Theory of Counting (pp 55-85):

• 1983 Pólya, Tarjan, Woods - Notes on Elementary Combinatorics

Chapter 6 Enumeration of Patterns (pp 239-285):

• 2007 Aigner - A Course in Enumeration

I once taught an entry-level course on symmetry; here is a web page on wallpaper patterns:

• The Seventeen Wallpaper Patterns

It would be an interesting puzzle to find counting problems related to these infinite groups.