GILA V: The Polya enumeration theorem and applications

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors (represented by variables ), and we have a set of slots with acted on by a group where each slot will be assigned a color. Define to be the number of orbits of functions under the action of where color is used times. (Since the action of only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

.

Note that setting we recover , which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

Again, the fixed points of a given permutation acting on functions are precisely the functions constant (that is, monochromatic) on each cycle of . Writing down each such fixed point in terms of the number of colors used then requires that we know how many cycles of each size there are in the cycle decomposition of . To that end, we’ll define the cycle index monomial

where denotes the number of cycles of size of and is the corresponding formal variable; note that we require the condition that . Now we can count fixed points as follows: the only ways to color a cycle of size are to color each of the slots the same color, hence what we need to do is to make the substitution . This is the important step! Each term represents a different color with which we can color every slot in the same cycle. We take to the power of and multiply because we can color each cycle independently. Again, note that when we recover the same argument we used to prove baby Polya.

And we’re done! What we’ve proven is the following. Define the cycle index polynomial of the group action of on to be the average of the cycle index monomials, or

.

Then the following holds.

Polya’s enumeration theorem: The generating function is equal to
.

Again, to appreciate this result we’ll work through what it says about cyclic groups and symmetric groups. It turns out the PET has quite a lot to say on these two subjects alone!

Balls and urns

As before, here the symmetry group is . We want to count the number of ways to assign one of urns to each of indistinguishable balls indexed by the multiset of number of times each urn is used; however, since we’re using the full symmetry group, the multiset of times each urn is used uniquely determines the orbit we’re in. In other words, for every choice of . We already knew this, of course, but the really nice thing here is that the full generating function

is the complete homogeneous symmetric polynomial . Summing over all we obtain the identity mentioned in the exercises of the last post,

.

This identity occurs because the choice of a term in each factor uniquely determines the number of times color appears in the corresponding coloring. Note what happens, again, when . What makes this result even nicer is that it implies that if we can express this generating function in terms of the power symmetric functions , we can compute the cycle index polynomials of the symmetric groups all at once!

Recall that the definition of the power symmetric functions is ; then the PET implies that

.

So how do we express this generating function in terms of the power symmetric functions? The answer is very elegant: we simply write

and, multiplying the factors together, this implies the beautiful identity

.

I have a lot to say about this identity, but it deserves its own separate post.

Necklaces

The necklace-counting result extends in a rather straightforward way to this new regime; the argument we used before immediately implies that

and therefore that

.

As promised, we’re going to use this to prove a special case of Lucas’ theorem. First, we’re going to let where is a specified prime. Second, we’re going to restrict to a subgroup of . This is the first time we’re going to need to distinguish between isomorphic groups and non-isomorphic group actions, so I’ll denote by the action of the subgroup of given by the powers of the elements of . This is a cyclic group of order , so again it has the nice property that orbits are either fixed points or full. We’re also going to restrict to the case of two colors again and we’re going to set because we lose no information in this way. The above then reduces to

.

The coefficient of in this generating function counts the number of orbits of necklaces that use of one color and of the other. By the binomial theorem, this coefficient is

if isn’t a multiple of – every element is in a “full” orbit in this case – or if , the coefficient is

hence as desired. One can duplicate the above argument using the properties of the Frobenius map, but as we’ve discussed we already know that the properties of the Frobenius map are intimately related to the group actions of .

Repeatedly applying the Frobenius map gives a proof of the full Lucas’ theorem, and there is a corresponding combinatorial proof given on the Wikipedia article that fits nicely into this framework; instead of considering a cyclic group of prime order we consider an appropriate direct product of cyclic groups. “Action on subsets” is just another way of saying “action on -colorings.”

Young diagrams in a box

This is an example I should’ve mentioned earlier, but the poset of Young diagrams fitting inside a box can be discussed in terms of Polya theory.

The set of slots is an box, and the number of colors is two. One color will denote that a box is filled, while another color will denote that it’s empty. This gives a total of functions, some of which are Young diagrams. What we want to show is that there exists a group acting on an box such that each orbit contains exactly one Young diagram.

The group can be described as follows: it consists of copies of , each of which acts to permute the entries in each row, but we’re also allowed to permute the rows themselves. In other words, a copy of is acting on the copies of . This construction goes by the name of the wreath product . It’s a rather large group, since by construction it has size . The orbits of its action on the functions can be uniquely identified with Young diagrams as follows: first sort the entries in each row so that the filled entries are left-justified, then sort the rows by the number of filled entries they have. This gives a unique Young diagram for each orbit since the multiset of number of filled entries in each row is invariant under the action of . The PET, together with the result we’ve already proved, implies that

.

I don’t, however, have a good idea of how to compute the cycle index polynomial of , and this result is clearly not good enough to do so, since the above identity cannot distinguish between and even though the two groups are very different.

If this isn’t a good way to actually compute , then what can we do with this realization of Young diagrams via a group action? It turns out there are some rather interesting general theorems in this area; see Stanley’s Lectures in Algebraic Combinatorics section 5.

A generalization

The set of colors in the setup of Polya’s theorem can be succinctly described by the generating function , one term for each color. There is a generalization of Polya’s theorem that allows us to replace this generating function by an arbitrary generating function , hence to consider objects more general than a set of distinct colors. Although the proof is essentially the same, I think the proper setting for discussing this generalization is the theory of species. Nevertheless, for the sake of completeness, the more general theorem states that is equal to

.

The value of the generalization is that we can fill the slots with something “fatter” than a single color: we could put, for example, a sequence of colors in, or a graph. That allows us to count more general objects and to use more general combinatorial parameters.

Suppose, for example, that we wanted to compute the generating function for “spindles” – necklaces with a path attached to every vertex – up to cyclic symmetry and indexed by the total number of vertices. The group action is as before, but the “colors” are non-empty sequences, which have the generating function . The generalized PET then tells us that the generating function for spindles with fixed necklace size is

.

This is by no means an obvious result. Applying the generalized PET to the symmetric groups gives the general form of the multiset construction, but again these issues will have to wait until another post.

Exercises

Compute the cycle index polynomials of the group acting on the complete binary tree of depth generated by the symmetries that flip the two children of any vertex, at least for some small . (I don’t know if there’s a nice answer in general; this is an example of an iterated wreath product.)

Let denote the number of involutions on elements. Show, using the cycle index polynomials of the symmetric groups, that

.

This implies both a summation formula and a recurrence relation for via differentiation. Prove both by a direct argument. Can you generalize?

Tags: cycle indices, Frobenius map, generating functions, group actions, Polya theory, symmetric functions, wreath product, Young tableaux