Pólya Enumeration

Prerequisites: Permutations and arrangements

Introduction

The Pólya enumeration theorem is usually used to solve counting problems involving “essentially different” objects.

This article may involve group theory

This article may involve group theory. It gives brief explanations of the group-theoretic concepts it uses, so that readers unfamiliar with them can understand and apply the Pólya enumeration theorem. For rigorous statements and discussions of group theory, see the sections on basic concepts of abstract algebra, group theory, and others.

“Symmetry groups”, “symmetric groups”, and “permutation groups”

This article inevitably uses the names of all three kinds of groups. Although they may be easy to confuse, they refer to different concepts. Given a geometric structure, its symmetry operations are the geometric transformations that make it coincide with itself, and its symmetry group is the set of those operations. The symmetric group is the set of all permutations of a given set. A permutation group is a subgroup of a symmetric group, consisting of some, not necessarily all, permutations. Later we explain how to represent the symmetry group of a given geometric structure as a permutation group and use it in counting problems.

Burnside's lemma

Related reading: Burnside's lemma

The Pólya enumeration theorem is an application and generalization of Burnside's lemma. Before introducing it, we briefly review Burnside's lemma.

To extract the general pattern, first consider a simple example.

Necklace coloring

We have a necklace of four beads. Each bead can be red or blue. How many essentially different bead colorings are there? (Two colorings are considered the same if one can be rotated to coincide with the other.)

Solution and analysis

This problem is simple enough to solve by enumeration. There are $4$ beads, each with $2$ possible colors, so there are $2^4=16$ possible necklace colorings. Group together colorings obtainable from one another by rotation; there are $6$ groups, as shown below. (The code for an individual coloring records the colors clockwise starting from the lower-left bead, with $B$ for blue and $R$ for red; colorings in the same group have the same background color.)

This example shows that to count essentially different colorings, the key is to know how many distinct colorings correspond to each equivalence class. In other words, we need to determine the size of every group in the figure.

Colorings in the same group are precisely those that can be transformed into one another by rotations. There are $4$ rotations, namely

$$G=\{r_0,r_1,r_2,r_3\},$$

representing rotations $0,1,2,3$ respectively. A rotation by $0$ leaves the necklace unchanged.

First consider the group containing $RRBB$. Applying these four operations gives

$$RRBB, RBBR, BBRR, BRRB.$$

The four colorings are distinct, so this group has $4$ elements.

Now consider the group containing $BRBR$. Applying the same four operations gives

$$BRBR, RBRB, BRBR, RBRB.$$

The result of rotating twice is the same as not rotating, and the result of rotating three times is the same as rotating once. Therefore this group has $2$ elements.

Finally, consider the groups containing $BBBB$ and $RRRR$. All four operations give each of them back unchanged, so each group has only $1$ element.

Let $x$ denote a coloring, and let $Gx$ denote the set of color codes obtainable by applying operations to $x$. The example suggests that the action of $G$ on $x$ has a kind of “periodicity”.

Let $|G|$ be the total number of operations. This “periodicity” means that if $m$ distinct operations in $G$ transform $x$ into itself, then the results for $x$ under these operations repeat $m$ times. Thus, for $x$, there are $|G|/m$ distinct results, which is the size of the group containing $x$.

In this example, only the zero rotation $r_0$ fixes $RRBB$, so its group has size $4/1=4$; both $r_0$ and the two-step rotation $r_2$ fix $BRBR$, so its group has size $4/2=2$; every rotation fixes $BBBB$, so its group has size $4/4=1$.

Below, let $G_x$ denote the number of operations that transform $x$ into itself, so $|G_x|$ is the $m$ above. The size of the group containing $X$ is $|G|/|G_x|$. To count the groups of colorings, enumerate all possible colorings $x\in X$; for a coloring with group size $|Gx|$, denoted $x$, assign the weight $1/|Gx|$. Then the number of groups is

$$|X/G|=\sum_{x\in X}\frac{1}{|Gx|}=\sum_{x\in X}\frac{|G_x|}{|G|}.$$

The form of this expression is not convenient to use. Let $gx$ be the result of applying an operation to a coloring $x\in X$ using $g\in G$. Then the set $G_x$ described above is $\{g\in G:gx=x\}$, so exchanging the order of summation gives

$$\begin{aligned} \sum_{x\in X}|G_x| &=\sum_{x\in X}|\{g\in G:gx=x\}|\\ &=\sum_{x\in X}\sum_{g\in G}[gx=x]\\ &=\sum_{g\in G}\sum_{x\in X}[gx=x]\\ &=\sum_{g\in G}|\{x\in X:gx=x\}|\\ &=\sum_{g\in G}|X^g|. \end{aligned}$$

