Burnside's Lemma

Question

I've been trying to understand what Burnside's Lemma is, and how to apply it, but the wiki page is confusing me. The problem I am trying to solve is:

You have 4 red, 4 white, and 4 blue identical dinner plates. In how many different ways can you set a square table with one plate on each side if two settings are different only if you cannot rotate the table to make the settings match?

Could someone explain how to use it for this problem, and if its not too complicated, try to explain to me what exactly it is doing in general?

Answer 1

There are four possible rotations of (clockwise) 0, 90, 180 and 270 degrees respectively. Let us denot the 90 degree rotation by $A$, so the other rotations are then its powers $A^i,i=0,1,2,3$. The exponent is only relevant modulo 4, IOW we have a cyclic group of 4 elements. These rotations act on the set of plate arrangements. So if $RWBR$ denotes the arrangement, where there is a Red plate on the North side, White on the East side, Blue on the South, and another Red plate on the Western seat, then $$ A(RWBR)=RRWB, $$ because rotating the table 90 degrees clockwise moves the North seat to East et cetera.

The idea in using Burnside's lemma is to calculate how many arrangements are fixed under the various rotations (or whichever motions you won't count as resulting in a distinct arrangement). Let's roll.

All $3^4=81$ arrangements are fixed under not doing anything to the table. So $A^0$ has $81$ fixed points.

If an arrangement stays the same upon having a 90 degree rotation act on it, then the plate colors at North and East, East and South, South and West, West and North must all match. IOW we use a single color only. Therefore the rotation $A^1$ has only $3$ fixed points: RRRR, WWWW and BBBB.

The same applies to the 270 degree rotation $A^3$. Only 3 fixed points.

The 180 degree rotation $A^2$ is more interesting. This rotation swaps the North/South and East/West pairs of plates. For an arrangement to be fixed under this rotation, it is necessary and sufficient that those pairs of plates had matching colors, but we can use any of the three colors for both N/S and E/W, so altogether there are 9 arrangements stable under the 180 degree rotation.

The Burnside formula then tells that the number of distinguishable table arrangements is $$ \frac14(81+3+9+3)=\frac{96}4=24. $$

Answer 2

Burnside's Lemma states that the number of orbits $|X/G|$ of a set $X$ under the action of a group $G$ is given by: \begin{equation} |X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g| \end{equation}

where $X^g$ denotes the set of elements in $X$ fixed under the action of $g$.

For the example given, your set $X$ is all the possible ways to arrange three different coloured plates around a square table and $G$ is the set of rotations of the square.

You can think of an arrangement as a string of length four, e.g. the string $RRWB$ indicates the first plate is red, the plate opposite is white, etc. There are $3^4$ arrangements of this kind, so we expect our answer to be smaller than this as, for instance, $RRWB,RWBR,WBRR \text{ and } BRRW$ are all considered to be equivalent as each may be obtained from another by rotation.

We say that the set $\{RRWB, RWBR, WBRR, BRRW\}$ is the orbit of the element $RRWB \in X$ under $G$, and the orbit of $X$ is the set of orbits of each element $x \in X$.

Now, $G$ contains $4$ elements which are rotation by $0,90,180 \text{ and } 270$ degrees respectively. Clearly, all elements in $X$ are fixed under rotation by $0$ rads, so $|X^0|=|X|=3^4$.

The arrangements fixed under rotation by $90$ degrees require that each plate be the same colour as the one next to it and thus include $RRRR,WWWW$ and $BBBB$ only. By symmetry, $$|X^{90}|=|X^{270}|=3$$

A similar counting argument shows that $|X^{180}|=3^2$ and thus by Burnside's Lemma:

$$|X/G|=\frac{1}{4}\left( |X^0|+|X^{90}|+|X^{180}|+|X^{270}|\right) $$ $$~~ = \frac{1}{4}(81+3+9+3)=\frac{96}{4}=24$$

Answer 3

The idea behind Burnside's lemma is fairly simple. Given a set $X$ and a group $G$ acting on it, it relates the number of orbits of $X$ under $G$, which are basically the subsets of $X$ which are traced out by $G$, to the number of elements of $X$ fixed by elements of $G$. Rigorously, orbits are sets of the form $\{gx: g\in G\}$ for fixed $x\in X$. The set of elements fixed by $g\in G$, denoted $X^g$ is the set $\{x: x\in X, gx=x\}$. The lemma states $$\text{Number of orbits}=\frac{1}{|G|}\sum\limits_{g\in G} |X^g|$$ which is useful because it's usually easier to count fixed points than it is to count orbits.

In your case, you are interested in how many ways you can arrange four plates, up to clockwise rotation. This can be stated as the number of sets of the form $$\{\text{setting, setting rotated once, setting rotated twice, setting rotated thrice}\}$$ or more compactly $\{abcd, dabc, cdab, bcda\}$ where each letter represents a plate. More mathematically, the number of orbits of the set of arrangements of your plates under the action of $C_4 = \{1,r,r^2,r^3\}$, the group of cyclic permutations. So to apply Burnside's lemma, we need to find the number of arrangements fixed by each element of $C_4$. The identity element fixes all arrangements, so $|X^1|=3^4$ as we can pick one of three colors for each place. The elements fixed by $r$, rotation to the right, are those which are all the same color, of which there are $3$, so $|X^r|=3$. Similarly, $|X^{r^3}|=3$. Finally, elements fixed by $r^2$ are of the form $abab$, so we have two choices of color for a total of $3\times 3=9$ elements. Thus we have $$\text{Number of orbits}=\frac{1}{4}\sum\limits_{g\in G}|X^g|=\frac{1}{4}(3^4+3+9+3)=24.$$