# Applied Combinatorics

## Section15.4Pó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 Section 15.1.

### Subsection15.4.1The cycle index

Unlike the generating functions we encountered in Chapter 8, 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\text{,}$$ 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\text{,}$$ then the monomial associated to $$\pi$$ is $$x_1^{j_1}x_2^{j_2}\cdots x_n^{j_n}\text{.}$$ Note that $$j_1 + 2j_2 + 3j_3 + \cdots + nj_n = n\text{.}$$ 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\text{.}$$ The permutation $$r_2=(13)(24)$$ has two cycles of length $$2\text{,}$$ and thus its monomial is $$x_2^2\text{.}$$ For $$p=(14)(2)(3)\text{,}$$ we have two $$1$$-cycles and one $$2$$-cycle, yielding the monomial $$x_1^2x_2^1\text{.}$$ In Figure 15.10, 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\text{,}$$ then we know that for $$\pi$$ to fix a coloring $$C\text{,}$$ vertices $$i$$ and $$j$$ must be colored the same in $$C\text{.}$$ 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\text{!}$$ 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\text{.}$$ 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\text{.}$$ In Figure 15.10, 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!
Recall that Burnside’s Lemma states that the number of colorings fixed by the action of a group can be obtained by adding up the number fixed by each permutation and dividing by the number of permutations in the group. If we do that instead for the monomials arising from the permutations in a permutation group $$G$$ in which every cycle of every permutation has at most $$n$$ entries, we obtain a polynomial known as the cycle index $$P_G(x_1,x_2,\dots,x_n)\text{.}$$ For our running example, we find
\begin{equation*} P_{D_8}(x_1,x_2,x_3,x_4) = \frac{1}{8}\left(x_1^4 + 2x_1^2x_2^1 + 3x_2^2 + 2x_4^1\right). \end{equation*}
To find the number of distinct $$2$$-colorings of the square, we thus let $$x_i=2$$ for all $$i$$ and obtain $$P_{D_8}(2,2,2,2) = 6$$ as before. Notice, however, that we have something more powerful than Burnside’s lemma here. We may substitute any positive integer $$m$$ for each $$x_i$$ to find out how many nonequivalent $$m$$-colorings of the square exist. We no longer have to analyze how many colorings each permutation fixes. For instance, $$P_{D_8}(3,3,3,3) = 21\text{,}$$ meaning that $$21$$ of the $$81$$ colorings of the vertices of the square using three colors are distinct.

### Subsection15.4.2The full enumeration formula

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\text{:}$$
\begin{equation*} P_{D_8}(x_1,x_2,x_3,x_4) = \frac{1}{8}\left(x_1^4 + 2x_1^2x_2^1 + 3x_2^2 + 2x_4^1\right). \end{equation*}
Instead of substituting integers for the $$x_i\text{,}$$ 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\text{?}$$ The first term in $$P_{D_8}$$ corresponds to the identity permutation $$\iota\text{,}$$ which fixes all colorings of the square. Letting $$x_1=w+g$$ in this term gives
\begin{equation*} (w+g)^4 = g^4+4 g^3 w+6 g^2 w^2+4 g w^3+w^4, \end{equation*}
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\text{.}$$ 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\text{,}$$ 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\text{.}$$ Letting $$x_1=w+g$$ and $$x_2 = w^2+g^2\text{,}$$ we find
\begin{equation*} x_1^2x_2^1 = g^4+2 g^3 w+2 g^2 w^2+2 g w^3+w^4, \end{equation*}
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 Figure 15.2 shows that the generating function is right on.
By now the pattern is becoming apparent. If we substitute $$w^i+g^i$$ for $$x_i$$ in the cycle index for each $$i\text{,}$$ we then keep track of how many vertices are colored white and how many are colored gold. The simplification of the cycle index in this case is then a generating function in which the coefficient on $$g^s w^t$$ is the number of distinct colorings of the vertices of the square with $$s$$ vertices colored gold and $$t$$ vertices colored white. Doing this and simplifying gives
\begin{equation*} P_{D_8}(w+g,w^2+g^2,w^3+g^3,w^4+g^4) = g^4+g^3 w+2 g^2 w^2+g w^3+w^4. \end{equation*}
From this we find one coloring with all vertices gold, one coloring with all vertices white, one coloring with three gold vertices and one white vertex, one coloring with one gold vertex and three white vertices, and two colorings with two vertices of each color.
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:
If we return to coloring the vertices of the square but now allow the color blue as well, we find
\begin{equation*} P_{D_8}(w+g+b,w^2+g^2+b^2,w^3+g^3+b^3,w^4+g^4+b^4) = b^4+b^3 g+2 b^2 g^2\\+b g^3+g^4+b^3 w+2 b^2 g w+2 b g^2 w+g^3 w+2 b^2 w^2+2 b g w^2+2 g^2 w^2\\+b w^3+g w^3+w^4. \end{equation*}
From this generating function, we can readily determine the number of nonequivalent colorings with two blue vertices, one gold vertex, and one white vertex to be $$2\text{.}$$ Because the generating function of Pólya’s Enumeration Theorem records the number of nonequivalent patterns, it is sometimes called the pattern inventory.
What if we were interested in making necklaces with $$500$$ (very small) beads colored white, gold, and blue? This would be equivalent to coloring the vertices of a regular $$500$$-gon, and the dihedral group $$D_{1000}$$ would give the appropriate transformations. With a computer algebra system 1  such as Mathematica®, it is possible to quickly produce the pattern inventory for such a problem. In doing so, we find that there are
\begin{align*} \amp 3636029179586993684238526707954331911802338502600162304034603583\\ \amp 2580600191583895484198508262979388783308179702534404046627287796\\ \amp 4304252714992703135653472347417085467453334179308247819807028526\\ \amp 92187253642441292279756575936040804567103229 \approx 3.6\times 10^{235} \end{align*}
possible necklaces. Of them,
\begin{align*} \amp 2529491842340460773490413186201010487791417294078808662803638965\\ \amp 6782447138833704326875393229442323085905838200071479575905731776\\ \amp 6605088026968640797415175535033372572682057214340157297357996\\ \amp 345021733060\approx 2.5\times 10^{200} \end{align*}
have $$225$$ white beads, $$225$$ gold beads, and $$50$$ blue beads.
The remainder of this chapter will focus on applications of Pólya’s Enumeration Theorem and the pattern inventory in a variety of settings.
With some more experience in group theory, it is possible to give a general formula for the cycle index of the dihedral group $$D_{2n}\text{,}$$ so the computer algebra system is a nice tool, but not required.