Here $[\cdot]$ is the Iverson bracket. In the result after exchanging the sums, $X^g=\{x\in X:gx=x\}$ is the set of colorings that, under operation $g$, remain unchanged, with such a coloring denoted $x$; in short, it is the set of fixed points of $g$.

We can now write the number of groups as

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.$$

In other words, the number of groups is the average number of fixed points of the rotations.

As an application of this result, recompute the number of necklace colorings. The fixed points of the rotations are:

Operation	Fixed points
$r_0$	$X$
$r_1$	$\{BBBB,RRRR\}$
$r_2$	$\{BBBB,BRBR,RBRB,RRRR\}$
$r_3$	$\{BBBB,RRRR\}$

Therefore, the number of groups is

$$\frac{16+2+4+2}{4} = 6.$$

This recovers the result above.

The example suggests the following general result for solving such counting problems. For convenience, we focus on coloring problems here, though the result also applies to other situations; examples appear at the end.

A coloring problem starts with a structure and colors each of its vertices, producing different colorings. The structure has symmetries, so colorings that appear different can be transformed into one another by symmetry operations. Such colorings are called essentially the same. The problem is to determine the number of essentially different colorings.

Following the analysis of the example, first determine the symmetry operations of the given structure. The set of these operations, $G$, is called the spatial symmetry group of the structure. In practice, it is usually unnecessary to know the definition of a group; it is enough to enumerate all spatial symmetry operations without omission or duplication. The structures of several common spatial symmetry groups are analyzed later, where the definition of a group is explained.

Let the set of all colorings be $X$, and let an individual coloring be $x$. The result of applying operation $g\in G$ to a coloring $x\in X$ is $gx$. Thus all results obtainable by applying an operation to $x$ form $Gx=\{gx:g\in G\}$, which is called the orbit of group $G$ acting on $x$. Different colorings in the same orbit are what “essentially the same” means in these problems. Therefore, the number of essentially different colorings is equal to the number of distinct orbits.

The analysis of the example generalizes to the general case.

Burnside's lemma

Given an action of a group $G$ on a set $X$, the number of distinct orbits is

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.$$

Here, $X^g=\{x\in X:gx=x\}$ is the set of fixed points under the action of $g\in G$.

Its proof is almost exactly the analysis of the example above. The example used the observation that the results of the action of group $G$ on one element $x$ have a kind of “periodicity”, so the number of repetitions equals the number of operations that transform $x$ into itself. This fact is correct in general, but because the structure of group $G$ may be complicated, its “periodicity” may not be as direct as in the example. A rigorous statement of this fact requires the orbit-stabilizer theorem from group theory.

In applications, it is enough to enumerate all symmetry operations and give the number of fixed points corresponding to each operation. Here is a slightly more complicated application.

Cube coloring

Color a cube with three colors and find the number of essentially different colorings (two colorings that become the same after a spatial rotation are considered identical).

Solution

A cube has $6$ faces, and each face has $3$ coloring choices, so there are $3^6$ colorings in total, that is, $|X|=3^6$. Let the spatial symmetry group of the cube be $G$.

We now analyze all operations in $G$. For convenience, call the six faces front, back, top, bottom, left, and right:

• Identity: Every coloring is fixed, so $|X^g|=3^6$;
• A $90^\circ$ rotation about the line through the centers of two opposite faces: there are $3$ choices of opposite faces and $2$ choices of rotation direction, so this type gives $6$ permutations. If the axis passes through the centers of the front and back faces, the top, bottom, left, and right faces must have the same color for the coloring to remain fixed. There are $3$ independently colored regions, so $|X^g|=3^3$;
• A $180^\circ$ rotation about the line through the centers of two opposite faces: there are $3$ choices of opposite faces, and the rotation direction does not matter, so this type gives $3$ permutations. If the axis passes through the centers of the front and back faces, the top and bottom faces must have the same color, and the left and right faces must have the same color. There are $4$ independently colored regions, so $|X^g|=3^4$;
• A $180^\circ$ rotation about the line through the midpoints of two opposite edges: there are $6$ choices of opposite edges, and the rotation direction again does not affect the permutation, so this type gives $6$ permutations. If the opposite edges are the boundaries of the front/top pair and the bottom/back pair, the front and top faces must have the same color, the bottom and back faces must have the same color, and the left and right faces must have the same color. There are $3$ independently colored regions, so $|X^g|=3^3$;
• A $120^\circ$ rotation about the line through two opposite vertices: there are $4$ choices of opposite vertices and $2$ choices of rotation direction, so this type gives $8$ permutations. If the opposite vertices are the upper-right vertex of the front face and the lower-left vertex of the back face, the front, top, and right faces must have the same color, and the back, bottom, and left faces must have the same color. There are $2$ independently colored regions, so $|X^g|=3^2$.

