An Application Of Burnside’s Lemma

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 G acting on a set X , and, for each g \in G : let X_g be the elements of X invariant by g . Then the number of orbits is equal to:

\frac{1}{|G|}\sum_{g \in G}|X_g|

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 2^8 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 2^2 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 2^4 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:

\frac{2^8+2+2^2+2+2^4+2+2^2+2}{8} = 36

Scroll to top