Advanced Counting: Burnside's Lemma

Sometimes the theory we have discussed so far is not enough to calculate the number of positions of a puzzle. Fortunately there is a theorem from group theory that will help us with this. It is called Burnside's Lemma (although he was not the first to discover or prove it):

Theorem: Suppose we have a finite set X, and a finite group G of permutations of X. For each element g in G write |Fix(g)| for the number of elements of X that are not changed by g, and write |G| for the number of elements of G. Then the number of orbits of X is equal to 1/|G| Σ_g∈G |Fix(g)|.

What does this mean, though? Well, when we are counting the number of positions of a puzzle, we want the number of positions regardless of orientation - you shouldn't be able to get from one position to another just by rotating the puzzle, but we also don't want to miss any. The way we do this is by setting X to the set of every possible position in every possible orientation and G the possible ways to rotate the cube. The number of elements in X is relatively easy to calculate (it's like finding the number of positions of a puzzle, except that you don't fix anything; for example the size of X for the 2x2 cube would be 8! 3^7), and the number of elements in G can mostly be looked up from a small table, since it is 12 for a puzzle with tetrahedral symmetry, 24 for puzzle with the symmetry of a cube or octahedron, and 60 for one with the symmetry of a dodecahedron or icosahedron. Now, the number of orbits is simply the number of positions of a puzzle regardless of orientation, which is exactly what we want - so as long as we can compute the Fix(g) values, we know exactly how many positions a puzzle has, even if the puzzle has repeated pieces.

One really important thing to notice is that, for any cycle in a permutation in G, every piece on the cycle has to look the same. This is pretty important because it tells us that if we have, say, three of each piece, it is impossible for g to fix any positions if g contains a 4-cycle (or bigger), because there are no sets of 4 of the same piece. Also, if g contains only 3-cycles, and the number of duplicate pieces in each set is not a multiple of 3, g cannot fix any positions.

I want to do two examples to show how this works. First I'll do the very simple example of a cube with three red faces and three blue faces which can be switched any way we want. We already saw that our basic approximation gave something like .83 when the actual answer was 2. Let's use Burnside's Lemma. The size of X is 6 choose 3 or 20, and the size of G is 24 because the puzzle is cubical. Let's calculate the |Fix(g)|'s: if g is the permutation that does nothing, 20 positions remain the same; if g is a rotation around a corner (there are 8 of these), 2 positions are fixed; if g is a 90-degree rotation around a face (there are 6 of these), there are no fixed positions; if g is a 180-degree rotation around a face (there are 3 of these), there are 4 fixed positions; and if g is a flip around an edge (there are 6 of these), there are no fixed positions. So the total number of positions is 1/24 (20 + 8*2 + 0 + 3*4 + 0) = 1/24 (48) = 2. It's exact!

Now let's do a very hard example: the (non-jumbled) Little Chop or 24-cube, which has 24 pieces, with 4 each of 6 colors and no orientation. The size of X is 24!/(4!^6) and the size of G is 24 again. Calculate the values of |Fix(g)|: if g does nothing, 24!/(4!^6) positions remain the same; if g rotates around a corner, we create 8 3-cycles so no positions can be fixed; if g is a 90-degree rotation around a face, there are 6 4-cycles so 6! positions are fixed; if g is a 180-degree rotation around a face, there are 12 2-cycles so 12!/(2!^6) positions are fixed; and if g is a flip around an edge, there are again 12 2-cycles so 12!/(2!^6) positions are fixed. The total number of positions is 1/24 (24!/(4!^6) + 6*6! + 3*12!/(2!^6) + 6*12!/(2!^6)), which works out to 135,277,941,853,080. We can't really verify this, but if we have done our calculations right it is the correct value. Note that with our basic computations, fixing one of the 4 pieces of a specific color, we would get an approximate value of 1/4 (23!/(3! * 4!^5)) = 135,277,939,046,250, which is pretty close (but not exact).