Therefore, the number of essentially different colorings is

$$\frac{1\times3^6+6\times3^3+3\times3^4+6\times3^3+8\times3^2}{1+6+3+6+8}=57.$$

The Pólya enumeration theorem

The statement of Burnside's lemma does not use the fact that $X$ is the set of all colorings of a structure. In fact, Burnside's lemma is not limited to coloring problems. For coloring problems, the Pólya enumeration theorem provides a more precise calculation. It can be viewed as the application of the general Burnside's lemma to coloring problems.

The improvement over Burnside's lemma is that the Pólya enumeration theorem provides a concrete method for calculating the size $|X^g|$ of the fixed-point set in coloring problems.

This is intuitive from the cube-coloring example. For each symmetry operation of a cube, the size of its fixed-point set has the form $m^{c(g)}$, where $m$ is the number of colors and $c(g)$ is the number of regions that can be colored independently under operation $g$. This observation also holds in general, but we need to make clear how to calculate, for a given $g$, the value $c(g)$.

Choosing a coloring of a structure means, mathematically, choosing a map from the set $X$ of colorable objects in the structure (such as beads in a necklace or faces of a cube) to the set $C$ of colors, namely $f:X\rightarrow C$. Thus the set of colorings is $C^X$. The spatial symmetry group $G$ of the structure acts on the structure and therefore naturally acts on the set $X$ as well. Each such symmetry operation is a bijection on $X$, namely a permutation. ¹

Now analyze the structure of the fixed-point set $(C^X)^g$. Given $g$ as a permutation of $X$, the example shows that if a position in $X$, denoted $x$, can, after finitely many applications of $g$, be moved to a position $y$, then a fixed point $f\in (C^X)^g$ must satisfy $f(x)=f(y)$. In the language of orbits from the previous section, positions $x$ and $y$ lie in the same orbit under the action of $g$², so they must be colored the same. In the language of permutations, for permutation $g$, the cycle decomposition shows that positions $x$ and $y$ lie in the same cycle, so they must be colored the same. Different cycles in the cycle decomposition need not have the same color and can be colored independently. Thus the number of independently colorable regions is $c(g)$, namely the number of cycles in the cycle decomposition of $g$.

It follows that the number of fixed points of operation $g$ is $|C|^{c(g)}$. Substituting this conclusion into Burnside's lemma gives the unweighted version of the Pólya enumeration theorem.

Pólya enumeration theorem (unweighted version)

Given an action of a group $G$ on a set $X$ and a color set $C$, the number of distinct colorings is

$$|C^X/G|=\frac{1}{|G|}\sum_{g\in G}m^{c(g)},$$

where $m$ is the number of colors and $c(g)$ is the number of cycles in the cycle decomposition of the permutation representation of an element $g\in G$.

Meaning of the group $G$

There is a slight abuse of notation here. If group $G$ acts on $X$, the action on the coloring set $C^X$ should be defined separately, but the distinction is omitted here.

As a simple application of the Pólya enumeration theorem, recompute the example from earlier.

Another solution to the necklace-coloring problem

Number the four beads $1\sim 4$. The elements of $G$ in the example have the following permutation representations, all written as cycle decompositions:

• Zero rotations $r_0=(1)$, with $4$ cycles in total (the omitted $1$-cycles should be noted);
• One rotation $r_1=(1234)$, with $1$ cycle;
• Two rotations $r_2=(13)(24)$, with $2$ cycles;
• Three rotations $r_3=(1432)$, with $1$ cycle.

Therefore, the number of essentially different colorings is

$$\frac{2^4+2^1+2^2+2^1}{4}=6.$$

Another solution to the cube-coloring problem

The preceding analysis effectively gave the cycle representations of each type of permutation, although it did not write them explicitly in numerical notation, so we do not repeat that analysis here. We illustrate only the case of a $180^\circ$ rotation about the line joining the midpoints of opposite edges. Number the front, back, top, bottom, left, and right faces $1\sim6$ in that order. The corresponding permutation is $(13)(24)(56)$, so $c(g)=3$. Other types of permutation can be analyzed similarly, and the final counting expression is exactly the same as above.

