GILA III: The orbit-counting lemma and baby Polya

The orbit-stabilizer theorem implies, very immediately, one of the most important counting results in group theory. The proof is easy enough to give in a paragraph now that we’ve set up the requisite machinery. Remember that we counted fixed points by looking at the size of the stabilizer subgroup. Let’s count them another way. Since a fixed point is really a pair such that , and we’ve been counting them indexed by , let’s count them indexed by . We use to denote the set of fixed points of . (Note that this is a function of the group action, not the group, but again we’re abusing notation.) Counting the total number of fixed points “vertically,” then “horizontally,” gives the following.

Proposition: .

On the other hand, by the orbit-stabilizer theorem, it’s true for any orbit that , since the cosets of any stabilizer subgroup partition . This immediately gives us the lemma formerly known as Burnside’s, or the Cauchy-Frobenius lemma, which we’ll give a neutral name.

Orbit-counting lemma: The number of orbits in a group action is given by , i.e. the average number of fixed points.

In this post we’ll investigate some consequences of this result.

First, though, I’d like to note that the proof is usually presented slightly differently. I prefer this presentation because “vertical” and “horizontal” counting is a very general technique and it’s good to see it spelled out when it appears. The orbit-counting lemma is not, by any means, a deep or technical result, but its value is in the change of perspective: averaging the behavior of every group element tells us the aggregate behavior of the group action. The emphasis on also ties the lemma into representation theory, since fixed points are an example of a character, and such averaging arguments are also common in representation theory.

Now, one example application I mentioned was about painting the faces of a cube up to rotational symmetry. This is the example used in the Wikipedia article on Burnside’s lemma, so instead of repeating Wikipedia I’ll just add that the group in question is known as the octahedral group. It’s not too hard to list its elements explicitly and figure out their fixed points.

I would give more examples, but the next big result I want to prove is, in my opinion, just as easy for the general case as for any of the interesting examples, so I’ll give the examples later. Recall that the general situation the PET deals with is that, given a set on which a group acts, we want to compute the orbits of the induced group action on functions where is a (for now, finite) set of “colors” or “urns.” So let denote the number of orbits of the induced action on functions . (Once more, this is a function of the group action and not just the group.) Orbit-counting tells us that to do this it suffices to count the number of fixed points of a given .

When does a permutation fix a function ? This is possible for some function if and only if for all , but after a moment’s thought this condition is equivalent to every slot in a cycle having the same color. In other words, if denotes the number of cycles in the cycle decomposition of (with respect to the group action on ), then (with respect to the group action on functions), since each cycle can be colored independently of the other cycles. This gives the following preliminary result which we will generalize to Polya’s theorem.

Baby Polya: .

In other words, is a polynomial (which would not have been obvious without orbit-counting) and the coefficient of is the number of permutations in with cycles divided by . It is, of course, quite useful to be able to describe an important aspect of the group action on functions using only information about the group action on , but to really appreciate this result we should apply it to a few examples.

Balls and urns

In this example is a set of size and it is being acted on by the full symmetry group ; this is just the balls and urns problem, with slots as the balls and colors as the urns. It can be solved with an elementary counting argument: an arrangement of indistinguishable balls into distinguishable urns is equivalent to a string of symbols, of which correspond to balls and of which correspond to “dividers” between urns. A typical string looks like

O O O O | O | | O O | | |

which corresponds to the sequence of seven balls in seven urns. By an elementary counting argument (which can be phrased in terms of group actions if you like), the number of ways to do this is

.

Note that this is a polynomial in of degree ; baby Polya tells us that it is also equal to

and therefore that the coefficient of in is the number of permutations in with cycles in their cycle decomposition. This is a defining identity of the (unsigned) Stirling cycle numbers. (Giving a direct proof of this fact is a good exercise.)

In this example, baby Polya didn’t tell us a better way to count the orbits of the group action, but rather gave us information about the group of symmetries. In the next example, we know more about the group of symmetries than the orbits.

Necklaces

Now the symmetry group is the cyclic group and is a finite set of colors for each of the beads of a necklace. Describing the cycle decomposition of elements of requires some number theory, so it’s instructive to look at an example. For example, when and the group is generated by , the cycle decompositions of its powers are as follows.

An easy way to describe what’s going on is that is isomorphic to the addition of . The length of any cycle is the smallest positive integer such that . If then we can take ; more generally,

.

It follows that the number of cycles in the cycle decomposition of is . By baby Polya, the number of necklaces with beads and colors is

.

To get a nicer formula, we need to count the solutions to . This is equivalent to solving , which has solutions (in the range we care about) by the definition of the totient function. It follows that the number of necklaces is also

.

Setting gives a classic proof of the identity . Setting gives the number of binary necklaces, which appears as A000031 in the OEIS. This identity can also be proven via Mobius inversion, another fascinating area of combinatorics I hope to discuss someday.

Simple graphs of small order

Here is the set of pairs of vertices, which we’ll denote , the action is the induced action of the full symmetry group acting on pairs in the obvious way, and we are only interested in functions , where a denotes that the edge is there. Unfortunately, it is very difficult to write down the cycle decomposition of permutations acting on pairs in general, so we’ll have to make do with small examples.

