15.5: Applications of Pólya's Enumeration Formula

This section explores a number of situations in which Pólya's enumeration formula can be used. The applications are from a variety of domains and are arranged in increasing order of complexity, beginning with an example from music theory and concluding with counting nonisomorphic graphs.

 

15.5.1 Counting musical scales

Western music is generally based on a system of 12 equally-spaced notes. Although these notes are usually named by letters of the alphabet (with modifiers), for our purposes it will suffice to number them as 0,1,…,11. These notes are arranged into octaves so that the next pitch after 11 is again named 0 and the pitch before 0 is named 11. For this reason, we may consider the system of notes to correspond to the integers modulo 12. With these definitions, a scale is a subset of {0,1,…,11} arranged in increasing order. A transposition of a scale is a uniform transformation that replaces each note x of the scale by \(x+a(mod12)\) for some constant \(a\). Musicians consider two scales to be equivalent if one is a transposition of the other. Since a scale is a subset, no regard is paid to which note starts the scale, either. The question we investigate in this section is “How many nonequivalent scales are there consisting of precisely \(k\) notes?”

Because of the cyclic nature of the note names, we may consider arranging them in order clockwise around a circle. Selecting the notes for a scale then becomes a coloring problem if we say that selected notes are colored black and unselected notes are colored white. In Figure 15.12, we show three 5-note scales using this convention. Notice that since \(S_2\) can be obtained from \(S_1\) by rotating it forward seven positions, \(S_1\) and \(S_2\) are equivalent by the transposition of adding 7. However, \(S_3\) is not equivalent to \(S_1\) or \(S_2\), as it cannot be obtained from them by rotation. (Note that \(S_3\) could be obtained from \(S_1\) if we allowed flips in addition to rotations. Since the only operation allowed is the transposition, which corresponds to rotation, they are inequivalent.)

Figure 15.12. Three scales depicted by coloring

We have now mathematically modeled musical scales as discrete structures in a way that we can use Pólya's Enumeration Theorem. What is the group acting on our black/white colorings of the vertices of a regular 12-gon? One permutation in the group is \(τ=(0 1 2 3 4 5 6 7 8 9 10 11)\), which corresponds to the transposition by one note. In fact, every element of the group can be realized as some power of \(τ\) since only rotations are allowed and \(τ\) is the smallest possible rotation. Thus, the group acting on the colorings is the cyclic group of order 12, denoted \(C_{12}=\{ι,τ,τ^2,…,τ^{11}\}\). Exercise 15.6.5 asks you to write all the elements of this group in cycle notation. The best way to do this is by multiplying \(τ^{i−1}\) by τ (i.e., compute \(ττ^{i−1}\)) to find \(τ\). Once you've done this, you will be able to easily verify that the cycle index is

\(P_{C_{12}}(x_1,...,x_{12}) = \dfrac{x_1^{12}}{12} + \dfrac{x_2^6}{12} + \dfrac{x_3^4}{6} + \dfrac{x_4^3}{6} + \dfrac{x_6^2}{6} + \dfrac{x_{12}}{3}\).

Since we've chosen colorings using black and white, it would make sense to substitute \(x_i=b^i+w^i\) for all \(i\) in \(P_{C_{12}}\) now to find the number of \(k\)-note scales. However, there is a convenient shortcut we may take to make the resulting generating function look more like those to which we grew accustomed in Chapter 8. The information about how many notes are not included in our scale (the number colored white) can be deduced from the number that are included. Thus, we may eliminate the use of the variable \(w\), replacing it by 1. We now find

\(P_{C_{12}}(1+b,1+b^2,…,1+b^{12})=b^{12}+b^{11}+6b^{10}+19b^9+43b^8+66b^7+80b^6+66b^5+43b^4+19b^3+6b^2+b+1\).

From this, we are able to deduce that the number of scales with \(k\) notes is the coefficient on \(b^k\). Therefore, the answer to our question at the beginning of the chapter about the number of 6-note scales is 80.

 

15.5.2 Enumerating isomers

Benzene is a chemical compound with formula \(C_6H_6\), meaning it consists of six carbon atoms and six hydrogen atoms. These atoms are bonded in such a way that the six carbon atoms form a hexagonal ring with alternating single and double bonds. A hydrogen atom is bonded to each carbon atom (on the outside of the ring). From benzene it is possible to form other chemical compounds that are part of a family known as aromatic hydrocarbons. These compounds are formed by replacing one or more of the hydrogen atoms by atoms of other elements or functional groups such as \(CH_3\) (methyl group) or \(OH\) (hydroxyl group). Because there are six choices for which hydrogen atoms to replace, molecules with the same chemical formula but different structures can be formed in this manner. Such molecules are called isomers. In this subsection, we will see how Pólya's Enumeration Theorem can be used to determine the number of isomers of the aromatic hydrocarbon xylenol (also known as dimethylphenol).