Weighted generalization

The unweighted Pólya enumeration theorem can count all essentially different coloring problems, but it is insufficient for more detailed questions. For example, if the number of times each available color may be used is specified in the coloring problem above, the Pólya counting formula cannot be applied directly. In practice, this requires deriving the result again using Burnside's lemma; expressing the resulting conclusions as generating functions gives the weighted version of the Pólya enumeration theorem.

Necklace coloring (with restrictions)

We have a necklace of four beads, each of which can be red or blue. Exactly two red beads and two blue beads are available. How many essentially different bead colorings are there? (Two colorings are considered the same if one can be rotated to coincide with the other.)

Solution and analysis

Apply Burnside's lemma. With two red and two blue beads, there are $\dbinom{4}{2}=6$ colorings. The spatial symmetry group $G=\{r_0,r_1,r_2,r_3\}$ consists of rotations by $0\sim3$ steps. Their fixed-point sets are:

• Zero rotations $r_0=(1)$: all $6$ colorings are fixed;
• One rotation $r_1=(1234)$: a fixed point would require all beads to have the same color, so there are no fixed points;
• Two rotations $r_2=(13)(24)$: there are two independently colored regions, both of size $2$. They must be colored red and blue respectively, so the fixed-point set has size $2$;
• Three rotations $r_3=(1432)$: this is the same as one rotation, so there are no fixed points.

Therefore, by Burnside's lemma, the number of essentially different colorings is

$$\frac{6+0+2+0}{4}=2.$$

The example gives the following calculation method. For problems with restrictions on the numbers of different colors, we again color the cycles of each permutation in the spatial symmetry group, but the numbers of colors used must be exactly the specified numbers. Such combinatorial problems usually have no closed-form solution. Except for special cases that can be calculated by combinatorial methods, they need to be solved as a knapsack problem.

Generating functions can provide the answers to these counting problems. Given a permutation $g$, suppose its cycle type is $1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}$, meaning that it has $\alpha_k$ cycles of length $k$. If each cycle can be colored in one of $m$ colors, then the generating function

$$\prod_{k=1}^n\left(\sum_{i=1}^mx_i^k\right)^{\alpha_k}$$

The coefficient of the monomial $x_1^{\beta_1}x_2^{\beta_2}\cdots x_m^{\beta_m}$ is the count in which the $i$-th color is used $\beta_i$ times. The combinatorial meaning of the expression $\sum_{i=1}^mx_i^k$ in parentheses is as follows: for a cycle of length $k$, the number of colorings that use $k$ instances of color $i$ is $1$, while the count is $0$ in all other cases. This exactly describes the requirement that all positions in the same cycle have the same color.

Given the generating function for colorings under a permutation $g$, applying Burnside's lemma to each monomial gives the counts of essentially different colorings for every color combination. Since a generating function is linear in its monomials, the generating function for the number of essentially different colorings is

$$\frac1{|G|}\sum_{g\in G}\prod_{k=1}^n\left(\sum_{i=1}^mx_i^k\right)^{\alpha_k}.$$

Expanding this expression, the coefficient of each monomial gives the number of essentially different colorings for the specified color combination.

In the discussion above, the generating function $\sum_{i=1}^mx_i^k$ for coloring each cycle has no special significance and can be replaced by another generating function. Thus we obtain the following general version of the Pólya enumeration theorem.

Cycle index of a permutation group

Given a permutation group $G$, the cycle index of group $G$ is defined as

$$Z_G(t_1,t_2,\cdots,t_n)=\frac{1}{|G|}\sum_{g\in G}t_1^{c_1(g)}t_2^{c_2(g)}\cdots t_n^{c_n(g)},$$

where $c_k(g)$ is the number of cycles in the cycle decomposition of permutation $g$ that have length $k$; that is, $1^{c_1(g)}2^{c_2(g)}\cdots n^{c_n(g)}$ is the cycle type of permutation $g$.

Pólya enumeration theorem (weighted version)

Given an action of a group $G$ on a set $X$, suppose the generating function for the coloring methods at each point is $f(x_1,x_2,\cdots,x_m)$. Then the generating function for the essentially different colorings of $X$ is

$$Z_G(f(x_1^1,x_2^1,\cdots,x_m^1),f(x_1^2,x_2^2,\cdots,x_m^2),\cdots,f(x_1^n,x_2^n,\cdots,x_m^n)),$$

