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.
Rotations and relabelings are both examples of symmetries that an object or collection of objects may have. Our broad goal is to discuss how finite sets behave “up to symmetry,” where we specify the symmetry as a group equipped with an “action.” There are plenty of places to learn about the basic definitions in group theory, so if you’re unfamiliar with the subject, John Armstrong’s introduction over at the Unapologetic Mathematician is a good one, and he has posts about group actions as well, although you may have to start from the beginning of the blog to get the full benefit of the category-oriented discussion. In any case, you should refer there for definitions.
Here’s a concrete example. I have three urns , and in them I want to place five balls . Such a placement consists of an assignment, to each ball, of a unique urn: in other words, a placing of the balls in the urns is a function from the set of balls to the set of urns . An example of such a function is
.
This says that ball is to be placed in urn and so forth. Right now we are in the “distinguishable” case: I have named all of the balls as well as all of the urns. The total number of such placements is easy to count, since it is just the total number of functions : since each ball can be in one of three urns, there are possible placements.
What do we mean when we decide to make the balls “indistinguishable”? It means, in short, that we’re identifying two placements if a permutation of the balls makes them the same! We’ve erased their names. This is an example of the group action of the full permutation group on five elements. It’s important to note that is acting on two different sets here: it is acting both on and on the set of functions . We can be more specific, too: a permutation acts on functions by sending to . (We use the inverse for the same reason that, if we want to shift the graph of a function to the left, we shift to the right.)
Now, any group action induces an equivalence relation, which is what we really mean by “indistinguishable”: if a permutation in the group sends two elements to each other, we consider them “equivalent.” The equivalence classes of this relation are called orbits, and when we want to count “indistinguishable” members of some set under some symmetry, it’s orbits that we’re really counting. The orbit to which an element belongs is precisely the set . Thinking in terms of equivalence relations is a good way to make sense of the group axioms. Why do we require an identity? This is the same as requiring that group actions induce reflexivity. Why do we require closure under composition? This is the same as requiring that group actions induce transitivity; if is equivalent to , which is also equivalent to , then better be equivalent to . Why do we require closure under inverses? This is the same as requiring that group actions induce symmetry; if is equivalent to , we’d like it if is equivalent to . (Associativity is a property of composition of functions.)
Continuing the above example, the simplest orbits of any group action consist of a single element. You should be able to convince yourself that the only single-element orbits of the action of on functions are those in which every ball is in the same urn, of which there are three: one for each urn. In fact, you should be able to convince yourself that in general the orbits correspond to multisets of ball numbers (and this is one way to define multisets abstractly): an orbit is uniquely specified by the number of balls in each urn. So if are the number of balls in urns , then orbits are in bijection with solutions to
in the non-negative integers. This leads to a neat solution to this particular problem via generating functions which the PET generalizes significantly, but we’ll discuss that when we get there. (Note that these are not the same as partitions of into three parts, since “order matters” here: to define partitions abstractly it is necessary to also define a group action on urns. There is a generalization of Polya’s theorem due to de Brujin that handles this, but I don’t know of any references.)
For now, let’s look at another special case: suppose a group action is generated by a single bijection . (This happens, for example, when talking about coloring necklaces.) What do the orbits look like? The orbit associated to is precisely the set , and since the underlying set is finite this sequence must be eventually periodic. Since is invertible, the sequence must in fact be periodic – that is, it must return back to – so the orbit associated to is in fact a cycle. This defines what is called the cycle decomposition of . Cycle decompositions are fundamental to Polya theory. A good way to visualize cycle decompositions is to draw the functional graph of : its vertices are the elements of the set on which acts and there is an edge from to if . The existence of cycle decompositions is equivalent to the fact that the functional graph of a bijection is a disjoint union of (directed) cycle graphs.
We write cycle decompositions as concatenations of terms that look like : this means the cycle . If this is , then has cycle decomposition . Geometrically, if is a rotation by acting on a square, then is a rotation by , so it swaps opposite vertices. The convention I will be using is that permutations multiply the same way as function composition, from right to left.
More generally, to understand the group actions of a cyclic groups we need to know the divisors of . Any cycle of length defines a group action of the cyclic group, and in the other direction if is a permutation of order then its cycle decomposition must contain only cycles of length dividing . In the next post we will investigate the natural generalization of this observation by proving a structure theorem for group actions.
Exercises
If you haven’t seen it before, solve the balls-and-urns problem from first principles: how many ways are there to place indistinguishable balls in distinguishable urns?
Write down the cycle decomposition of the reflectional and rotational symmetries of a cube. How many elements does the corresponding group have?
Write down the cycle decomposition of every element of a cyclic group of order acting on . Which permutations consist of a single cycle?
Let be two elements in the same orbit, and let denote stabilizer subgroup. Show that is a torsor for , and vice versa. What is the non-canonical choice that determines an isomorphism? How is this related to andrea’s example?
[…] taste and you can solve them using representation theory/group theory. One example I know is this series of blog posts by Qiaochu Yuan applying group theory to few basic combinatorial questions about […]
A stable link to Stanley’s “Topics in Algebraic Combinatorics” appears to be available here: http://www-math.mit.edu/~rstan/algcomb/algcomb.pdf. Polya enumeration is covered in Chapter 7.
Hey ! I really love your blog.
Just a comment to point to a very useful link.
Introduction to the Theory of
Species of Structures
I really enjoy combinatorics a lot. I’ve first learned about Polya theory by learning Species theory which is a very enlightening reformulation of Polya theory by A. Joyal.
Unfortunately, the link on Stanley’s lectures on algebraic combinatorics is broken.
Yes, I saw a more permanent link somewhere on MO but have forgotten where it was…
I think you’ll find that in the distinguishable case, each of the five balls can be placed in 1 of 3 urns for a total of 3^5 (not 5^3) permutations.
[…] any prerequisites other than a passing familiarity with group theory.” It begins with GILA I: Group Actions and Equivalence Relations, the last post of the series being GILA VI: The cycle index polynomials of the symmetric […]
Whoops; thanks for the correction.
For the exercise on the balls-and-urns problem, I think you mean n *in*distinguishable balls in k distinguishable urns.
[…] Comments GILA I: Group action… on Non-canonical isomorphism…Qiaochu Yuan on Young diagrams, q-analogues, […]