## Applications of Burnside’s Lemma

Burdnside’s Lemma. Let $G$ be a group of permutations of the set $S$. Let $T$ be any collection of colorings of $S$ that is closed under $G$. Then the number $N$ of equivalence classes is

$\displaystyle N=\dfrac{1}{G} \sum_{\pi \in G} \Psi(\pi)$

where $|G|$ is the number of permutations and $\Psi(\pi)$ is the number of colorings in $T$ left fixed by $\pi$.

I have just read this book during Jarkom (Computer Network) class this afternoon. The class is so boring that I really push myself to understand the textbook (Alan Tucker’s Applied Combinatorics) I borrowed from library.

At least, I got something good for me during that class.

Source: howtoteachothers.com

I believe that the theorem has deeper philosophical meaning, but here are some applications that are down-to-earth.

Example 1. A merry-go-round can be built with three different styles of horses. How many five-horse merry-go-rounds are there?

Solution. First, notice that there are some merry-go-rounds that are different by its horses’ fixed position, but equivalent when you rotate the horses. So, we realize that there are $5$ kinds of permutation (by $\frac{2k}{5} \pi$ degree for $k=0,1,2,3,4$). For $k=0$, note that any kind of colorings of $5$ horses are fixed (because we don’t rotate them). Hence, there are $3^5$ kind of coloring. For $k=1,2,\dots,4$, one can show that the only fixed coloring of the five-horses are those that have all horses colored with the same color, thus there are only $3$ perceived colorings for each rotation. By Burnside’s Lemma, the number of such colorings is $\dfrac{1}{5}(3^5 +3+3+3+3)=51$.

$\blacksquare$

Example 2. Fifteen balls are put in a triangular array as shown. How many different arrays can be made using balls of three colors if the array is free to rotate?

Source: My computer

Solution. First, there are three kinds of rotation. The first rotation may give you $3^{15}$ possible colorings. The second and third rotation each will give you $3^5$ colorings (why?). Thus, the number of possible colorings is $\dfrac{1}{3}(3^{15}+2\times 3^5)=4783131$ possible colorings.

$blacksquare$

Example 3. How many different ways are there to color five faces pyramid (with square base) using red, white, blue, and yellow?

Source: revelationsofthebible.com

Solution. The base may choose any color it wants, so there are $4$ possible colorings. Now, the two standing faces may consider rotations. We know that there are $8$ realistic permutations (the regular $90^{\circ}$ rotations, also facing faces symmetry, and diagonal symmetry).

For the $0^0$ rotations, we have $4^4$ colorings. For $90^{\circ}$ and $270^{\circ}$ rotations, all faces must have same color, thus there are $4$ possible colorings, each. For $180^{\circ}$ rotations, two facing faces must be of equal color thus there are $4 \times 4$ possible colorings. In this case, thus there are $4^4+2\times 4 + 4^2$ possible colorings.

Now, we consider facing faces symmetry. There are two kinds of symmetry here (say horizontal and vertical). Intuitively, both symmetry will have the same number of colorings, so let’s fix two facing faces. There are $4\times 4$ ways of coloring the fixed faces while the other two must have the same color, so there are $4$ possible colorings. In this case, thus, there are $2 \times 4^3$ possible colorings.

The last is diagonal symmetry. Again, we only count based on the symmetry of one diagonal only. By symmetry, we only need to color the two faces in one side of symmetry. Thus, in this case, there are $2\times 4^2$ colorings.

Finally, we obtain the number of ways coloring the pyramid $= \dfrac{1}{8}(4^4+2 \times 4+4^2+2 \times 4^3 + 2 \times 4^2) = 55$ ways.

$\blacksquare$

If you have much time like me, you may try the following problem.

Exercise 1. How many different $9-$beads necklaces (cyclicly distinct) can be made from three colors of beads?

Exercise 2. How many ways are there to $3-$color the corners of a square with rotations and reflections allowed if adjacent corners must have different colors?

Exercise 3. Two $n-$digit sequences of digits $0,1,6,8,9$ are vertically equivalent if reading one upside down produces the other, that is, $0068$ and $8900$. How many different (vertically equivalent) $n-$digit sequences are there?

So, I’d post more stuff if I have time. Enjoy!

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.