Skip to main content

Section 13.3 Burnside's Counting Theorem

Suppose that we wish to color the vertices of a square with two different colors, say black and white. We might suspect that there would be \(2^4=16\) different colorings. However, some of these colorings are equivalent. If we color the first vertex black and the remaining vertices white, it is the same as coloring the second vertex black and the remaining ones white since we could obtain the second coloring simply by rotating the square \(90^\circ\) (Figure 13.17).

Figure 13.17. Equivalent colorings of square

Burnside's Counting Theorem offers a method of computing the number of distinguishable ways in which something can be done. In addition to its geometric applications, the theorem has interesting applications to areas in switching theory and chemistry. The proof of Burnside's Counting Theorem depends on the following lemma.

Proof.

Let \(G\) act on \(X\) by \((g,x) \mapsto g \cdot x\text{.}\) Since \(x \sim y\text{,}\) there exists a \(g \in G\) such that \(g \cdot x=y\text{.}\) Let \(a \in G_x\text{.}\) Since

\begin{equation*} gag^{-1} \cdot y = ga \cdot g^{-1}y = ga \cdot x = g \cdot x = y\text{,} \end{equation*}

we can define a map \(\phi: G_x \rightarrow G_y\) by \(\phi(a) = gag^{-1}\text{.}\) The map \(\phi\) is a homomorphism since

\begin{equation*} \phi(ab) = gabg^{-1} = gag^{-1} gbg^{-1} = \phi(a) \phi(b)\text{.} \end{equation*}

Suppose that \(\phi(a) = \phi(b)\text{.}\) Then \(gag^{-1}= gbg^{-1}\) or \(a=b\text{;}\) hence, the map is injective. To show that \(\phi\) is onto, let \(b\) be in \(G_y\text{;}\) then \(g^{-1}bg\) is in \(G_x\) since

\begin{equation*} g^{-1}bg \cdot x = g^{-1}b \cdot gx = g^{-1}b \cdot y = g^{-1} \cdot y = x; \end{equation*}

and \(\phi(g^{-1}bg ) = b\text{.}\)

Proof.

We look at all the fixed points \(x\) of all the elements in \(g \in G\text{;}\) that is, we look at all \(g\)'s and all \(x\)'s such that \(gx =x\text{.}\) If viewed in terms of fixed point sets, the number of all \(g\)'s fixing \(x\)'s is

\begin{equation*} \sum_{g \in G} |X_g|\text{.} \end{equation*}

However, if viewed in terms of the stabilizer subgroups, this number is

\begin{equation*} \sum_{x \in X} |G_x|; \end{equation*}

hence, \(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\text{.}\) By Lemma 13.18,

\begin{equation*} \sum_{y \in {\mathcal O}_x} |G_y| = | {\mathcal O}_x| \cdot |G_x|\text{.} \end{equation*}

By Theorem 13.11 and Lagrange's Theorem, this expression is equal to \(|G|\text{.}\) Summing over all of the \(k\) distinct orbits, we conclude that

\begin{equation*} \sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = k \cdot |G|\text{.} \end{equation*}
Example 13.20.

Let \(X = \{1, 2, 3, 4, 5 \}\) and suppose that \(G\) is the permutation group \(G= \{(1), (1 3), (1 3)(2 5), (2 5) \}\text{.}\) The orbits of \(X\) are \(\{1, 3\}\text{,}\) \(\{2, 5\}\text{,}\) and \(\{4\}\text{.}\) The fixed point sets are

\begin{align*} X_{(1)} & = X\\ X_{(1 3)} & = \{2, 4, 5 \}\\ X_{(1 3)(2 5)} & = \{4\}\\ X_{(2 5)} & = \{1, 3, 4 \}\text{.} \end{align*}

Burnside's Theorem says that

\begin{equation*} k = \frac{1}{|G|} \sum_{g \in G} |X_g| = \frac{1}{4}(5 + 3 + 1 + 3) = 3\text{.} \end{equation*}

Subsection 13.3.1 A Geometric Example

