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:
Awesome man
i think there is a trick to make the Polya sum run in about $$$\sqrt n$$$ time instead of $$$O(n)$$$:
So the final answer is
loop only over the divisors of $$$n$$$ (there are $$$O(\sqrt n)$$$ of them) then precompute $$$\varphi(d)$$$ with a sieve or factorization and use fast exponentiation for $$$k^{n/d}$$$
This avoids scanning all $$$r$$$ in $$$[0,n-1]$$$ and can handle $$$n$$$ up to $$$10^6$$$
not 100% sure but should theoretically work
but if n < 1e6 then we can precompute all divisors in 1e6 and answer queries in $$$O(d(n) log(n))$$$. is it correct?
Yes, you are right. That’s an optimization using number theoretic grouping. Looping over divisors is much faster and with precomputed φ and fast exponentiation it works efficiently even for large n.
Hot