Burnside Combinatorics

Back here we learned about the Burnside Counting Formula. Now we will see how this formula is applied to the problem of combinatorics.

Problem 1: How many different ways are there to seat n people around a round table?

Solution: Number the seats of this table as 1,2,...,n. Let X be the set of all possible arrangements of this table. Clearly, |X|=n! , but we are assuming that two seating arrangements are the same if we can turn on arrangement into another round the table. This this number is too much, we are over counting. Let G be the group of all rotations of the table labeled 1,2,...,n. If we let r be the counterclockwise rotation one position over then we clearly see that r has order n and that r generated G. Therefore, G is cyclic of order n. We will now define the action of G on X to be a rotation applied to a seating arrangement. Consider two arrangements of the table. They are considered the same iff we can rotate one into another. That is to say two seating arrangements are the same if they are related to one another under some rotation. If $$x_1,x_2\in X$$ are two arrangements we say that they are equal iff $$x_2=gx_1$$ for some g in G. Thus, two arrangements are equal if and only if they lie in the same orbit. The desired number of seating arrangements is therefore equal to the number of orbits. This is given by $$\frac{1}{|G|}\sum_{g\in G}|X_g|$$ by Burnside's formula. Note that if g is not trivial then $$X_g$$ is empty, but $$|X_e| = n!$$. Therfore, the answer is $$\tfrac{n!}{n} = (n-1)!$$.

Problem 2 How many different ways are there to color a cube with different colors on every face?

Solution: Label the sides of some cube as 1,2,3,4,5,6. Let X be the number of ways to number a cube in a static position, clearly |X|=6!=720. Let G be the "rotation symmetry group" on this cube. Put simply G consists of all rotation operators on the cube. And G will act on X in the natural way, the rotations applied to our numbered cube. As before two coloring of a cube a considered the same if we can rotate on into another. And again notice that $$|X_g|=0$$ if g is not the identity and $$|X_e|=720$$. So all what remains is to count the size of |G|. We do not actually need to know the group structure of G just its order. To see what the order let us say that top face is labeled 1. There are six ways to rotate that number 1 into six other positions. Once we put 1 into a certain position there are then four ways to rotate around this axis keeping 1 fixed. Therefore, rotational symmetry group is of order 24. (It turns out this group is the symmetry group on four elements but this is irrelevant). This means the number of ways is given by 720/24=30.

Problem 3: Let n>2 be odd and consider a $$n\times n$$ grid of squares. The grid is white. How many different ways are there to color this grid with two black squares?

Solution: Let X be the numbered grid with all possible colorings. There are $${{n^2}\choose 2}$$ such colorings. Let G be the group of all rotations on this grid, clearly there are just 4 rotations on this grid, so |G|=4. If $$g$$ is an order three rotation then $$|X_g|=0$$. Obviously $$|X_e|=|X|$$. The interesting case is when g is an order two rotation, i.e. a rotation of 180 degrees. If two points are "rotationally opposite" then a 180 degree rotation will preserve the grid. Note if one colored grid is in the center then no rotationally opposite point exists. But if a point is chosen outside the center there is one and only one pair to it. There are $$n^2-1$$ such choices, but because we double counted we need to take that into account. Therefore, there we shown that $$|X_g|=\tfrac{1}{2}(n^2-1)$$ if g is a rotation of order two. Thus, the number of such colorings given by $$\tfrac{1}{4}{{n^2}\choose 2}+\tfrac{1}{8}(n^2-1)$$.

Exercise: Consider problem #3 again. Suppose that we have a flippable board. That is, we can flip the board around also. How many such coloring are possible in such a case?