where $Z_G(t_1,t_2,\cdots,t_n)$ is the cycle index of group $G$.

Here, if the generating function for coloring a single position is $f(x_1,x_2,\cdots,x_m)$, then the generating function for coloring a cycle of length $k$ is $f(x_1^k,x_2^k,\cdots,x_m^k)$. This reflects the fact that if a coloring is a fixed point of a given permutation, all positions in the same cycle must have the same color. Evaluating the generating function at $x_i=1$ gives the unweighted version of the Pólya enumeration theorem above.

The statement of the theorem uses the concept of the cycle index of a permutation group. It is independent of any particular coloring problem and describes the structure of a permutation group.

Another solution to the restricted necklace-coloring problem

The cycle index of the rotation symmetry group is $\dfrac14\left(t_1^4+t_2^2+2t_4\right)$, and the generating function for coloring a single point is $r+b$. Thus the generating function for all colorings is

$$\begin{aligned} F(r,b)&=\frac14\left((r+b)^4+(r^2+b^2)^2+2(r^4+b^4)\right)\\ &=r^4+r^3b+2r^2b^2+rb^3+b^4. \end{aligned}$$

The desired count is the coefficient of $r^2b^2$, namely $2$ essentially different colorings. Incidentally, this expression also gives the counts under other restrictions.

Applications

The weighted version of the Pólya enumeration theorem plays an important role in combinatorial counting problems. Here we briefly discuss its applications; for a more general discussion, see formal methods for combinatorial problems.

Diamond necklace

We have a necklace with four identical beads, and any number of diamonds can be set into each bead. If there are four diamonds, how many essentially different ways are there to set them? (Two settings are considered the same if one can be rotated to coincide with the other.)

Solution and analysis

The spatial symmetry group of the necklace is still the same as above. Without restricting the total number of diamonds, the generating function for the setting at one position is

$$f(x)=1+x+x^2+\cdots=\sum_{i=1}^\infty x^i=\frac{1}{1-x}.$$

Applying the weighted Pólya enumeration theorem, the generating function for all diamond settings is

$$\begin{aligned} F(x)&=\frac14\left(f(x)^4+f(x^2)^2+2f(x^4)\right)\\ &=1+x+3x^2+5x^3+10x^4+\cdots. \end{aligned}$$

Thus the desired number of settings is the coefficient of $x^4$, namely $10$. As a check, enumeration gives

$$4000,3100,3010,3001,2200,2020,2110,2101,2011,1111.$$

Each group of four digits gives the number of diamonds set into each bead.

This example shows that the weighted version of the Pólya enumeration theorem can solve a much broader class of problems than coloring counts. It provides a method for extending the count at a single point to the count of essentially different configurations on an entire structure. Coloring problems are only a special case of this class.

Common spatial symmetry groups

One difficulty in Pólya-counting problems is analyzing the structure of permutation groups. Here we briefly discuss common spatial symmetry groups and describe them using their cycle indices. Note that for the spatial symmetry group of the same structure, different sets of objects being acted on give different group actions, and therefore different permutation representations. For example, the action of the spatial symmetry group of a cube on its vertices, edges, and faces gives the vertex, edge, and face permutation groups of the cube, respectively. The numbers of vertices, edges, and faces differ, so these permutation groups and their corresponding cycle indices naturally differ as well. Thus, when solving a specific problem, the objects on which the group acts must not be overlooked.

Relationship between spatial symmetry groups and permutation groups

Although the two concepts are very similar, they are not the same object. In group-theoretic language, given a spatial symmetry group $G$ and its action on a set $X$, the permutation representation of the action is a homomorphism from group $G$ to the symmetric group $S_X$, denoted $\varphi$. In combinatorial counting, this representation is often faithful, meaning $\ker\varphi=\{e\}$, so the homomorphism $\varphi$ is an embedding of group $G$ into group $S_X$. The permutation group in this article is the image of this embedding, namely $\varphi(G)$, and it is isomorphic to the spatial symmetry group $G$ itself. Therefore, for the spatial symmetry group $G$ of the same structure, different choices of the group action can give different permutation groups $\varphi(G)$ and hence different cycle indices (isomorphic permutation groups need not have the same cycle index).

Given a structure, its spatial symmetry group is the set of all operations that can transform it into itself. It necessarily satisfies the following conditions:

• Applying two symmetry operations successively to a given structure can be viewed as applying another symmetry operation; that is, the set of symmetry operations is closed under composition;
  • composition of symmetry operations is associative;
  • there is an identity symmetry operation; leaving the given structure unchanged is itself regarded as an operation;
  • every operation has an inverse operation that can cancel the effect of the given operation.