Before we get into the molecular structure of xylenol, we need to discuss the permutation group that will act on a benzene ring. Much like with our example of coloring the vertices of the square, we find that there are rotations and flips at play here. In fact, the group we require is the dihedral group of the hexagon, \(D_{12}\). If we number the six carbon atoms in clockwise order as 1,2,…,6, then we find that the clockwise rotation by \(60^\circ\) corresponds to the permutation \(r=(123456)\). The other rotations are the higher powers of \(r\), as shown in Figure 15.13. The flip across the vertical axis is the permutation \(f=(16)(25)(34)\). The remaining elements of \(D_{12}\) (other than the identity \(ι\)) can all be realized as some rotation followed by this flip. The full list of permutations is shown in Figure 15.13, where each permutation is accompanied by the monomial it contributes to the cycle index.

Figure 15.13. Cycle representation of permutations in \(D_{12}\)

With the monomials associated to the permutations in \(D_{12}\) identified, we are able to write down the cycle index

\(P_{D_{12}}(x_1,…,x_6)=\dfrac{1}{12}(x_1^6+2x_6^1+2x_3^2+4x_2^3+3x_1^2x_2^2)\).

With the cycle index determined, we now turn our attention to using it to find the number of isomers of xylenol. This aromatic hydrocarbon has three hydrogen molecules, two methyl groups, and a hydroxyl group attached to the carbon atoms. Recalling that hydrogen atoms are the default from benzene, we can more or less ignore them when choosing the appropriate substitution for the \(x_i\) in the cycle index. If we let \(m\) denote methyl groups and \(h\) hydroxyl groups, we can then substitute \(x_i=1+m^i+h^i\) in \(P_{D_{12}}\). This substitution gives the generating function

\(1+h+3h^2+3h^3+3h^4+h^5+h^6+m+3hm+6h^2m+6h^3m+3h^4m+h^5m+3m^2+6hm^2+11h^2m^2+6h^3m^2+3h^4m^2+3m^3+6hm^3+6h^2m^3+3h^3m^3+3m^4+3hm^4+3h^2m^4+m^5+hm^5+m^6\).

Since xylenol has one hydroxyl group and two methyl groups, we are looking for the coefficient on \(hm^2\) in this generating function. The coefficient is 6, so there are six isomers of xylenol.

In his original paper, Pólya used his techniques to enumerate the number of isomers of the alkanes \(C_nH_{2n+2}\). When modeled as graphs, these chemical compounds are special types of trees. Since that time, Pólya's Enumeration Theorem has been used to enumerate isomers for many different chemical compounds.

 

15.5.3 Counting nonisomorphic graphs

Counting the graphs with vertex set \([n]\) is not difficult. There are \(C(n,2)\) possible edges, each of which can be included or excluded. Thus, there are \(2^{C(n,2)}\) labeled graphs on \(n\) vertices. It's only a bit of extra thought to determine that if you only want to count the labeled graphs on \(n\) vertices with \(k\) edges, you simply must choose a \(k\)-element subset of the set of all \(C(n,2)\) possible edges. Thus, there are

\(\dbinom{\binom{n}{2}}{k}\)

graphs with vertex set \([n]\) and exactly \(k\) edges.

A more difficult problem arises when we want to start counting nonisomorphic graphs on \(n\) vertices. (One can think of these as unlabeled graphs as well.) For example, in Figure 15.14, we show four different labeled graphs on four vertices. The first three graphs shown there, however, are isomorphic to each other. Thus, only two nonisomorphic graphs on four vertices are illustrated in the figure. To account for isomorphisms, we need to bring Pólya's Enumeration Theorem into play.

Figure 15.14. Four labeled graphs on four vertices

We begin by considering all \(2^{C(n,2)}\) graphs with vertex set \([n]\) and choosing an appropriate permutation group to act in the situation. Since any vertex can be mapped to any other vertex, the symmetric group \(S_4\) acts on the vertices. However, we have to be careful about how we find the cycle index here. When we were working with colorings of the vertices of the square, we realized that all the vertices appearing in the same cycle of a permutation \(\pi\) had to be colored the same color. Since we're concerned with edges here and not vertex colorings, what we really need for a permutation to fix a graph is that every edge be sent to an edge and every non-edge be sent to a non-edge. To be specific, if {1,2} is an edge of some \(\textbf{G}\) and \(\pi∈S_4\) fixes \(\textbf{G}\), then \(\{ \pi (1), \pi (2)\}\) must also be an edge of \(\textbf{G}\). Similarly, if vertices 3 and 4 are not adjacent in \(\textbf{G}\), then \(\pi(3)\) and \(\pi(4)\) must also be nonadjacent in \(\textbf{G}\).

