Burnside's Lemma

Burnside's lemma is a result in group theory that can help when counting objects with symmetry taken into account. It gives a formula to count objects, where two objects that are related by a symmetry (rotation or reflection, for example) are not to be counted as distinct.

Burnside's lemma gives a way to count the number of orbits of a finite set acted on by a finite group.

Burnside's Lemma:

Let $G$ be a finite group that acts on the set $X$. Let $X / G$ be the set of orbits of $X$ $($that is, each element of $X/G$ is an orbit of $X).$ For any element $g\in G,$ let $X^g$ be the set of points of $X$ which are fixed by $g$: $X^g = \{ x \in X \colon g \cdot x = x\}.$ Then

$$\displaystyle{ |X / G| = \frac1{|G|} \sum_{g \in G} |X^g| }.$$

In other words, the number of orbits is the average number of fixed points of $G$.

Main article: Group actions

To understand Burnside's lemma, we need to understand symmetry groups and group actions. The following is a summary of some concepts and definitions from the group actions wiki, repeated here for convenience.

As an informal definition, a group is a mathematical object consisting of a set and an operation that satisfies certain properties. Groups generalize many structures that we know; for example, the integers together with the addition operation form a group. However, groups are more general than that; for example, the "rotate by $x^\circ$" operations, together with the composition operation, also form a group.

For a formal definition,

A group is an ordered pair $(G, +)$, where $G$ is a nonempty set and $+ : G \times G \to G$ is a two-argument function on $G$ satisfying the following:

• Associativity: $(a+b)+c = a+(b+c)$ for all $a,b,c \in G.$
• Identity element: There exists $0 \in G$ such that $0+a = a+0 = a$ for all $a \in G.$
• Inverse element: For every $a \in G$, there exists an inverse $-a \in G$ such that $a+(-a) = (-a)+a = 0.$

A symmetry group is a group whose elements are transformations on some objects, and whose operation is the composition operation $\circ$. (This is similar to composition of functions.) For example, the "rotate by" example above is a symmetry group, since the elements are transformations that can be applied to objects, and the operation is the composition operation.

A symmetry group is technically written as $(G, \circ)$ with both the set of transformation and the composition operation explicitly written, but often it's understood that the composition operation is implied, so a symmetry group is often written as simply $G$, the set of transformations it has.

A symmetry group can act on a set of objects. Informally, this basically means each element of the group transforms an object into another object. For example, if we have the symbol "6", we can apply the element "rotate by $180^\circ$" to it, transforming it to "9".

For a formal definition,

If $G$ is a symmetry group with identity element $\epsilon$ and $X$ is a set, then a (left) group action $\varphi$ of $G$ on $X$ is a function from $G \times X$ to $X$ satisfying the following:

• Identity property: $\varphi(\epsilon, x) = x$ for all $x \in X.$
• Composition property: $\varphi(g \circ h, x) = \varphi\big(g, \varphi(h, x)\big)$ for all $g,h \in G$, $x \in X.$

Often, $\varphi(g, x)$ is denoted as $g\cdot x$, and the composition operator is omitted, which make the following statements:

• Identity property: $\epsilon \cdot x = x$ for all $x \in X.$
• Composition property: $(gh) \cdot x = g \cdot (h \cdot x)$ for all $g,h \in G$, $x \in X.$

For example, suppose $X$ is the set of all unit squares whose sides are colored in red and/or blue. We can apply "rotate by $90^\circ$ (clockwise)" to the square on the left to give the square on the right:

If a group acts on a set, we can talk about fixed points and orbits, two concepts that will be used in Burnside's lemma. Fixed points are comparable to the similar concept in functions. The orbit of an object is simply all the possible results of transforming this object.

Let $G$ be a symmetry group acting on the set $X$.

For an element $g \in G$, a fixed point of $X$ is an element $x \in X$ such that $g . x = x$; that is, $x$ is unchanged by the group operation. The set of all fixed points of $X$ with respect to $g$ is often denoted $X^g$.

For an element $x \in X$, the orbit $G . x$ of $x$ is the set $\{g . x | g \in G\}$; that is, all possible results of transforming $x$.

A result in group theory states that orbits partition the set $X$; that is, if $a \in X$ has orbit $A$, then all elements of $A$ also have orbit $A$, and for every element $a' \not\in A$, the orbit of $a'$ doesn't share any element with $A$. Thus, it makes sense to talk about the number of orbits:

