An Application Of Burnside’s Lemma – Mattia Giuri's bizarre blog

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$