$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.3: Pólya-Redfield Enumeration Theory

• • Contributed by Kenneth P. Bogart
• Professor (Mathematics) at Dartmouth University
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

George Pólya and Robert Redfield independently developed a theory of generating functions that describe the action of a group G on colorings of a set S by a set T when we know the action of G on S. Pólya’s work on the subject is very accessible in its exposition, and so the subject has become popularly known as Pólya theory, though Pólya-Redfield theory would be a better name. In this section we develop the elements of this theory. Figure 6.7: A graph on six vertices.

The idea of coloring a set S has many applications. For example, the set S might be the positions in a hydrocarbon molecule which are occupied by hydrogen, and the group could be the group of spatial symmetries of the molecule (that is, the group of permutations of the atoms of the molecule that move the molecule around so that in its final position the molecule cannot be distinguished from the original molecule). The colors could then be radicals (including hydrogen itself) that we could substitute for each hydrogen position in the molecule. Then the number of orbits of colorings is the number of chemically different compounds we could create by using these substitutions.6

In Figure 6.8 we show two different ways to substitute the OH radical for a hydrogen atom in the chemical diagram we gave for butane in Chapter 2. We have colored one vertex of degree 1 with the radical OH and the rest with the atom H. There are only two distinct ways to do this, as the OH must either connect to an “end” C or a “middle” C. This shows that there are two different forms, called isomers of the compound shown. This compound is known as butyl alcohol. Figure 6.8: The two different isomers of butyl alcohol.

Note

6There is a fascinating subtle issue of what makes two molecules different. For example, suppose we have a molecule in the form of a cube, with one atom at each vertex. If we interchange the top and bottom faces of the cube, each atom is still connected to exactly the same atoms as before. However, we cannot achieve this permutation of the vertices by a member of the rotation group of the cube. It could well be that the two versions of the molecule interact with other molecules in different ways, in which case we would consider them chemically different. On the other hand, if the two versions interact with other molecules in the same way, we would have no reason to consider them chemically different. This kind of symmetry is an example of what is called chirality in chemistry.

So think intuitively about some “figure” that has places to be colored. (Think of the faces of a cube, the beads on a necklace, circles at the vertices of an n-gon, etc.) How can we picture the coloring? If we number the places to be colored, say 1 to n, then we have a standard way to represent our coloring. For example, if our colors are blue, green and red, then $$BBGRRGBG$$ describes a typical coloring of 8 such places. Unless the places are somehow “naturally” numbered, this idea of a coloring imposes structure that is not really there. Even if the structure is there, visualizing our colorings in this way doesn’t “pull together” any common features of different colorings; we are simply visualizing all possible colorings. We have a group (think of it as symmetries of the figure you are imagining) that acts on the places. That group then acts in a natural way on the colorings of the places and we are interested in orbits of the colorings. Thus we want a picture that pulls together the common features of the colorings in an orbit. One way to pull together similarities of colorings would be to let the letters we are using as pictures of colors commute as we did with our pictures in Chapter 4; then our picture $$BBGRRGBG$$ becomes $$B^3G^3R^2$$, so our picture now records simply how many times we use each color. Think about how we defined the action of a group on the colorings of a set on which the group acts. You will see that acting with a group element won’t change how many times each color is used; it simply moves colors to different places. Thus the picture we now have of a given coloring is an equally appropriate picture for each coloring in an orbit. One natural question for us to ask is “How many orbits have a given picture?”

Exercise 310

Suppose we draw identical circles at the vertices of a regular hexagon. Suppose we color these circles with two colors, red and blue.

1. In how many ways may we color the set {1, 2, 3, 4, 5, 6} using the colors red and blue?
2. These colorings are partitioned into orbits by the action of the rotation group on the hexagon. Using our standard notation, write down all these orbits and observe how many orbits have each picture, assuming the picture of a coloring is the product of commuting variables representing the colors.
3. Using the picture function of the previous part, write down the picture enumerator for the orbits of colorings of the vertices of a hexagon under the action of the rotation group.

