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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s