Pólya's Theorem

Before getting to the full version of Pólya's formula, we must develop a generating function as promised at the beginning of the chapter. To do this, we will return to our example of .

Unlike the generating functions we encountered in , the generating functions we will develop in this chapter will have more than one variable. We begin by associating a monomial with each element of the permutation group involved. In this case, it is \(D_8\), the dihedral group of the square. To determine the monomial associated to a permutation, we need to write the permutation in cycle notation and then determine the monomial based on the number of cycles of each length. Specifically, if \(\pi\) is a permutation of \([n]\) with \(j_k\) cycles of length \(k\) for \(1\leq k\leq n\), then the monomial associated to \(\pi\) is \(x_1^{j_1}x_2^{j_2}\cdots x_n^{j_n}\). Note that \(j_1 + 2j_2 + 3j_3 + \cdots + nj_n = n\). For example, the permutation \(r_1=(1234)\) is associated with the monomial \(x_4^1\) since it consists of a single cycle of length \(4\). The permutation \(r_2=(13)(24)\) has two cycles of length \(2\), and thus its monomial is \(x_2^2\). For \(p=(14)(2)(3)\), we have two \(1\)-cycles and one \(2\)-cycle, yielding the monomial \(x_1^2x_2^1\). In , we show all eight permutations in \(D_8\) along with their associated monomials.

Now let's see how the number of \(2\)-colorings of the square fixed by a permutation can be determined from its cycle structure and associated monomial. If \(\pi(i)=j\), then we know that for \(\pi\) to fix a coloring \(C\), vertices \(i\) and \(j\) must be colored the same in \(C\). Thus, the second vertex in a cycle must have the same color as the first. But then the third vertex must have the same color as the second, which is the same color as the first. In fact, all vertices appearing in a cycle of \(\pi\) must have the same color in \(C\) if \(\pi\) fixes \(C\)! Since we are coloring with the two colors white and gold, we can choose to color the points of each cycle uniformly white or gold. For example, for the permutation \(v=(12)(34)\) to fix a coloring of the square, vertices \(1\) and \(2\) must be colored the same color (\(2\) choices) and vertices \(3\) and \(4\) must be colored the same color (\(2\) choices). Thus, there are \(2\cdot 2=4\) colorings fixed by \(v\). Since there are two choices for how to uniformly color the elements of a cycle, letting \(x_i=2\) for all \(i\) in the monomial associated with \(\pi\) gives the number of colorings fixed by \(\pi\). In , the Fixed colorings column gives the number of \(2\)-colorings of the square fixed by each permutation. Before, we obtained this manually by considering the action of \(D_8\) on the set of all \(16\) colorings. Now we only need the cycle notation and the monomials that result from it to derive this!

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Hopefully the power of the cycle index to count colorings that are distinct when symmetries are considered is becoming apparent. In the next section, we will provide additional examples of how it can be used. However, we still haven't seen the full power of Pólya's technique. From the cycle index alone, we can determine how many colorings of the vertices of the square are distinct. However, what if we want to know how many of them have two white vertices and two gold vertices? This is where Pólya's enumeration formula truly plays the role of a generating function.

Let's again consider the cycle index for the dihedral group \(D_8\): \[\begin{aligned}\end{aligned}\] Instead of substituting integers for the \(x_i\), let's consider what happens if we substitute something that allows us to track the colors used. Since \(x_1\) represents a cycle of length \(1\) in a permutation, the choice of white or gold for the vertex in such a cycle amounts to a single vertex receiving that color. What happens if we substitute \(w+g\) for \(x_1\)? The first term in \(P_{D_8}\) corresponds to the identity permutation \(\iota\), which fixes all colorings of the square. Letting \(x_1=w+g\) in this term gives \[\begin{aligned}\end{aligned}\] which tells us that \(\iota\) fixes one coloring with four gold vertices, four colorings with three gold vertices and one white vertex, six colorings with two gold vertices and two white vertices, four colorings with one gold vertex and three white vertices, and one coloring with four white vertices.

Let's continue establishing a pattern here by considering the variable \(x_2\). It represents the cycles of length \(2\) in a permutation. Such a cycle must be colored uniformly white or gold to be fixed by the permutation. Thus, choosing white or gold for the vertices in that cycle results in two white vertices or two gold vertices in the coloring. Since this happens for every cycle of length \(2\), we want to substitute \(w^2+g^2\) for \(x_2\) in the cycle index. The \(x_1^2x_2^1\) terms in \(P_{D_8}\) are associated with the flips \(p\) and \(n\). Letting \(x_1=w+g\) and \(x_2 = w^2+g^2\), we find \[\begin{aligned}\end{aligned}\] from which we are able to deduce that \(p\) and \(n\) each fix one coloring with four gold vertices, two colorings with three gold vertices and one white vertex, and so on. Comparing this with shows that the generating function is right on.

As with the other results we've discovered in this chapter, this property of the cycle index holds up beyond the case of coloring the vertices of the square with two colors. The full version is Pólya's enumeration theorem:

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.