In Problem 310c we saw a picture enumerator for pictures of orbits of the action of a group on colorings. As above, we ask how many orbits of the colorings have any given picture. We can think of a multivariable generating function in which the letters we use to picture individual colors are the variables, and the coefficient of a picture is the number of orbits with that picture. Such a generating function provides an answer to our natural question, and so it is this sort of generating function we will seek. Since the CFB theorem was our primary tool for saying how many orbits we have, it makes sense to think about whether the CFB theorem has an analog in terms of pictures of orbits.

## 6.3.1 The Orbit-Fixed Point Theorem

Orbit-Fixed Point Theorem

Suppose now we have a group G acting on a set and we have a picture function on that set with the additional feature that for each orbit of the group, all its elements have the same picture. In this circumstance we define the picture of an orbit or multiorbit to be the picture of any one of its members. The orbit enumerator Orb(G, S) is the sum of the pictures of the orbits. (Note that this is the same as the sum of the pictures of the multiorbits.) The fixed point enumerator Fix(G, S) is the sum of the pictures of each of the fixed points of each of the elements of G. We are going to construct a generating function analog of the CFB theorem. The main idea of the proof of the CFB theorem was to try to compute in two different ways the number of elements (i.e. the sum of all the multiplicities of the elements) in the union of all the multiorbits of a group acting on a set. Suppose instead we try to compute the sum of all the pictures of all the elements in the union of the multiorbits of a group acting on a set. By thinking about how this sum relates to Orb(G, S) and Fix(G, S), find an analog of the CFB theorem that relates these two enumerators. State and prove this theorem.

We will call the theorem of Problem 311 the Orbit-Fixed Point Theorem. In order to apply the Orbit-Fixed Point Theorem, we need some basic facts about picture enumerators.

Exercise 312

Suppose that P1 and P2 are picture functions on sets S1 and S2 in the sense of Section 4.1.2. Define P on S1 × S2 by P(x1, x2) = P1(x1)P2(x2). How are EP1 , EP1 , and EP related? (You may have already done this problem in another context!)

Exercise 313

Suppose Pi is a picture function on a set Si for i = 1, . . . , k. We define the picture of a k-tuple (x1, x2, . . . , xk) to be the product of the pictures of its elements, i.e. Pb((x1, x2, . . . xk)) = Y k i=1 Pi(xi). How does the picture enumerator EPb of the set S1 × S2 × · · · × Sk of all k-tuples with xi ∈ Si relate to the picture enumerators of the sets Si? In the special case that Si = S for all i and Pi = P for all i, what is EPb (S k )?

Exercise

•314. Use the Orbit-Fixed Point Theorem to determine the Orbit Enumerator for the colorings, with two colors (red and blue), of six circles placed at the vertices of a hexagon which is free to move in the plane. Compare the coefficients of the resulting polynomial with the various orbits you found in Problem 310. 315. Find the generating function (in variables R, B) for colorings of the faces of a cube with two colors (red and blue). What does the generating function tell you about the number of ways to color the cube (up to spatial movement) with various combinations of the two colors?

## 6.3.2 The Pólya-Redfield Theorem

Pólya’s (and Redfield’s) famed enumeration theorem deals with situations such as those in Problems 314 and 315 in which we want a generating function for the set of all colorings a set S using a set T of colors, where the picture of a coloring is the product of the multiset of colors it uses. We are again thinking of the colors as variables. The point of the next series of problems is to analyze the solutions to Problems 314 and 315 in order to see what Pólya and Redfield saw (though they didn’t see it in this notation or using this terminology).

Exercise 316.

