Burnside's Lemma implementation

Question

Can someone please explain to me what Burnside's Lemma theory is about, how to understand if a situation or problem calls for the use this theory? I went through the wiki page but could not grasp the concept. I found it too complicated. Can someone break it down to simple steps and explain with an example ? I need to know how to place 5 identical red beads, 3 green beads and 2 blue beads in a circular arrangement?

Answer 1

In your example, you wish to arrange 10 beads, five of which are red, three of which are green, and two of which are blue around a circle. You can convince yourself that any rotation of the circle from one point to the next will produce a different circle (since you cannot simultaneously fix both the blue and the green beads), so we may naively approach this problem.

Ask the related question: How many ways can we arrange five red, three green, and two blue beads on a straight line? You should know this to be $\binom{10}{5,3,2}=\binom{10}{5}\binom{5}{3}\binom{2}{2}=\frac{10!}{5!3!2!}$ (seen by multiplication principle: pick the spots for the reds, pick the spots for the greens, pick the spots for the blues).

Now, we ask the question, for each of these, how many times did we overcount. We overcounted by a factor of 10, since each arrangement is "similar"(considered the same) as each of its rotations. Hence the final answer is $\frac{10!}{5!3!2!}\cdot\frac{1}{10} = \frac{9!}{5!3!2!}$.

This could have been seen via Burnside's as well. Our transformation group in this case, $G$, will be $\{ id, \rho, \rho^2,\dots,\rho^9\}=\langle \rho\rangle$, the rotations on the circle. Then $|G|=10$.

Burnside's lemma says:

$\text{total number of "different" ways} = \frac{1}{|G|}\sum\limits_{\sigma\in G} f(\sigma)$ where $f(\sigma)$ counts the number of arrangements which are left fixed by the symmetry $\sigma$. Noticing exactly as I had before, that no rotation (except the identity) can simultaneously fix all of the blues and greens, we have the only surviving term in the summation is $f(id)$, i.e., the number of ways of arranging the beads on a straight line. Hence the answer is again $\frac{1}{|G|}f(id) = \frac{1}{10}\binom{10}{5,3,2} = \frac{9!}{5!3!2!}$

---

Burnside's is a much more powerful and necessary tool if we are asking the question of when we are not limited to a specific number of each bead. How many ways can we arrange 10 beads (distinguishable only by color) around a circle if each bead is one of three colors (red, blue, green) and we consider an arrangement to be similar if it is a rotation of another.

For this, we start by understanding what the symmetries allowed are: In my example, we are only interested in the rotations again: $G=\{id,\rho,\rho^2,\dots,\rho^9\}$. Now, let us inspect which arrangements are left fixed by each symmetry individually.

• $f(id)$: Every arrangement is fixed by $f(id)$, so we have $3^{10}$ possible arrangements that are fixed by $id$.
• $f(\rho)$: Every space is necessarily the same color as the one next to it (else the rotation would have made it look different), so all beads must have been the same color. Therefore there are only three arrangements (one for each color) that are left fixed.
• $f(\rho^2)$: Every other space is the same color. Thus the beads in spots 1,3,5,7,9 are all the same color, and the beads in spots 2,4,6,8,10 are all the same color (possibly same or different to the first set). Choose the color for the first set, and choose the color for the second set, for a total of $3\cdot 3=9$ arrangements left unchanged by $\rho^2$.
• $f(\rho^5)$: The beads in spots 1 and 6 must be the same color, the beads in spots 2,7 must be the same color, ... the beads in spots 5,10 must be the same color. Thus, there are $3^5 = 243$ arrangements left unchanged by $\rho^5$.
• $f(\rho^3),f(\rho^7),f(\rho^9)$ all follow the same logic as $f(\rho^1)$ and so also have 3 arrangements each.
• $f(\rho^4),f(\rho^6),f(\rho^8)$ all follow the same logic as $f(\rho^2)$ and so also have 9 arrangements each.

Thus the total number of "different" necklaces are is:

$\frac{1}{|G|}\sum\limits_{\sigma\in G} f(\sigma) = \frac{1}{10}(3^{10}+3\cdot 4+9\cdot 4 + 243) = 5934$