Groups are the abstraction of concepts satisfying all these conditions. The study of group structures is the main subject of group theory. The analysis here focuses on spatial symmetry groups and mainly uses geometric viewpoints. The common examples given below should provide readers with general approaches to analyzing such problems.

Cyclic groups

For a regular $n$-gon, the spatial symmetry group formed by all rotations is called the cyclic group (cyclic group), denoted $C_n$. Let the operation of counterclockwise rotation by $(360/n)^\circ$ be $r$. The elements of group $C_n$ can be written as

$$C_n=\{e,r,r^2,\cdots,r^{n-1}\}.$$

Here $r^k$ means applying operation $r$ $k$ times, namely counterclockwise rotation by $(360k/n)^\circ$, while $e=r^0$ is the identity transformation.

Whether we consider the action of the cyclic group on all vertices or all edges of a regular $n$-gon, its permutation representation is the same. Analyze the permutation representation of the action on the set of all vertices as an example. Its cycle index is

$$Z(C_n)=\frac1n\sum_{d\mid n}\varphi(d)t_{d}^{n/d}.$$

Here $\varphi(\cdot)$ is the Euler totient function from number theory.

If we count only rotations, the spatial symmetry group of a necklace of length $n$ is $C_n$.

Analysis

Number the vertices in counterclockwise order as $\{0,1,\cdots,n-1\}$. Then $r^k(i)=i+k\bmod n$. The set of vertices in the cycle containing vertex $i$ is

$$\{i+\ell k\bmod n:\ell\in\mathbf Z\}.$$

Clearly, $i\equiv i+\ell k\pmod n$ if and only if

$$\frac{n}{\gcd(k,n)}\mid\ell.$$

This means that every cycle containing a vertex $i$ has length $\dfrac{n}{\gcd(k,n)}$. Therefore permutation $r^k$ has $\gcd(k,n)$ cycles of equal length. Combining like terms in the cycle-index expression, for a given $d\mid n$, the condition $\gcd(k,n)=n/d$ holds for $k$ values, and their number is $\varphi(d)$; all of them correspond to monomials of the form $t_d^{n/d}$. Thus we obtain the cycle-index expression above.

Dihedral groups

For a regular $n$-gon, the operations consisting of all rotations and reflections across symmetry axes also form a spatial symmetry group, called the dihedral group (dihedral group), denoted $D_{2n}$. Let the operation of counterclockwise rotation by $(360/n)^\circ$ be $r$, and let the operation of reflection across a given symmetry axis (for example, the line from the center to a vertex) be $s$. Then the operations of group $D_{2n}$ can be written as

$$D_{2n}=\{e,r,\cdots,r^{n-1},s,sr,\cdots,sr^{n-1}\}.$$

Here $r^k$ is still a rotation. Although $sr^k$ means first performing $k$ rotations and then reflecting across the given symmetry axis, it can equivalently be viewed as reflection across another symmetry axis. Therefore, group $D_{2n}$ has $1$ identity transformation, $(n-1)$ rotations, and $n$ reflections in total. Its actions on the vertex set and edge set also have the same permutation representation. Its cycle index is

$$Z(D_{2n})=\frac12Z(C_n)+ \begin{cases} \dfrac12t_1t_2^k,&n=2k+1,\\ \dfrac14\left(t_1^2t_2^{k-1}+t_2^k\right),&n=2k. \end{cases}$$

Analysis

The analysis of the rotations in group $D_{2n}$, namely $r^k$ including the identity transformation, is the same as for cyclic group $C_n$. The key is to analyze the remaining reflections, separating the cases according to the parity of the number of vertices $n$.

When $n=2k+1$, every reflection axis connects a vertex to the midpoint of the opposite edge, and there are $n$ such axes. After each reflection, the vertex on the axis remains fixed and all other vertices are exchanged in pairs, giving $1$ fixed point (a $1$-cycle) and $k$ $2$-cycles.

When $n=2k$, there are two types of symmetry axes. Half connect opposite vertices. Reflection across such an axis fixes the two vertices on the axis and exchanges all remaining vertices in pairs, giving $2$ fixed points (two $1$-cycles) and $(k-1)$ $2$-cycles. The other half connect the midpoints of opposite edges. Reflection across such an axis exchanges all vertices in pairs, giving $k$ $2$-cycles.

This analysis gives the cycle-index expression above.

Symmetric groups