In Problem 314 we have four kinds of group elements: the identity (which fixes every coloring), the rotations through 60 or 300 degrees, the rotations through 120 and 240 degrees, and the rotation through 180 degrees. The fixed point enumerator for the rotation group acting on the colorings of the hexagon is by definition the sum of the fixed point enumerators of colorings fixed by the identity, of colorings fixed by 60 or 300 degree rotations, of colorings fixed by 120 or 240 degree rotations, and of colorings fixed by the 180 degree rotation. To the extent that you haven’t already done it in an earlier problem, write down each of these enumerators (one for each kind of permutation) individually and factor each one (over the integers) as completely as you can. 317. In Problem 315 we have five different kinds of group elements. For each kind of element, to the extent that you haven’t already done it in an earlier problem, write down the fixed point enumerator for the elements of that kind. Factor the enumerators as completely as you can.

Exercise 318

In Problem 316, each “kind” of group element has a “kind” of cycle structure. For example, a rotation through 180 degrees has three cycles of size two. What kind of cycle decomposition does a rotation through 60 or 300 degrees have? What kind of cycle decomposition does a rotation through 120 or 240 degrees have? Discuss the relationship between the cycle structures and the factored enumerators of fixed points of the permutations in Problem 316. Recall that we said that a group of permutations acts on a set S if, for each member σ of G there is a permutation σ of S such that σ ◦ ϕ = σ ◦ ϕ for all members σ and ϕ of G. Since σ is a permutation of S, σ has a cycle decomposition as a permutation of S (as well as whatever its cycle decomposition is in the original permutation group G).

Exercise 319

In Problem 317, each “kind” of group element has a “kind” of cycle decomposition in the action of the rotation group of the cube on the faces of the cube. For example, a rotation of the cube through 180 degrees around a vertical axis through the centers of the top and bottom faces has two cycles of size two and two cycles of size one.

To the extent that you haven’t already done it in an earlier problem, answer the following questions. How many such rotations does the group have? What are the other “kinds” of group elements, and what are their cycle structures? Discuss the relationship between the cycle decomposition and the factored enumerator in Problem 317. •320. The usual way of describing the Pólya-Redfield enumeration theorem involves the “cycle indicator” or “cycle index” of a group acting on a set. Suppose we have a group G acting on a finite set S. Since each group element σ gives us a permutation σ of S, as such it has a decomposition into disjoint cycles as a permutation of S. Suppose σ has c1 cycles of size 1, c2 cycles of size 2, ..., cn cycles of size n. Then the cycle monomial of σ is z(σ) = z c1 1 z c2 2 · · · z cn n . The cycle indicator or cycle index of G acting on S is Z(G, S) = 1 |G| X σ:σ∈G z(σ). •(a) What is the cycle index for the group D6 acting on the vertices of a hexagon? (b) What is the cycle index for the group of rotations of the cube acting on the faces of the cube?

Exercise 312: enumeration theorem

How can you compute the Orbit Enumerator of G acting on colorings of S by a finite set T of colors from the cycle index of G acting on S? (Use t, thought of as a variable, as the picture of an element t of T.) State and prove the relevant theorem! This is Pólya’s and Redfield’s famous enumeration theorem.

Exercise 322

Suppose we make a necklace by stringing 12 pieces of brightly colored plastic tubing onto a string and fastening the ends of the string together. We have ample supplies of blue, green, red, and yellow tubing available. Give a generating function in which the coefficient of BiGjRkY h is the number of necklaces we can make with i blues, j greens, k reds, and h yellows. How many terms would this generating function have if you expanded it in terms of powers of B, G, R, and Y ? Does it make sense to do this expansion? How many of these necklaces have 3 blues, 3 greens, 2 reds, and 4 yellows?

Exercise 323.

What should we substitute for the variables representing colors in the orbit enumerator of G acting on the set of colorings of S by a set T of colors in order to compute the total number of orbits of G acting on the set of colorings? What should we substitute into the variables in the cycle index of a group G acting on a set S in order to compute the total number of orbits of G acting on the colorings of S by a set T? Find the number of ways to color the faces of a cube with four colors.

