The Burnside Lemma looks like it should have an intuitive explanation. Does anyone have one?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
As an example, we consider the number of ways of colouring a cube with n colours with uniqueness up to rotation. We call each unique colouring where rotations are not allowed a static colouring and each unique one where they are allowed a dynamic colouring. We define the the set of orbits to be the (disjoint) static colourings that correspond to each dynamic colouring. We will use rotations to mean a rotation that makes the cube occupy the same space, and as being unique if it is a unique function from the cube to the cube. This includes the identity rotation. Intuitively, the lemma says:
Proposition 1. #Orbits * #Rotations = sum for each rotation r of #static colourings unchanged by this rotation
We will now consider each orbit O separately. Pick a static colouring c inside O. Suppose two (possibly equal) rotations p, q give the same static colouring, d, when applied on c. Then p^-1*q fixes d. Additionally, suppose r (possibly the identity) fixes d. p^-1*(p*r) will also fix d. So p*r will take c to d. Since p*r is different for each r, and p^-1*q is different for each q, the mapping functions are injective in both directions and there is a bijection between the q and r values.
So, for each O, the number of rotations is the sum over each static colorings x in O times the number of rotations producing x. This can be rewritten as the sum over each rotation r of the number of static colourings in O fixed by r (due to the bijection in the previous paragraph). We get proposition 1 by adding over all O.
The general proof is quite similar to this, except that it uses group theory.
You can quickly reduce to the case of a transitive action, in which case we just want to explain why the total number of times that something gets fixed is exactly the size of the group. But in this case everything is symmetric at all points in the (unique) orbit. So to count all the times something gets fixed, we can just count how many times a particular x gets fixed, and multiply by the size of the orbit. Now we've reduced to the fact that the size of an orbit is the index of the stabilizer.
If you have a picture in mind of the action groupoid then the Burnside's lemma is quite intuitive. Truth is, you can see it as a 'global' version of the orbit-stabilizer theorem, in fact in any orbit the automorphisms are in bijection with the group and since the orbits form a partition of the set you have a bijection between all the automorphisms and the product of G with the orbit space. If it is not so clear you can find some notes I wrote for personal use here. The usual combinatorial formula for finite groups follows from the global orbit-stabilizer theorem computing the sizes of the sets, but the isomorphism between the two sets is also interesting.
I also wonder if it is a natural bijection, and answers this MO question.