To account for edges, we move from the symmetric group \(S_4\) to its pair group \(S_4^{(2)}\). The objects that \(S_4^{(2)}\) permutes are the 2-element subsets of {1,2,3,4}. For ease of notation, we will denote the 2-element subset \(\{i,j\}\) by \(e_{ij}\). To find the permutations in \(S_4^{(2)}\), we consider the vertex permutations in \(S_4\) and see how they permute the \(e_{ij}\). The identity permutation \(ι=(1)(2)(3)(4)\) of \(S_4\) corresponds to the identity permutation \(ι=(e_{12})(e_{13})(e_{14})(e_{23})(e_{24})(e_{34})\) of \(S_4^{(2)}\). Now let's consider the permutation (12)(3)(4). It fixes \(e_{12}\) since it sends 1 to 2 and 2 to 1. It also fixed \(e_{34}\) by fixing 3 and 4. However, it interchanges \(e_{13}\) with \(e_{23}\) (3 is fixed and 1 is swapped with 2) and \(e_{14}\) with \(e_{24}\) (1 is sent to 2 and 4 is fixed). Thus, the corresponding permutation of pairs is \((e_{12})(e_{13}e_{23})(e_{14}e_{24})(e_{34})\). For another example, consider the permutation (123)(4). It corresponds to the permutation \((e_{12}e_{23}e_{13})(e_{14}e_{24}e_{34})\) in \(S_4^{(2)}\).

Since we're only after the cycle index of \(S_4^{(2)}\), we don't need to find all 24 permutations in the pair group. However, we do need to know the types of those permutations in terms of cycle lengths so we can associate the appropriate monomials. For the three examples we've considered, the cycle structure of the permutation in the pair group doesn't depend on the original permutation in \(S_4\) other than for its cycle structure. Any permutation in \(S_4\) consisting of a 2-cycle and two 1-cycles will correspond to a permutation with two 2-cycles and two 1-cycles in \(S_4^{(2)}\). A permutation in \(S_4\) with one 3-cycle and one 1-cycle will correspond to a permutation with two 3-cycles in the pair group. By considering an example of a permutation in \(S_4\) consisting of a single 4-cycle, we find that the corresponding permutation in the pair group has a 4-cycle and a 2-cycle. Finally, a permutation of \(S_4\) consisting of two 2-cycles corresponds to a permutation in \(S_4^{(2)}\) having two 2-cycles and two 1-cycles. (Exercise 15.6.8 asks you to verify these claims using specific permutations.)

Now that we know the cycle structure of the permutations in \(S_4^{(2)}\), the only task remaining before we can find its cycle index of is to determine how many permutations have each of the possible cycle structures. For this, we again refer back to permutations of the symmetric group \(S_4\). A permutation consisting of a single 4-cycle begins with 1 and then has 2, 3, and 4 in any of the 3!=6 possible orders, so there are 6 such permutations. For permutations consisting of a 1-cycle and a 3-cycle, there are 4 ways to choose the element for the 1-cycle and then 2 ways to arrange the other three as a 3-cycle. (Remember the smallest of them must be placed first, so there are then 2 ways to arrange the remaining two.) Thus, there are 8 such permutations. For a permutation consisting of two 1-cycles and a 2-cycle, there are \(C(4,2)=6\) ways to choose the two elements for the 2-cycle. Thus, there are 6 such permutations. For a permutation to consist of two 2-cycles, there are \(C(4,2)=6\) ways to choose two elements for the first 2-cycle. The other two are then put in the second 2-cycle. However, this counts each permutation twice, once for when the first 2-cycle is the chosen pair and once for when it is the “other two.” Thus, there are 3 permutations consisting of two 2-cycles. Finally, only \(ι\) consists of four 1-cycles.

Now we're prepared to write down the cycle index of the pair group

\(P_{S_4^{(2)}}(x_1,…,x_6)=\dfrac{1}{24}(x_6^1+9x_1^2x_2^2+8x_3^2+6x_2x_4)\).

To use this to enumerate graphs, we can now make the substitution \(x_i=1+x^i\) for \(1≤i≤6\). This allows us to account for the two options of an edge not being present or being present. In doing so, we find

\(P_{S_4^{(2)}}(1+x,…,1+x^6)=1+x+2x^2+3x^3+2x^4+x^5+x^6\)

is the generating function for the number of 4-vertex graphs with \(m\) edges, \(0≤m≤6\). To find the total number of nonisomorphic graphs on four vertices, we substitute \(x=1\) into this polynomial. This allows us to conclude there are 11 nonisomorphic graphs on four vertices, a marked reduction from the 64 labeled graphs.

The techniques of this subsection can be used, given enough computing power, to find the number of nonisomorphic graphs on any number of vertices. For 30 vertices, there are

\(334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384 \approx 3.3×10^{98}\)

nonisomorphic graphs, as compared to \(2^{435} \approx 8.9×10^{130}\) labeled graphs on 30 vertices. The number of nonisomorphic graphs with precisely 200 edges is

\(3133824809970726276258772475733640185446767033655017855836082677050799699893512219821910360979601 \approx 3.1×10^{96}\).

The last part of the question about graph enumeration at the beginning of the chapter was about enumerating the graphs on some number of vertices in which every vertex has degree \(r\). While this might seem like it could be approached using the techniques of this chapter, it turns out that it cannot because of the increased dependency between where vertices are mapped.