Before we apply Burnside's Theorem to switching-theory problems, let us examine the number of ways in which the vertices of a square can be colored black or white. Notice that we can sometimes obtain equivalent colorings by simply applying a rigid motion to the square. For instance, as we have pointed out, if we color one of the vertices black and the remaining three white, it does not matter which vertex was colored black since a rotation will give an equivalent coloring.

The symmetry group of a square, \(D_4\text{,}\) is given by the following permutations:

\begin{align*} &(1) & &(13) & & (24) & & (1432)\\ &(1234) & &(12)(34) & & (14)(23) & & (13)(24) \end{align*}

The group \(G\) acts on the set of vertices \(\{ 1, 2, 3, 4\}\) in the usual manner. We can describe the different colorings by mappings from \(X\) into \(Y = \{ B, W \}\) where \(B\) and \(W\) represent the colors black and white, respectively. Each map \(f : X \rightarrow Y\) describes a way to color the corners of the square. Every \(\sigma \in D_4\) induces a permutation \(\widetilde{ \sigma }\) of the possible colorings given by \(\widetilde{\sigma}(f) = f \circ \sigma\) for \(f : X \rightarrow Y\text{.}\) For example, suppose that \(f\) is defined by

\begin{align*} f(1) & = B\\ f(2) & = W\\ f(3) & = W\\ f(4) & = W \end{align*}

and \(\sigma = (1 2)(3 4)\text{.}\) Then \(\widetilde{\sigma}(f) = f \circ \sigma\) sends vertex \(2\) to \(B\) and the remaining vertices to \(W\text{.}\) The set of all such \(\widetilde{\sigma}\) is a permutation group \(\widetilde{G}\) on the set of possible colorings. Let \(\widetilde{X}\) denote the set of all possible colorings; that is, \(\widetilde{X}\) is the set of all possible maps from \(X\) to \(Y\text{.}\) Now we must compute the number of \(\widetilde{G}\)-equivalence classes.

  1. \(\widetilde{X}_{(1)} = \widetilde{X}\) since the identity fixes every possible coloring. \(|\widetilde{X}| = 2^4 =~16\text{.}\)

  2. \(\widetilde{X}_{(1 2 3 4)}\) consists of all \(f \in \widetilde{X}\) such that \(f\) is unchanged by the permutation \((1 23 4)\text{.}\) In this case \(f(1) = f(2) = f(3) = f(4)\text{,}\) so that all values of \(f\) must be the same; that is, either \(f(x)= B\) or \(f(x)= W\) for every vertex \(x\) of the square. So \(|\widetilde{X}_{(1 2 3 4)}| = 2\text{.}\)

  3. \(|\widetilde{X}_{(1 4 3 2)}| = 2\text{.}\)

  4. For \(\widetilde{X}_{(1 3)(2 4)}\text{,}\) \(f(1) = f(3)\) and \(f(2) = f(4)\text{.}\) Thus, \(|\widetilde{X}_{(13)(24)}| = 2^2 = 4\text{.}\)

  5. \(|\widetilde{X}_{(1 2)(3 4)}| = 4\text{.}\)

  6. \(|\widetilde{X}_{(1 4)(2 3)}| = 4\text{.}\)

  7. For \(\widetilde{X}_{(1 3 )}\text{,}\) \(f(1) = f(3)\) and the other corners can be of any color; hence, \(|\widetilde{X}_{(1 3)}| = 2^3 = 8\text{.}\)

  8. \(|\widetilde{X}_{(2 4)}| = 8\text{.}\)

By Burnside's Theorem, we can conclude that there are exactly

\begin{equation*} \frac{1}{8} ( 2^4 + 2^1 + 2^2 + 2^1 + 2^2 + 2^2 +2^3 + 2^3) = 6 \end{equation*}

ways to color the vertices of the square.

Proof.

Let \(\sigma \in G\) and \(f \in \widetilde{X}\text{.}\) Clearly, \(f \circ \sigma\) is also in \(\widetilde{X}\text{.}\) Suppose that \(g\) is another function from \(X\) to \(Y\) such that \(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\text{.}\) Then for each \(x \in X\text{,}\)

\begin{equation*} f( \sigma(x )) = \widetilde{\sigma}(f)(x) = \widetilde{\sigma}(g)(x) = g( \sigma(x ))\text{.} \end{equation*}