324. We have red, green, and blue sticks all of the same length, with a dozen sticks of each color. We are going to make the skeleton of a cube by taking eight identical lumps of modeling clay and pushing three sticks into each lump so that the lumps become the vertices of the cube. (Clearly we won’t need all the sticks!) In how many different ways could we make our cube? How many cubes have four edges of each color? How many have two red, four green, and six blue edges?

325. How many cubes can we make in Problem 324 if the lumps of modeling clay can be any of four colors? Figure 6.9: A possible computer network. 1 2 3 5 4 6

Exercise ∗326

In Figure 6.9 we see a graph with six vertices. Suppose we have three different kinds of computers that can be placed at the six vertices of the graph to form a network. In how many different ways may the computers be placed? (Two graphs are not different if we can redraw one of the graphs so that it is identical to the other one.) This is equivalent to permuting the vertices in some way so that when we apply the permutation to the endpoints of the edges to get a new edge set, the new edge set is equal to the old one. Such a permutation is called an automorphism of the graph. Then two computer placements are the same if there is an automorphism of the graph that carries one to the other. Online hint. A second online hint.

Exercise 327

Two simple graphs on the set [n] = {1, 2, . . . , n} with edge sets E and E0 (which we think of as sets of two-element sets for this problem) are said to be isomorphic if there is a permutation σ of [n] which, in its action of two-element sets, carries E to E0 . We say two graphs are different if they are not isomorphic. Thus the number of different graphs is the number of orbits of the set of all sets of two-element subsets of [n] under the action of the group Sn. We can represent an edge set by its characteristic function (as in problem 33). That is, we define χE({u, v}) = ( 1 if {u, v} ∈ E 0 otherwise. Thus we can think of the set of graphs as a set of colorings with colors 0 and 1 of the set of all two-element subsets of [n]. The number of different graphs with vertex set [n] is thus the number of orbits of this set of colorings under the action of the symmetric group Sn on the set of two-element subsets of [n]. Use this to find the number of different graphs on five vertices. Online hint.

## 6.4: Supplementary Problems

1. Show that a function from S to T has an inverse (defined on T) if and only if it is a bijection.

2. How many elements are in the dihedral group D3? The symmetric group S3? What can you conclude about D3 and S3?

3. A tetrahedron is a three-dimensional geometric figure with four vertices, six edges, and four triangular faces. Suppose we start with a tetrahedron in space and consider the set of all permutations of the vertices of the tetrahedron that correspond to moving the tetrahedron in space and returning it to its original location, perhaps with the vertices in different places.

1. Explain why these permutations form a group.
2. What is the size of this group?
3. Write down in two row notation a permutation that is not in this group.

4. Find a three-element subgroup of the group S3. Can you find a different three-element subgroup of S3? 5. Prove true or demonstrate false with a counterexample: “In a permutation group, (σϕ) n = σ nϕ n .” 6. If a group G acts on a set S, and if σ(x) = y, is there anything interesting we can say about the subgroups Fix(x) and Fix(y)? 7. (a) If a group G acts on a set S, does σ(f) = f ◦ σ define a group action on the functions from S to a set T? Why or why not? (b) If a group G acts on a set S, does σ(f) = f ◦ σ −1 define a group action on the functions from S to a set T? Why or why not? (c) Is either of the possible group actions essentially the same as the action we described on colorings of a set, or is that an entirely different action? 8. Find the number of ways to color the faces of a tetrahedron with two colors. 9. Find the number of ways to color the faces of a tetrahedron with four colors so that each color is used. 10. Find the cycle index of the group of spatial symmetries of the tetrahedron acting on the vertices. Find the cycle index for the same group acting on the faces. 11. Find the generating function for the number of ways to color the faces of the tetrahedron with red, blue, green and yellow. 12. Find the generating function for the number of ways to color the faces of a cube with four colors so that all four colors are used. 13. How many different graphs are there on six vertices with seven edges? 14. Show that if H is a subgroup of the group G, then H acts on G by σ(τ ) = σ ◦ τ for all σ in H and τ in G. What is the size of an orbit of this action? How does the size of a subgroup of a group relate to the size of the group?