The set of all permutations of $n$ elements forms a group called the symmetric group of degree $n$ (symmetric group), denoted $S_n$. It describes all symmetries that these $n$ vertices can have. It is also the permutation representation of the action of these symmetry operations on the vertex set.

According to the analysis in Permutations and arrangements, its cycle index is

$$Z(S_n)=\sum_{a_1+2\alpha_2+\cdots+n\alpha_n=n}\frac{t_1^{\alpha_1}t_2^{\alpha_2}\cdots t_n^{\alpha_n}}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}.$$

The count of permutations with cycle type $1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}$ used here is

$$\frac{n!}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}.$$

It satisfies the recurrence relation

$$Z(S_n)=\frac1n\sum_{k=1}^nt_kZ(S_{n-k}),$$

The starting point of the recurrence is $Z(S_0)=1$. The combinatorial meaning of this recurrence is that, to construct a permutation of length $n$, we can first choose the cycle containing point $n$ and let its length be $k$, and then construct a permutation on the remaining $(n-k)$ vertices.

Given a complete graph with $n$ vertices, its spatial symmetry group is precisely $S_n$. The cycle index of its action on the set of all vertices is given by $Z(S_n)$ above. However, its permutation representation on the set of all edges is different. For example, the sizes of the sets differ: the total number of edges is $n(n-1)/2$. The edge case requires additional analysis. Here we give a simple example; the general case can be found in the exercises.

Counting undirected simple graphs

Count the number of undirected simple graphs with $4$ vertices up to isomorphism.

Solution

This is equivalent to coloring the complete graph with $4$ vertices using two colors and counting essentially different colorings. The spatial symmetry group is $S_4$, and we now analyze the cycle index of its edge permutation group $S_4^{(2)}$.

• Identity ($1$ operation): the edges also remain fixed, so the corresponding monomial is $t_1^6$;
• Swapping two vertices ($6$ operations): suppose $a$ and $b$ are swapped. Edges $1$ and $3$ remain fixed, while edges $2$ and $5$ are exchanged, and edges $4$ and $6$ are exchanged, so the corresponding monomial is $6t_1^2t_2^2$;
• A three-vertex cycle ($8$ operations): suppose the cycle is $(abc)$. The edges $1,2,5$ between these vertices cycle accordingly, and the edges connecting them to the fourth vertex $d$, namely $4,6,3$, also cycle accordingly, so the corresponding monomial is $8t_3^2$;
• Swapping two pairs of vertices ($3$ operations): suppose vertices $a$ and $b$ are swapped, and vertices $c$ and $d$ are swapped. Edges $1$ and $3$ remain fixed, while edges $2$ and $4$ are exchanged, and edges $5$ and $6$ are exchanged, so the corresponding monomial is $3t_1^2t_2^2$;
• A four-vertex cycle ($6$ operations): suppose the cycle is $(abcd)$. The edges $1,2,3,4$ between adjacent vertices cycle accordingly, while the edges $5,6$ between opposite vertices are exchanged, so the corresponding monomial is $6t_2t_4$.

Therefore, the cycle index of the edge permutation group is

$$Z(S_4^{(2)})=\dfrac{1}{24}(t_1^6+9t_1^2t_2^2+8t_3^2+6t_2t_4).$$

By the Pólya enumeration theorem, the number of undirected simple graphs with $4$ vertices up to isomorphism is

$$\frac{2^6+9\times 2^4+8\times 2^2+6\times 2^2}{24} = 11.$$

Polyhedral groups

A polyhedral group is the spatial symmetry group of a regular polyhedron. There are only five regular polyhedra: the regular tetrahedron, cube, regular octahedron, regular dodecahedron, and regular icosahedron. If the adjacency relations among vertices, edges, and faces are preserved while vertices and faces are exchanged, we obtain the dual regular polyhedron. The regular tetrahedron is dual to itself, the cube is dual to the regular octahedron, and the regular dodecahedron is dual to the regular icosahedron. The duality relation simplifies the discussion of their spatial symmetry groups.

Counting only rotations that can be performed in three-dimensional space, there are only three spatial symmetry groups.

• Tetrahedral group, that is, the spatial symmetry group of a regular tetrahedron:

• Identity;

  • Rotations by $120^\circ$ and $240^\circ$ about the line through a vertex and the center of the opposite face;
  • A $180^\circ$ rotation about the line through the midpoints of opposite edges.

There are $1+2\times4+1\times3=12$ symmetry operations in total.

The cycle indices of its corresponding permutation groups are as follows.

