Burnside’s Lemma is a very nice tool I had the occasion to use in the Mathematical Olympiads to solve some Combinatorics problems.

It says that, given a finite group acting on a set , and, for each : let be the elements of invariant by . Then the number of orbits is equal to:

May sound a little scary, but let’s see an application.

We have a regular octagon, and every side is painted either black or white. How many possible colorations are there if configurations that can be obtained from another one by a rotation are considered as equal?

So, the set is the total number of configurations, and the group is the one containing all the 8 possible rotations (including the identity).

Let’s apply Burnside’s Lemma and number the vertexes from 1 to 8.

Identity: all 2^8 configurations are fixed.

Rotation by 45 degrees: being invariant by such a rotation means that vertex 1 = vertex 2 = … = vertex 8. So there only are 2 fixed configurations.

Rotation by 90 degrees: this means vertex 1 = vertex 3 = vertex 5 = vertex 7 and vertex 2 = vertex 4 = vertex 6 = vertex 8. So, there are fixed configurations.

Rotation by 135 degrees: same as 45 degrees.

Rotation by 180 degrees: this means vertex 1 = vertex 5, vertex 2 = vertex 6, vertex 3 = vertex 7, vertex 4 = vertex 8. So, there are fixed configurations.

Rotation by 225 degrees: same as 45 degrees.

Rotation by 270 degrees: same as 90 degrees.

Rotation by 315 degrees: same as 45 degrees.

To sum up, we have that the number of distinct configurations (or orbits) is: