How many distinct ways can you color the vertices of a square using 3 colors, considering rotational symmetry?
If you said 3⁴ = 81, you're ignoring symmetry.
If you said 81 / 4 = 20.25, well... you're ignoring math.
In this blog, I will dive deep into Burnside’s Lemma and the Polya Enumeration Theorem – two powerful tools in counting under symmetry, often underused in Competitive Programming.
Suppose, you’re given n beads on a circular necklace. You can color each bead with k colors.
How many distinct colorings exist, considering that rotating the necklace doesn't change its appearance?
Brute force? Exponential.
Naive formulas? Won’t work.
This is where group actions and Burnside’s Lemma step in.
Now Let's suppose, you have a square with 4 vertices. You want to color each vertex with 3 colors.
But two colorings are considered the same if one can be rotated to get the other.
Step 1: Define Group Actions
There are 4 rotational symmetries of a square:
| Rotation | Description |
|---|---|
| g₀ | 0° (identity) |
| g₁ | 90° clockwise |
| g₂ | 180° |
| g₃ | 270° clockwise |
So, |G| = 4
Step 2: Count Fix(g) for each rotation
Let’s denote the number of colors as k = 3.
For each rotation, we count the number of colorings that remain unchanged after the rotation:
| Rotation | Cycles induced by rotation | Fix(g) |
|---|---|---|
| g₀ | (1)(2)(3)(4) | 3⁴ = 81 |
| g₁ | (1→2→3→4→1) | 3¹ = 3 |
| g₂ | (1↔3)(2↔4) | 3² = 9 |
| g₃ | Same as g₁ | 3¹ = 3 |
Step 3: Apply Burnside’s Lemma
Total distinct colorings:
= (1/4) * (81 + 3 + 9 + 3) = (1/4) * 96 = 24 So the answer is 24 distinct colorings, not 81.
Burnside gives us the idea — Polya gives us the formula.
Let’s Suppose say we want to count the number of ways to color n beads on a circular necklace using k colors, modulo rotations.
In circular rotation, the group G has n elements: rotation by 0, 1, ..., n−1 positions.
For each rotation by r, the number of cycles it induces is gcd(n, r).
So the number of distinct colorings is:
