Sometimes I worry that I should be more consistent or more lenient about the background I expect of my readers. (Readers, I have to admit that I still don’t really know who you are!) Considering how important I think it is that mathematicians value communicating their ideas to non-specialists (what John Armstrong calls the Generally Interested Lay Audience (GILA)), I should probably be putting my money where my mouth is.

So, inspired by the Unapologetic Mathematician, I have decided on a little project: to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory. Posts in this project, or any subsequent similar projects, will be labeled “GILA.” The general plan is to talk about group actions in general, the orbit-stabilizer theorem, the lemma formerly known as Burnside’s, and generating functions on the way. Much of this discussion can be found in Section 7 of Stanley’s lectures on algebraic combinatorics.

The PET is a very general way to think about questions of the following nature:

- How many ways are there to paint the faces of a cube if we consider two colorings related by some rotation to be the same?
- How many ways are there to paint the beads on a necklace if we consider two colorings related by a rotation of the necklace to be the same?
- How many ways are there to place some balls into some urns if we consider two placements related by a relabeling of the balls to be the same? (In other words, we want the balls to be “indistinguishable.”)
- How many graphs with a fixed number of vertices and edges are there if we consider two graphs related by a relabeling of the vertices to be the same? (In other words, we want the graphs to be “non-isomorphic.”)

The general situation is that we have a (finite) set of slots and another (for now, finite) set of objects we want to put into those slots, which it is useful to think of as a set of colors that we can “paint” the slots. We also have a (finite) group of symmetries that controls when we consider two colorings to be “the same.” To understand this situation, it is first necessary to understand something about group actions.

(more…)

Read Full Post »