• Vertex and face permutation groups: $\dfrac1{12}\left(t_1^4+8t_1t_3+3t_2^2\right)$;

  • Edge permutation group: $\dfrac1{12}\left(t_1^6+8t_3^2+3t_1^2t_2^2\right)$.

• Octahedral group, that is, the spatial symmetry group of the cube (and the regular octahedron):

• Identity;

  • Rotations by $120^\circ$ and $240^\circ$ about the line through opposite vertices;
  • A $180^\circ$ rotation about the line through the midpoints of opposite edges;
  • Rotations by $90^\circ$, $180^\circ$, and $270^\circ$ about the line through the centers of opposite faces.

There are $1+2\times 4+1\times 6+3\times 3=24$ symmetry operations in total.

The cycle indices of the permutation groups of the corresponding cube are as follows.

• Vertex permutation group: $\dfrac{1}{24}\left(t_1^8+8t_1^2t_3^2+9t_2^4+6t_4^2\right)$;
  • Edge permutation group: $\dfrac{1}{24}\left(t_1^{12}+8t_3^4+6t_1^2t_2^5+6t_4^3+3t_2^6\right)$;
  • Face permutation group: $\dfrac{1}{24}\left(t_1^6+8t_3^2+6t_2^3+6t_1^2t_4+3t_1^2t_2^2\right)$.

The permutation groups of the regular octahedron are analogous; only the roles of vertices and faces need to be exchanged.

• Icosahedral group, that is, the spatial symmetry group of the regular dodecahedron (and the regular icosahedron):

• Identity;

  • Rotations by $120^\circ$ and $240^\circ$ about the line through opposite vertices;
  • A $180^\circ$ rotation about the line through the midpoints of opposite edges;
  • Rotations by $72^\circ$, $144^\circ$, $216^\circ$, and $288^\circ$ about the line through the centers of opposite faces.

There are $1+2\times 10+1\times 15+6\times 4=60$ symmetry operations in total.

The cycle indices of the permutation groups of the corresponding regular dodecahedron are as follows.

• Vertex permutation group: $\dfrac{1}{60}\left(t_1^{20}+20t_1^2t_3^6+15t_2^{10}+24t_5^4\right)$;
  • Edge permutation group: $\dfrac{1}{60}\left(t_1^{30}+20t_3^{10}+15t_1^2t_2^{14}+24t_5^6\right)$;
  • Face permutation group: $\dfrac{1}{60}\left(t_1^{12}+20t_3^4+15t_2^6+24t_1^2t_5^2\right)$.

The permutation groups of the regular icosahedron are analogous; only the roles of vertices and faces need to be exchanged.

The cycle indices given here are for permutation groups acting separately on vertices, edges, faces, and other individual types of objects. If different types of objects are to be colored simultaneously, a joint cycle index must be written.

Exercises

Coloring problems

These problems only require analyzing the structure of permutation groups and applying the Pólya enumeration theorem.

• Luogu P4980 Template: Pólya theorem
• Luogu P2561 [AHOI2002] Black and White Tiles
• TRANSP - Transposing is Fun
• TRANSP2 - Transposing is Even More Fun
• Luogu P3307 [SDOI2013] Necklace

When the allowed color combinations are restricted, the number of ways to color the cycles needs to be found using knapsack DP or combinatorial methods.

• Luogu P1446 [HNOI2008] Cards
• UVA10601 Cubes
• Luogu P4916 [MtOI2018] Magic Ring

Graph-counting problems

The Pólya enumeration theorem can be applied to graph-counting problems. The difficulty in these problems lies in enumerating the edge permutation group of a graph.

• SGU 282. Isomorphism
• Luogu P4727 [HNOI2009] Counting graph isomorphisms
• Luogu P4128 [SHOI2006] Colored graph

Another class of graph-counting problems to which the Pólya enumeration theorem applies requires directly manipulating generating functions.

• LOJ 6538 Alkyl counting, enhanced edition, enhanced edition
• LOJ 6512 “Yali Training 2018” Alkane counting
• Luogu P6597 Alkene counting
• Luogu P5818 [JSOI2011] Counting isomers

References and notes

• Pólya enumeration theorem - Wikipedia
• Notes on Pólya's Enumeration Theorem
• Cycle index - Wikipedia

Footnotes

1. Thus the spatial symmetry group $G$ can be represented as a permutation group on $X$, that is, as a subgroup of the symmetric group $S_X$. ↩

2. Strictly speaking, this is the action of the subgroup $\langle g\rangle\le G$. ↩