The set of orbits $X / G$ of $X$ acted upon by $G$ is $\{G . x | x \in X\}$; that is, it's the set of orbits over all elements of $X$, not counting repetition. The number of orbits is simply its cardinality $|X / G|$.

Those are all the definitions needed to understand Burnside's lemma.

Burnside's lemma is very often used in counting objects, in which symmetry should be taken into account. Consider the example below.

The sides of a square are to be colored by either red or blue. How many different arrangements are there if

1. a coloring that can be obtained from another by rotation is considered different, or
2. a coloring that can be obtained from another by rotation is considered identical?

---

For the first problem, this is simple. Since symmetry is not taken into account, we can simply use usual counting methods. Each side has two possible choices, and all of these are independent, so we can multiply everything: $2^4 = 16$ for four sides.

The second problem is much harder since we need to be careful not to double-count things that can be obtained by rotation. We can try a case by case analysis:

• All red is one. All blue is also one.
• One red (and the rest blue) has four possibilities, all of them able to be obtained from each other by rotation. Thus there is only one unique coloring here.
• One blue (and the rest red) also has only one unique coloring.
• Among two reds and two blues, there are two possible ways. Either the reds are adjacent to each other, in which there are four colorings but all of them identical, or they aren't, in which there are just two and also identical. This case gives us two unique colorings.

In total, there are $1+1+1+1+2 = 6$ such colorings:

However, we can apply Burnside's lemma to this.

The group $G$ is made up of four elements: "rotate by $0^\circ$," "rotate by $90^\circ$," "rotate by $180^\circ$," and "rotate by $270^\circ$" (all clockwise). $($This group is also known as the cyclic group of order 4, or $C_4).$ The set $X$ contains all $2^4 = 16$ colorings if we assume rotations are distinct (as in the first problem). Now, we need to count the number of fixed points:

• "Rotate by $0^\circ$" is the identity transformation. This clearly doesn't change any of the 16 colorings; there are 16 fixed points.
• To determine the fixed points of "rotate by $90^\circ$," we can inspect the sides. The top side will become the right side; if they are of different colors, clearly the coloring isn't a fixed point (since the right sides will be different). For example, if the top side is red and the right side is blue, after rotating, we have the right side to become red; since the right side has different colors before and after transformation, this is not a fixed point. Likewise, the right side and the bottom side must have the same color. The same goes with the bottom and left, and left and top. In other words, all sides must have the same color. There are only two such colorings, all red or all blue, and thus 2 fixed points.
• "Rotate by $270^\circ$" has a similar argument as above; we also get 2 fixed points here.
• "Rotate by $180^\circ$" is a little more complex. The top and bottom sides must be the same color, and so must the left and right sides, but otherwise there's not much else. Indeed, we can give colors independently: one color for the top and bottom, and another (may be identical) for the left and right sides, giving $2^2 = 4$ fixed points.

In total, we have $16+2+2+4 = 24$ fixed points, over 4 group elements. By Burnside's lemma, the number of orbits, and thus the number of distinct colorings including rotation, is $\frac{24}{4} = 6$. This matches our case-by-case work. $_\square$

In the above example, it's pretty easy to identify all possible colorings by case-by-case work. But what if there are three colors available? Or how can we generalize it? Burnside's lemma allows us to generalize that easily:

The sides of a square are to be colored by $n$ colors (each side has one color, but a color may color many sides). How many different arrangements are there if two arrangements that can be obtained from each other by rotation are identical?

---

We can use Burnside's lemma here to avoid casework entirely. We already identified all four elements above:

• "rotate by $0^\circ$" fixes all $n^4$ elements,
• "rotate by $90^\circ$" and "rotate by $270^\circ$" fix $n$ elements each, and
• "rotate by $180^\circ$" fixes $n^2$ elements.

In total, that's $n^4 + n^2 + 2n$ elements, and dividing this by the number of transformations 4 gives the desired number of distinct colorings, $\frac{n^4 + n^2 + 2n}{4}$.

This allows us to compute, for example, that the number of distinct colorings with 2016 colors is 4129545225456 by simply plugging into the formula. We can technically do case work, but it will be messy. $_\square$

The relevant group is not just rotations.

The sides of a rectangle (that is not a square) are to be colored by either red or blue. How many possible colorings are there, if two colorings that can be obtained from each other by rotation and/or reflection are considered identical?

---

The group in question is the dihedral group of order 2, also known as $D_2$, which has these four elements:

• identity transformation
• rotate by $180^\circ$
• reflect along the short side
• reflect along the long side.