Since \(\sigma\) is a permutation of \(X\text{,}\) every element \(x'\) in \(X\) is the image of some \(x\) in \(X\) under \(\sigma\text{;}\) hence, \(f\) and \(g\) agree on all elements of \(X\text{.}\) Therefore, \(f=g\) and \(\widetilde{\sigma}\) is injective. The map \(\sigma \mapsto \widetilde{\sigma}\) is onto, since the two sets are the same size.

Suppose that \(\sigma\) is a permutation of \(X\) with cycle decomposition \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\text{.}\) Any \(f\) in \({\widetilde{X}}_{\sigma}\) must have the same value on each cycle of \(\sigma\text{.}\) Since there are \(n\) cycles and \(|Y|\) possible values for each cycle, \(|{\widetilde{X}}_{\sigma}| = |Y|^n\text{.}\)

Example 13.22.

Let \(X = \{1, 2, \ldots, 7\}\) and suppose that \(Y = \{ A, B, C \}\text{.}\) If \(g\) is the permutation of \(X\) given by \((1 3)(2 4 5) = (1 3)(2 4 5)(6)(7)\text{,}\) then \(n = 4\text{.}\) Any \(f \in \widetilde{X}_g\) must have the same value on each cycle in \(g\text{.}\) There are \(|Y|=3\) such choices for any value, so \(|\widetilde{X}_g| = 3^4 = 81\text{.}\)

Example 13.23.

Suppose that we wish to color the vertices of a square using four different colors. By Proposition 13.21, we can immediately decide that there are

\begin{equation*} \frac{1}{8} (4^4 + 4^1 + 4^2 + 4^1 + 4^2 + 4^ 2 + 4^3 + 4^3) = 55 \end{equation*}

possible ways.

Subsection 13.3.2 Historical Note

William Burnside was born in London in 1852. He attended Cambridge University from 1871 to 1875 and won the Smith's Prize in his last year. After his graduation he lectured at Cambridge. He was made a member of the Royal Society in 1893. Burnside wrote approximately 150 papers on topics in applied mathematics, differential geometry, and probability, but his most famous contributions were in group theory. Several of Burnside's conjectures have stimulated research to this day. One such conjecture was that every group of odd order is solvable; that is, for a group \(G\) of odd order, there exists a sequence of subgroups

\begin{equation*} G = H_n \supset H_{n-1} \supset \cdots \supset H_1 \supset H_0 = \{ e \} \end{equation*}

such that \(H_i\) is normal in \(H_{i+1}\) and \(H_{i+1} / H_i\) is abelian. This conjecture was finally proven by W. Feit and J. Thompson in 1963. Burnside's The Theory of Groups of Finite Order, published in 1897, was one of the first books to treat groups in a modern context as opposed to permutation groups. The second edition, published in 1911, is still a classic.

Exercises 13.3.3 Collected Homework

1.

Let \(X = \{1,2,3,4,5\}\) and let \(G = \{(1), (123), (132), (45), (123)(45), (132)(45)\}\text{.}\) Let \(G\) act on \(X\) in the obvious way.

  1. For each \(x \in X\) and \(g \in G\text{,}\) find \(\mathcal O_x\text{,}\) \(G_x\text{,}\) and \(X_g\text{.}\) Label these clearly.

  2. Verify the orbit-stabilizer theorem and Burnside's lemma for this example and explain (i.e., demonstrate that you know what these are and mean).

  3. To thank your professors for doing such an amazing job all semester, you decide to bake 6 pies. You will give 3 to your favorite abstract algebra professor, 2 to your next favorite professor, and 1 to your third favorite. You know how to make 4 different types of pies. How man different pie-to-professor combinations can you create? Use Burnside's lemma to explain how this relates to the \(X\) and \(G\) in this problem.

2.

You want to make friendship bracelets for all your friends. Each will consist of 10 beads. You have access to an unlimited supply of four different colors of beads. However, you require that no two bracelets can be identical (since each of your friends is unique). How many friends could you have and still be able to accomplish this?

Hint

You will want to use the group \(D_{10}\) that contains 20 elements (10 rotations and 10 reflections).