Skip to main content
Mathematics LibreTexts

6.3: Burnside's Theorem

  • Page ID
    7175
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Burnside's Theorem will allow us to count the orbits, that is, the different colorings, in a variety of problems. We first need some lemmas.

    If \(c\) is a coloring, \([c]\) is the orbit of \(c\), that is, the equivalence class of \(c\). Let \(G(c)\) be the set of permutations in \(G\) that fix \(c\), that is, those \(\phi\) such that \(\phi(c)=c\); the permutation in Figure 6.2.4 fixes the coloring in the bottom row, for example.

    Lemma \(\PageIndex{1}\)

    \(G(c)\) is a group of permutations.

    Proof

    We check the properties of a group from Definition 6.2.1.

    Suppose \(\phi\) and \(\sigma\) both fix \(c\); then \(\phi(\sigma(c))=\phi(c)=c\), so \(\phi\circ\sigma\) fixes \(c\) and \(\phi\circ\sigma\in G(c)\).

    The identity permutation fixes all colorings, so \(\id\in G(c)\).

    If \(\phi(c)=c\) then \(\phi^{-1}(c)=\phi^{-1}(\phi(c))=\id(c)=c\), so \(\phi^{-1}\in G(c)\).

    Lemma \(\PageIndex{2}\)

    \(|G|=|[c]|\cdot|G(c)|\).

    Proof

    For \(\phi\) and \(\sigma\) in \(G\), define \(\phi\sim\sigma\) if \(\sigma^{-1}\circ\phi\in G(c)\). This is an equivalence relation:

    1. \(\sigma^{-1}\circ\sigma\) is the identity function, which is in \(G(c)\). Thus \(\sigma\sim\sigma\), so the relation is reflexive.
    2. If \(\phi\sim\sigma\), \(\sigma^{-1}\circ\phi\in G(c)\). Then \((\sigma^{-1}\circ\phi)^{-1}\in G(c)\), and \((\sigma^{-1}\circ\phi)^{-1}=\phi^{-1}\circ\sigma\in G(c)\), so \(\sigma\sim\phi\) and \(\sim\) is symmetric.
    3. If \(\phi\sim\sigma\) and \(\sigma\sim\tau\), then \(\sigma^{-1}\circ\phi\in G(c)\) and \(\tau^{-1}\circ\sigma\in G(c)\), so \((\tau^{-1}\circ\sigma)\circ(\sigma^{-1}\circ\phi)\in G(c)\). Since \((\tau^{-1}\circ\sigma)\circ(\sigma^{-1}\circ\phi)=\tau^{-1}\circ\phi\), \(\phi\sim\tau\), and \(\sim\) is transitive.

    Now we claim that the equivalence class of \(\phi\) is \(A=\{\phi\circ\sigma\mid\sigma\in G(c)\}\). First, suppose that \(\sigma\in G(c)\); then \(\phi^{-1}\circ\phi\circ\sigma=\sigma\in G(c)\), so \(\phi\circ\sigma\sim\phi\) and \(A\subseteq[\phi]\). Next, suppose \(\phi\sim\tau\), so \(\tau^{-1}\circ\phi=\gamma\in G(c)\). Then \(\phi\circ\gamma^{-1}=\tau\), so \(\tau\in A\) and \([\phi]\subseteq A\).

    Now we show that each equivalence class is the same size as \(G(c)\). Define \(f\colon G(c)\to \{\phi\circ\sigma\mid\sigma\in G(c)\}\) by \(f(\gamma)=\phi\circ\gamma\). If \(f(\gamma_1)=f(\gamma_2)\), then \[\eqalign{ \phi\circ\gamma_1&=\phi\circ\gamma_2\cr \phi^{-1}\circ\phi\circ\gamma_1&=\phi^{-1}\circ\phi\circ\gamma_2\cr \gamma_1&=\gamma_2\cr }\nonumber\] so \(f\) is 1–1. Since every \(\phi\circ\gamma\in\{\phi\circ\sigma\mid\sigma\in G(c)\}\) is \(f(\gamma)\), \(f\) is onto.

    Thus the number of equivalence classes is \(|G|/|G(c)|\).

    Finally, we show that the number of equivalence classes is \(|[c]|\). Let the set of equivalence classes in \(G\) be \(E\), that is, \(E=\{[\phi]\mid \phi\in G\}\). We define \(g\colon [c]\to E\) and show that \(g\) is a bijection. Suppose \(d\in[c]\), so \(d=\sigma(c)\) for some \(\sigma\in G\). Let \(g(d)=[\sigma]\).

    First, we show \(g\) is well-defined. If \(d=\sigma_1(c)=\sigma_2(c)\), then \(\sigma_2^{-1}\circ\sigma_1(c)=c\), so \(\sigma_1\sim\sigma_2\) and \([\sigma_1]=[\sigma_1]\), that is, \(g(\sigma_1)=g(\sigma_2)\).

    Next, suppose \(g(d_1)=g(d_2)\). This means that \(d_1=\sigma_1(c)\), \(d_2=\sigma_2(c)\), and \([\sigma_1]=[\sigma_2]\). Hence \(\sigma_2^{-1}\circ\sigma_1(c)=c\), so \(\sigma_1(c)=\sigma_2(c)\) and thus \(d_1=d_2\), so \(g\) is 1–1.

    Suppose that \([\sigma]\in E\). Then \(g(\sigma(c))=[\sigma]\), so \(g\) is onto.

    Thus we have \[|[c]|=|E|={|G|\over|G(c)|}\nonumber\] and \[|G(c)|\cdot|[c]|=|G|\nonumber\] as desired.

    Corollary \(\PageIndex{1}\)

    If \(c\sim d\) then \(|G(c)|=|G(d)|\).

    Proof

    Since \(c\sim d\), \([c]=[d]\), and \[\eqalign{ {|G|\over|G(c)|} = |[c]|&=|[d]|= {|G|\over|G(c)|}\cr |G(c)|&=|G(d)|\cr }\nonumber \]

    Definition \(\PageIndex{1}\)

    If group \(G\) acts on the colorings of an object and \(\sigma\in G\), \(\text{fix}(\sigma)\) is the set of colorings that are fixed by \(\sigma\).

    Theorem \(\PageIndex{1}\): Burnside's Theorem

    If group \(G\) acts on the colorings of an object, the number of distinct colorings modulo \(G\) is \[{1\over|G|}\sum_{\sigma\in G} |\text{fix}(\sigma)|.\nonumber \]

    Proof

    Let \(C\) be the set of all colorings, and let \(\cal O\) be the set of orbits. Let \(c_1,c_2,\ldots,c_k\) be a list of colorings, one in each orbit, so that the orbits are \([c_1],[c_2],\ldots,[c_k]\). Consider the sum \(\sum_{c\in C}|G(c)|\):

    \[\eqalign{ \sum_{c\in C}|G(c)|&=\sum_{i=1}^k\sum_{c\in[c_i]}|G(c)|\cr &=\sum_{i=1}^k\sum_{c\in[c_i]}|G(c_i)|\cr &=\sum_{i=1}^k\sum_{c\in[c_i]}{|G|\over|[c_i]|}\cr &=\sum_{i=1}^k |[c_i]|{|G|\over|[c_i]|}\cr &=\sum_{i=1}^k |G|=|G|\sum_{i=1}^k 1 = |G||{\cal O}|.\cr }\nonumber\] Then \[|{\cal O}| = {1\over|G|}\sum_{c\in C}|G(c)|.\nonumber \]

    This already gives an interesting formula for \(|{\cal O}|\), but it is unwieldy, since the number of colorings is typically quite large; indeed, since we typically want to compute the number of orbits for \(k\) colors, the number of colorings is not a fixed number.

    With just a little more work we can fix this problem: \[\eqalign{ \sum_{c\in C}|G(c)|&=\sum_{c\in C}\sum_{\sigma\in G(c)} 1\cr &=\sum_{\sigma\in G}\sum_{c\in \text{fix}(\sigma)} 1\cr &=\sum_{\sigma\in G}|\text{fix}(\sigma)|.\cr }\nonumber\] Now \[|{\cal O}| = {1\over|G|}\sum_{\sigma\in G}|\text{fix}(\sigma)|\nonumber\] as desired.

    Since the group of permutations in a typical problem is fairly small, the sum in Burnside's Theorem is usually manageable. Moreover, we can make the task of computing \(|\text{fix}(\sigma)|\) fairly straightforward. Let's consider a particular example, the permutation of Figure 6.2.4, shown again in Figure \(\PageIndex{1}\). If we are using \(k\) colors, how many colorings of the pentagon are fixed by this permutation? Since the permutation swaps vertices 2 and 5, they must be the same color if \(\phi\) is to fix the coloring. Likewise vertices 3 and 4 must be the same color; vertex 1 can be any color. Thus, the number of colorings fixed by \(\phi\) is \(k^3\). It is easy to see that every "flip'' permutation of the pentagon is essentially the same, so for each of the five flip permutations, the size of \(\text{fix}(\sigma)\) is \(k^3\).

    clipboard_e7a93239a8e4051f01bd98f83b6f734b8.png
    Figure \(\PageIndex{1}\): The cycles in a vertex permutation.

    Every permutation can be written in cycle form: The permutation in Figure \(\PageIndex{1}\), for example, is \((1)(2,5)(3,4)\). A cycle in this context is a sequence \((x_1,x_2,\ldots,x_k)\), meaning that \(\phi(x_1)=x_2\), \(\phi(x_2)=x_3)\), and so on until \(\phi(x_k)=x_1\). Following our reasoning above, the vertices in each cycle must be colored the same color, and the total number of colors fixed by \(\phi\) is \(k^m\), where \(m\) is the number of cycles.

    Let's apply this to another permutation, shown in Figure \(\PageIndex{2}\). This permutation consists of a single cycle, so every vertex must have the same color, and the number of colorings fixed by \(\phi\) is \(k^1\). All rotations of the pentagon consist of a single cycle except the trivial rotation, that is, the identity permutation. In cycle form, the identity permutation is \((1)(2)(3)(4)(5)\), so the number of colorings fixed by the identity is \(k^5\). Putting everything together, we thus have \[|{\cal O}|={1\over 10}(k^5+k+k+k+k+k^3+k^3+k^3+k^3+k^3)= {1\over 10}(k^5+5k^3+4k).\nonumber\] For example, the number of different 3-colorings is \((3^5+5\cdot3^3+4\cdot 3)/10=39\).

    clipboard_ea4471a49c82142660d0b55625c857526.png
    Figure \(\PageIndex{2}\): The permutation \((1,3,5,2,4)\) is a single cycle.
    Example \(\PageIndex{1}\)

    We find the number of distinct colorings of the vertices of a square with \(k\) colors, modulo \(D_4\), the dihedral group of size 8. The elements of \(D_4\) are the four rotations \(r_0\), \(r_{90}\), \(r_{180}\), \(r_{270}\), where \(r_i\) is the counterclockwise rotation by \(i\) degrees, and the four reflections \(f_H\), \(f_V\), \(f_D\), \(f_A\), as indicated in Figure \(\PageIndex{3}\).

    clipboard_e95cec0177acd92850e4319b8152c549a.png
    Figure \(\PageIndex{3}\): The reflection axes for \(f_H\), \(f_V\), \(f_D\), and \(f_A\).

    In cycle notation these permutations are: \[\eqalign{ r_0&=(1)(2)(3)(4)\cr r_{90}&=(1,4,3,2)\cr r_{180}&=(1,3)(2,4)\cr r_{270}&=(1,2,3,4)\cr f_H&=(1,4)(2,3)\cr f_V&=(1,2)(3,4)\cr f_D&=(1)(2,4)(3)\cr f_A&=(1,3)(2)(4).\cr }\nonumber\] so the number of colorings is \[f(k)={1\over 8}(k^4+k+k^2+k+k^2+k^2+k^3+k^3)={1\over8}(k^4+2k^3+3k^2+2k).\nonumber\] For example, \(f(2)=6\); the six colorings are shown in Figure \(\PageIndex{4}\).

    clipboard_e64209b48fee635b512340534634a04d6.png
    Figure \(\PageIndex{4}\): The six 2-colorings of the square.
    Example \(\PageIndex{2}\)

    Here is a more complicated example: how many different graphs are there on four vertices? In this case, of course, "different'' means "non-isomorphic''. We can interpret this as a coloring problem: Color the edges of the complete graph \(K_4\) with two colors, say black and white. The black edges form a graph; the white edges are the ones left out of the graph. The group \(G\) we need to consider is all permutations of the six edges of \(K_4\) induced by a permutation of the vertices, so \(|G|=4!=24\). All we need to know is the number of cycles in each permutation; we consider a number of cases.

    Case 1. The identity permutation on the vertices induces the identity permutation on the edges, with 6 cycles, so the contribution to the sum is \(2^6\).

    Case 2. A 4-cycle on the vertices induces a permutation of the edges consisting of one 4-cycle and one 2-cycle, that is, two cycles. There are \(3!=6\) 4-cycles on the vertices, so the contribution of all of these is \(6\cdot2^2\).

    Case 3. A permutation of the vertices consisting of a 3-cycle and a 1-cycle induces a permutation of the edges consisting of two 3-cycles. There are \(4\cdot2=8\) such permutations of the vertices, so the contribution of all is \(8\cdot2^2\).

    Case 4. A permutation of the vertices consisting of two 2-cycles induces a permutation of the edges consisting of two 1-cycles and two 2-cycles. There are \({1\over2}{4\choose2}=3\) such permutations, so the contribution is \(3\cdot 2^4\).

    Case 5. A permutation of the vertices consisting of a 2-cycle and two 1-cycles induces a permutation of the edges consisting of two 1-cycles and two 2-cycles. There are \({4\choose2}=6\) such permutations, so the contribution is \(6\cdot 2^4\).

    The number of distinct colorings, that is, the number of distinct graphs on four vertices, is

    \[{1\over24}(2^6+6\cdot2^2+8\cdot2^2+3\cdot 2^4+6\cdot2^4)= {1\over24}(264)=11.\nonumber\]

    It is possible, though a bit difficult, to see that for \(n\) vertices the result is

    \[\label{eq:1}\eqalignno{ f(n)&=\sum_{\bf j}\prod_{k=1}^n{1\over k^{j_k} j_k!} \prod_{k=1}^{\lfloor n/2\rfloor}2^{k j_{2k}} \!\!\prod_{k=1}^{\lfloor (n-1)/2\rfloor}\!\!2^{kj_{2k+1}} \prod_{k=1}^{\lfloor n/2\rfloor} 2^{kC(j_k,2)} \!\!\!\!\prod_{1\le r< s\le n-1}\!\!\!\!\!\!\!\! 2^{\gcd(r,s)j_rj_s}\cr} \]

    where the sum is over all partitions \({\bf j}=(j_1,j_2,\ldots,j_n)\) of \(n\), that is, over all \(\bf j\) such that \(j_1+2j_2+3j_3+\cdots+nj_n=n\), and \(C(m,2)={m\choose2}\). With this formula and a computer it is easy to compute the number of graphs when \(n\) is not too large; for example, \(f(5)=34\), so there are 34 different five-vertex graphs.

    In light of the forgoing discussion, we can restate Theorem \(\PageIndex{1}\). If \(\sigma\) is a permutation, let \(\#\sigma\) denote the number of cycles when \(\sigma\) is written in cycle form.

    Corollary \(\PageIndex{2}\)

    If group \(G\) acts on the colorings of an object, the number of distinct colorings modulo \(G\) with \(k\) colors is \[{1\over|G|}\sum_{\sigma\in G} k^{\#\sigma}.\nonumber\]


    This page titled 6.3: Burnside's Theorem is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.