We now use Burnside's lemma again:

• Identity transformation fixes $2^4 = 16$ elements. No restrictions on sides.
• Rotating by $180^\circ$ fixes $2^2 = 4$ elements. Long sides must match, and so must short sides.
• Reflecting along the short side fixes $2^3 = 8$ elements. Short sides must match, but the two long sides may not match.
• Reflecting along the long side fixes $2^3 = 8$ elements. Long sides must match, but the two short sides may not match.

That gives a total of $\frac{1}{4} \cdot (16+4+8+8) = 9$ orbits. $_\square$

Six indistinguishable balls are to be distributed into three indistinguishable boxes. How many ways are there to do this?

---

At first, this doesn't look like a Burnside's lemma problem. However, we can still solve it with Burnside's lemma anyway.

The relevant group is the permutation group on three elements, also known as $S_3$, which has these elements:

• Don't move the boxes.
• Swap the first and the second boxes.
• Swap the first and the third boxes.
• Swap the second and the third boxes.
• Make the first box to be the second and push the others in circular fashion.
• Make the first box to be the third and push the others in circular fashion.

Or alternatively, represented as permutations,

• $(1,2,3)$ stays as $(1,2,3)$;
• $(1,2,3)$ becomes $(2,1,3)$;
• $(1,2,3)$ becomes $(3,2,1)$;
• $(1,2,3)$ becomes $(1,3,2)$;
• $(1,2,3)$ becomes $(2,3,1)$;
• $(1,2,3)$ becomes $(3,1,2)$.

This time we can simplify our work a bit:

• The identity permutation fixes all possible configurations.
• The three permutations which swap two boxes fix configurations in which the contents of the two swapped boxes are equal.
• The two permutations which rotate the boxes fix configurations in which the contents of all boxes are equal.

The problem, now, is to compute how many possible configurations fall in each possibility.

The case of identity permutation is the hardest one. We can imagine that the boxes are now distinguishable (since we are no longer to move them around, we might as well name them first, second, and third box). This problem of putting 6 indistinguishable balls in 3 distinguishable boxes can be solved using the stars and bars technique, which tells us that there are $\binom{8}{2} = 28$ configurations.

The second, where two boxes are swapped, is easier because we can just do a simple case work. The contents of the two swapped boxes must be either 0, 1, 2, or 3 balls each, and the content of the remaining box follows (6, 4, 2, or 0 balls respectively). There are 4 configurations here for each pair of swapped boxes.

The third, where boxes are rotated, is the simplest: since all of them have the same number of balls, all of them must necessarily have 2 balls. There is exactly one configuration in this case.

Adding everything up, we obtain $\frac{1}{6} \cdot (28+4+4+4+1+1) = 7$ orbits; that is, there are 7 ways to put them. We can verify this with casework: $$6+0+0,\ 5+1+0,\ 4+2+0,\ 4+1+1,\ 3+3+0,\ 3+2+1,\ 2+2+2$$ are all of them. $_\square$

These tools will allow one to solve the following problem:

Start by working with the sum $\sum\limits_{g\in G} |X^g|.$ This can be changed to a sum over $X$: $$\begin{aligned} \sum_{g\in G} |X^g| &= \sum_{g\in G} \big| \{ x \in X : g \cdot x = x \} \big| \\ &= \big| \{ (g,x) : g \in G, x \in X, g \cdot x = x \} \big| \\ &= \sum_{x \in X} \big| \{g \in G : g \cdot x = x\} \big| \\ &= \sum_{x \in X} |G_x|. \end{aligned}$$ Here $G_x$ is the stabilizer of $x.$

The orbit-stabilizer theorem gives $|G_x| = \frac{|G|}{|O_x|},$ where $O_x$ is the orbit of $x.$ So the sum becomes $$\begin{aligned} \sum_{x\in X} |G_x| &= \sum_{x \in X} \frac{|G|}{|O_x|} \\ &= |G| \sum_{x\in X} \frac{1}{|O_x|}. \end{aligned}$$ To evaluate this last sum, consider the contribution to it from all the $x$ in a given orbit $O.$ Each $x$ in the orbit contributes $\frac{1}{|O|}$ to the sum, and there are $|O|$ such $x.$ So the contribution to the sum from all the $x$ in a given orbit is exactly $1,$ and therefore the sum is equal to the number of orbits, $|X/G|.$

Putting this all together gives $$\sum_{g\in G} |X^g| = |G| \cdot |X/G|,$$ and the lemma follows. $_\square$