First, it should be clear that the number of cycles induced by a given permutation on depends only on its conjugacy class, since conjugation is equivalent to relabeling the elements of each cycle. In fact, the number of conjugacy classes in is given by the number of partitions of , so let’s take , which only has seven partitions. The symmetry group has elements arranged in the following conjugacy classes, which we’ll name using a representative element:

1. The identity, of which there is one. It has cycles, one for every edge.
2. , of which there are . Every edge is in a cycle of order five, so there are cycles.
3. , of which there are . The six edges connecting organize into two cycles, but of different sizes (check this). The remaining four edges form another cycle, so there are cycles.
4. , of which there are . The three edges connecting form one cycle. The six edges connecting to form two cycles. The edge is fixed, so there are cycles.
5. , of which there are . The six edges connecting to form three cycles. The remaining four edges are all fixed, so there are cycles.
6. , of which there are . The four edges connected to form two cycles. The edges are fixed. The remaining four edges form two cycles, so there are cycles.
7. , of which there are . The edge is fixed and the edges connecting form their own cycle. The remaining six edges are in their own cycle, so there are cycles.

Phew! In total, baby Polya tells us that the number of non-isomorphic (not necessarily connected) simple graphs on vertices is

(which doesn’t seem to display entirely, unfortunately). This computes to , and you can find the list here. But isn’t this computation so much easier than trying to list them by hand and only finding ? This is sequence A000088 in the OEIS, which also corroborates the value of . Stanley says that there exist explicit formulas describing the cycle decomposition of the action of of , so everything we’ve done here generalizes.

Now, by restricting ourselves to a few classes of permutation that we understand well, we can compute lower bounds on the number of non-isomorphic graphs. For example, taking only the identity gives the trivial lower bound , which is what would happen if every graph had full automorphism group. Taking the identity and every transposition gives

.

The OEIS gives more precise asymptotic expansions along these lines. We can also use this technique to get an upper bound. First, note that the reason we picked transpositions is that any non-identity permutation induces at most cycles in its action on edges (why?) and transpositions are the equality case. All other permutations induce larger cycles, so have less of them, which gives the upper bound

.

Unfortunately, the two are rather far apart (far larger than a constant factor). Even if we attempt the casework going through other “nice” conjugacy classes, I believe the gap between the lower and upper bounds we get remains large. The upper bound gives us much more information than the lower bound, however; asymptotically, the lower bound reduces to the trivial lower bound, whereas the upper bound is a factor of smaller than the trivial upper bound (the number of labeled graphs on vertices).

Where do we go from here?

The analysis we had to do in the case of simple graphs suggests that we might not only like to count the number of cycles in a given group action, but how many cycles there are of each length. It would be useful, in particular, if we could do this for the symmetric group. Our analysis also suggests that baby Polya isn’t detailed enough: if we want to compute the number of non-isomorphic graphs with a fixed number of vertices and also a fixed number of edges, what we need is a way to generalize baby Polya to count functions with a specified number of uses of each color.

Both of these concerns are answered by the PET and its surrounding machinery. As a motivating example, consider “prime necklaces,” i.e. let be prime. Then the necklace-counting result tells us that the number of necklaces is

which, as we have seen, gives us a combinatorial proof of Fermat’s little theorem. Now let where is an odd prime and let’s count the number of necklaces using two colors, but with the additional constraint that there are exactly beads of the first color and beads of the other. This is a natural enough question, but baby Polya isn’t equipped to specify how many of each color there are.

We can solve this problem “by hand,” though. There are “labeled” necklaces. Two of these necklaces are in their own orbit: they are the necklaces consisting of alternating colors. Every other “labeled” necklace has trivial stabilizer subgroup (why?), hence is in a “full” orbit. This gives a combinatorial proof that

which is a special case of a special case of Lucas’ theorem. More generally, it’s true that

and if we could generalize baby Polya to computing the number of necklaces with such that of the beads are of one color and of the beads are of the other, we could prove this as well. Again, this can be proven “by hand” (and it’s easier to consider a smaller symmetry group to do it), but we’re going for generality here.

What’s going to happen is that while it will be tedious to compute the number of orbits that use a particular combination of colors, it will be very interesting to compute the number of orbits using every combination of colors, packaged into a generating function; the particular coefficients of this generating function will tell us about particular combinations of colors, but it’s the entire function that is most easily computed. The next post will discuss and justify the use of generating functions; I’ll try to start from the beginning and give plenty of references.

Exercises

Compute for “dihedral” necklaces, i.e. replace with the dihedral group .

Compute for “alternating” balls-and-urns, i.e. replace with the alternating group .

Compute directly the number of permutations in in the conjugacy class given by a partition ; in other words, the number of permutations with a cycle decomposition consisting of cycles of lengths .

Give a second proof of the orbit-counting lemma by analyzing the linear operator on the representation of given by the free vector space over .

If you haven’t seen it before, give a combinatorial proof that . (Bonus: why is it interesting to write the RHS as ? What does this have to do with the third exercise?)