Burnside's Lemma

Count distinct objects under symmetry (rotations) using Burnside's lemma.

[Combinatorics]|

Jul 9, 2026

|explanatory_notes.md|

#burnside#counting#symmetry#necklace#group-theory

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

ll power(ll base, ll exp, ll mod) {
    ll res = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll modInv(ll x) { return power(x, MOD - 2, MOD); }

ll necklaceCount(ll n, ll k) {
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
        ans = (ans + power(k, __gcd(i, n), MOD)) % MOD;
    return ans % MOD * modInv(n) % MOD;
}

24 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Burnside's Lemma

Counts distinct objects under a group action (e.g., rotational symmetry).

Formula

|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|

where $X^g$ is the set of elements fixed by group element $g$ .

Necklace Application

For $n$ beads with $k$ colors, considering only rotational symmetry:

\text{Necklaces} = \frac{1}{n} \sum_{i=1}^{n} k^{\gcd(i, n)}

Rotating by $i$ positions fixes $k^{\gcd(i,n)}$ colorings.

When to Use

Counting distinct colorings under rotation

"How many distinct objects up to symmetry?"

Grid or polygon coloring with rotational equivalence

Notes

For reflections too, use Polya enumeration (Burnside + reflection group)

Requires modular inverse of

n

(so MOD must be prime and

\gcd(n, \text{MOD}) = 1

)

Complexity

Time —

O(n \log n)

Space —

O(1)