Why this matters when you build with AI
Some statements ask you to count objects that look the same after a move. A bead necklace is the same necklace when you turn it. A coloured square is the same square when you flip it. The statement says "count the distinct ones", and the easy wrong answer counts every colouring, which is too large by a factor that depends on the symmetry.
AI tools often produce the first answer, k to the power n, and present it with confidence. For 4 beads and 2 colours that gives 16. The correct count of necklaces, where turning counts as the same, is 6. A quick brute force over all 16 strings, keeping one string per rotation class, shows the difference in a few lines. If you have no brute force, the mistake goes unnoticed.
This lesson covers Burnside's lemma. It turns a count of distinct objects into an average over the symmetry moves. The code is C++17. We compiled it with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2.0, and the output blocks are from our runs. The arithmetic is exact and does not depend on the machine.
Definitions
A group of moves is a set of moves that can be combined. For beads on a circle, the rotations form a group of n moves, one for each shift of 0 to n - 1. A reflection flips the circle over an axis. The rotations and reflections together form the dihedral group, which has 2n moves for n beads. Turning twice in a row is a rotation, so the group is closed under combination.
An orbit is the set of objects that one move can reach from each other. Two colourings of a necklace are in the same orbit when one is a rotation of the other. Counting necklaces means counting orbits.
A fixed point of a move g is an object that g leaves unchanged. A colouring is fixed by a rotation when every bead has the same colour as the bead it moves to.
A cycle of a move is a loop of positions the move passes through. A rotation by 2 on 6 beads sends bead 0 to 2, 2 to 4, 4 to 0, and bead 1 to 3, 3 to 5, 5 to 1. That gives two cycles of length 3.
A canonical form is one chosen representative of each orbit, for example the smallest string among the rotations of a colouring. Two colourings are the same necklace exactly when they have the same canonical form.
Burnside's lemma
Burnside's lemma says: the number of orbits equals the average number of fixed points over the moves.
number of orbits = (1 / |G|) times the sum over moves g in G of the number of objects fixed by g
Here |G| is the number of moves. The lemma is also called the Cauchy-Frobenius lemma. Burnside's 1897 book states it and credits Frobenius, so the name is a convention, and the result is older than either name suggests.
Why does it work? Count the pairs (g, x) where move g fixes object x. Count the same pairs in the other order. For a fixed object x, the moves that fix it form a subgroup, and the size of that subgroup times the size of x's orbit is |G|. So each orbit contributes exactly |G| pairs in total, and dividing by |G| gives one per orbit.
Check it on 4 beads with 2 colours. The rotations are shifts by 0, 1, 2, 3.
- Shift by 0 fixes everything: 2^4 = 16 colourings.
- Shift by 1 has one cycle of length 4, so all beads must match: 2 colourings.
- Shift by 2 has two cycles of length 2: 2^2 = 4 colourings.
- Shift by 3 is like shift by 1: 2 colourings.
The sum is 16 + 2 + 4 + 2 = 24, and 24 / 4 = 6. The six necklaces are 0000, 0001, 0011, 0101, 0111 and 1111, where 1 and 0 are the two colours.
Counting cycles
The key step is counting the fixed colourings of one move. A colouring is fixed by a move exactly when every cycle of that move is a single colour, because the beads in one cycle must all match. A move with c cycles therefore fixes k^c colourings when there are k colours. So the work for each move is to count its cycles.
For rotations, a shift by i on n beads has gcd(i, n) cycles, where gcd is the greatest common divisor. Each cycle has length n / gcd(i, n). For n = 4 and shift 2: gcd(2, 4) = 2, so 2 cycles. That is why shift 2 gives 2^2 = 4.
Summing over the n shifts and grouping by divisors gives the standard formula. Let e run over the divisors of n. There are phi(e) shifts with gcd(i, n) = n / e, where phi is Euler's totient, the count of numbers from 1 to e that share no factor with e. So:
necklaces(n, k) = (1 / n) times the sum over divisors e of n of phi(e) times k^(n / e)
Check n = 4, k = 2: divisors 1, 2, 4 with phi values 1, 1, 2 give 1 * 2^4 + 1 * 2^2 + 2 * 2^1 = 16 + 4 + 4 = 24, and 24 / 4 = 6.
For reflections, the count depends on whether n is odd or even.
- For odd n, every reflection axis passes through one bead and the midpoint of the opposite edge. It fixes 1 bead and pairs the other n - 1 beads into (n - 1) / 2 two-cycles. Total cycles: (n + 1) / 2.
- For even n there are two kinds. n / 2 axes go through two opposite beads. Each fixes 2 beads and pairs the other n - 2 beads into (n - 2) / 2 two-cycles, so n / 2 + 1 cycles in total. The other n / 2 axes go through midpoints of two opposite edges, pair up all beads, and have n / 2 cycles.
So bracelets, which allow turning and flipping, are:
bracelets(n, k) = (1 / (2n)) times (the rotation sum plus the reflection sum)
For n = 4, k = 2 the reflection sum is 2 * 2^3 + 2 * 2^2 = 16 + 8 = 24. The total is 24 + 24 = 48, and 48 / 8 = 6. The rotation sum and the reflection sum are different numbers in general, so do not add the reflection part to the necklace answer without dividing by 2n.
The code
The function necklaces_mod and bracelets_mod use the formulas above. They work for large n when the modulus is a prime bigger than n. The main function checks them against an explicit list of the moves and against a brute force over canonical forms.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;
ll pow_mod(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
if (a < 0) a += m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
// Euler's totient phi(e): how many numbers in 1..e are coprime to e. Trial division, O(sqrt e).
ll phi(ll e) {
ll result = e, x = e;
for (ll p = 2; p * p <= x; p++) {
if (x % p == 0) {
while (x % p == 0) x /= p;
result -= result / p;
}
}
if (x > 1) result -= result / x;
return result;
}
vector<ll> divisors(ll n) {
vector<ll> small, large;
for (ll d = 1; d * d <= n; d++) {
if (n % d == 0) {
small.push_back(d);
if (d != n / d) large.push_back(n / d);
}
}
for (auto it = large.rbegin(); it != large.rend(); ++it) small.push_back(*it);
return small;
}
// Burnside sum over the n rotations, modulo MOD: sum over e | n of phi(e) * k^(n / e).
ll rotation_sum_mod(ll n, ll k) {
ll s = 0;
for (ll e : divisors(n)) s = (s + phi(e) % MOD * pow_mod(k, n / e, MOD)) % MOD;
return s;
}
// Necklaces: rotations only. Divide the rotation sum by n.
ll necklaces_mod(ll n, ll k) {
return rotation_sum_mod(n, k) * pow_mod(n, MOD - 2, MOD) % MOD;
}
// Bracelets: rotations and reflections, so the sum is divided by 2n.
ll bracelets_mod(ll n, ll k) {
ll total = rotation_sum_mod(n, k);
if (n % 2 == 1) {
// Each reflection fixes one position and has (n - 1) / 2 two-cycles.
total = (total + n % MOD * pow_mod(k, (n + 1) / 2, MOD)) % MOD;
} else {
// n / 2 reflections through two positions: n / 2 + 1 cycles.
// n / 2 reflections through two edge midpoints: n / 2 cycles.
ll half = n / 2 % MOD;
total = (total + half * pow_mod(k, n / 2 + 1, MOD)) % MOD;
total = (total + half * pow_mod(k, n / 2, MOD)) % MOD;
}
return total * pow_mod(2 * n % MOD, MOD - 2, MOD) % MOD;
}
// ---------- Explicit moves, for checking the formulas ----------
// Number of cycles of a permutation of positions 0..n-1.
int count_cycles(const vector<int>& perm) {
int n = perm.size(), cycles = 0;
vector<bool> seen(n, false);
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
cycles++;
for (int j = i; !seen[j]; j = perm[j]) seen[j] = true;
}
return cycles;
}
// Rotations: position j goes to (j + i) mod n. Reflections: position j goes to (i - j) mod n.
vector<vector<int>> rotations(int n) {
vector<vector<int>> g;
for (int i = 0; i < n; i++) {
vector<int> p(n);
for (int j = 0; j < n; j++) p[j] = (j + i) % n;
g.push_back(p);
}
return g;
}
vector<vector<int>> reflections(int n) {
vector<vector<int>> g;
for (int i = 0; i < n; i++) {
vector<int> p(n);
for (int j = 0; j < n; j++) p[j] = ((i - j) % n + n) % n;
g.push_back(p);
}
return g;
}
// Exact integer power, for small values.
ll ipow(ll a, int e) {
ll r = 1;
for (int i = 0; i < e; i++) r *= a;
return r;
}
// Burnside: (1 / |G|) * sum over g of k^(cycles of g). Exact, for small n and k.
ll burnside_exact(const vector<vector<int>>& group, ll k) {
ll total = 0;
for (const auto& g : group) total += ipow(k, count_cycles(g));
return total / (ll)group.size();
}
// ---------- Brute force: canonical form ----------
// Smallest string among all rotations (and reflections, if flips is true).
string canonical(const string& s, bool flips) {
int n = s.size();
string best = s;
for (int i = 0; i < n; i++) {
string r = s.substr(i) + s.substr(0, i);
best = min(best, r);
if (flips) {
string rev(r.rbegin(), r.rend());
best = min(best, rev);
}
}
return best;
}
// Count distinct canonical forms over all k^n strings.
ll brute_count(int n, int k, bool flips) {
set<string> seen;
string s(n, '0');
ll total = 1;
for (int i = 0; i < n; i++) total *= k;
for (ll code = 0; code < total; code++) {
ll c = code;
for (int i = 0; i < n; i++) {
s[i] = char('0' + c % k);
c /= k;
}
seen.insert(canonical(s, flips));
}
return (ll)seen.size();
}
int main() {
cout << "n = 4, k = 2\n";
cout << " rotations: sum of 2^cycles = " << [&] {
ll t = 0;
for (auto& g : rotations(4)) t += ipow(2, count_cycles(g));
return t;
}() << ", necklaces = " << burnside_exact(rotations(4), 2) << "\n";
auto dihedral = rotations(4);
auto refl4 = reflections(4);
dihedral.insert(dihedral.end(), refl4.begin(), refl4.end());
cout << " rotations and reflections: bracelets = " << burnside_exact(dihedral, 2) << "\n\n";
// Formula against the explicit group, for n from 1 to 12 and k from 1 to 4.
bool formula_ok = true;
for (int k = 1; k <= 4; k++)
for (int n = 1; n <= 12; n++) {
auto rot = rotations(n);
auto all = rot;
auto ref = reflections(n);
all.insert(all.end(), ref.begin(), ref.end());
ll necklace_exact = burnside_exact(rot, k);
ll bracelet_exact = burnside_exact(all, k);
if (necklace_exact % MOD != necklaces_mod(n, k)) formula_ok = false;
if (bracelet_exact % MOD != bracelets_mod(n, k)) formula_ok = false;
}
cout << "Formulas match the explicit Burnside sums for n <= 12, k <= 4: " << (formula_ok ? "yes" : "no") << "\n";
// Brute force: canonical forms. Sizes are kept small enough to run quickly.
bool brute_ok = true;
for (int k = 1; k <= 4; k++) {
int limit = (k == 4) ? 10 : 12;
for (int n = 1; n <= limit; n++) {
if (brute_count(n, k, false) % MOD != necklaces_mod(n, k)) brute_ok = false;
if (brute_count(n, k, true) % MOD != bracelets_mod(n, k)) brute_ok = false;
}
}
cout << "Canonical-form brute force matches for the tested sizes: " << (brute_ok ? "yes" : "no") << "\n\n";
cout << "n necklaces bracelets (k = 2)\n";
for (int n = 1; n <= 12; n++)
cout << n << " " << necklaces_mod(n, 2) << " " << bracelets_mod(n, 2) << "\n";
return 0;
}Output from our run:
n = 4, k = 2
rotations: sum of 2^cycles = 24, necklaces = 6
rotations and reflections: bracelets = 6
Formulas match the explicit Burnside sums for n <= 12, k <= 4: yes
Canonical-form brute force matches for the tested sizes: yes
n necklaces bracelets (k = 2)
1 2 2
2 3 3
3 4 4
4 6 6
5 8 8
6 14 13
7 20 18
8 36 30
9 60 46
10 108 78
11 188 126
12 352 224The OEIS sequence A000029 lists bracelet counts for two colours. Its entry gives three bracelets for n = 2 and four for n = 3, which agree with our table.
The Python version below is short enough to read as a second implementation. It runs the sum directly over the n rotations instead of over divisors. It is fast for n up to a few thousand.
Output from our run:
n necklaces bracelets (2 colours)
1 2 2
2 3 3
3 4 4
4 6 6
5 8 8
6 14 13
7 20 18
8 36 30
9 60 46
10 108 78
11 188 126
12 352 224
3 colours, n = 4: 24 21Worked problem: bracelets with huge n
Statement (our own wording). A bracelet has n beads in a ring, and each bead gets one of k colours. Two bracelets are the same if one can be turned into the other by a rotation or a flip. Print the number of different bracelets, modulo 1000000007. The input is one line with two integers n and k, where 1 <= n <= 10^9 and 1 <= k <= 10^9.
Recognition. Count colourings up to a group that contains rotations and reflections. The group has 2n moves. Burnside applies.
Why the limits matter. n is too large to loop over the rotations one by one, so the solution uses the divisor form, which needs the divisors of n and the totient of each divisor. The modulus 1000000007 is prime and bigger than n, so the inverses of n and 2n exist. Even at the limit the divisor count stays small: 735134400, a number below 10^9, has 1344 divisors. Each divisor costs a trial division for its totient, which takes O(sqrt e) time.
Solution. The code is the bracelets function plus a main that reads the two numbers. It uses the same phi, divisors, and rotation_sum as the lesson code above.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;
ll pow_mod(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
if (a < 0) a += m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
// Euler's totient phi(e), by trial division.
ll phi(ll e) {
ll result = e, x = e;
for (ll p = 2; p * p <= x; p++) {
if (x % p == 0) {
while (x % p == 0) x /= p;
result -= result / p;
}
}
if (x > 1) result -= result / x;
return result;
}
vector<ll> divisors(ll n) {
vector<ll> small, large;
for (ll d = 1; d * d <= n; d++) {
if (n % d == 0) {
small.push_back(d);
if (d != n / d) large.push_back(n / d);
}
}
for (auto it = large.rbegin(); it != large.rend(); ++it) small.push_back(*it);
return small;
}
// Burnside sum over the n rotations, modulo MOD: sum over e | n of phi(e) * k^(n / e).
ll rotation_sum(ll n, ll k) {
ll s = 0;
for (ll e : divisors(n)) s = (s + phi(e) % MOD * pow_mod(k, n / e, MOD)) % MOD;
return s;
}
// Bracelets: (rotation sum + reflection sum) / (2n), modulo MOD.
ll bracelets(ll n, ll k) {
ll total = rotation_sum(n, k);
if (n % 2 == 1) {
total = (total + n % MOD * pow_mod(k, (n + 1) / 2, MOD)) % MOD;
} else {
ll half = (n / 2) % MOD;
total = (total + half * pow_mod(k, n / 2 + 1, MOD)) % MOD;
total = (total + half * pow_mod(k, n / 2, MOD)) % MOD;
}
return total * pow_mod(2 * n % MOD, MOD - 2, MOD) % MOD;
}
int main() {
ll n, k;
cin >> n >> k;
cout << bracelets(n, k) << "\n";
return 0;
}Compiled and run on sample inputs:
input [4 2] -> 6
input [3 2] -> 4
input [1 5] -> 5
input [2 3] -> 6
input [1000000000 1000000000] -> 638747898
input [999999999 2] -> 108780398
input [1000000000 2] -> 537849669The first four lines are small enough to check by hand. For n = 1 there is one bead, and the answer is k, because the only move is the identity and the flip does nothing new. For n = 2 the answer is (k^2 + k) / 2, the number of unordered pairs of colours with repetition. With k = 3 that is 6, which matches the output.
Test. We cannot brute force n = 10^9, so the test uses an independent second implementation. A Python script computes the exact integer count, not modulo anything, with the same formula, and then reduces it modulo 1000000007. We compared 66 inputs: the four small ones above, 60 random pairs with n up to 3000 and k up to 10^9, and two larger fixed pairs. Result: 0 mismatches. This test only confirms that the modular arithmetic and the divisor loop are right. The formula itself was checked against the explicit group sums and the canonical-form brute force for n up to 12 in the lesson code above.
Complexity. Time O(sqrt(n) + d(n) * sqrt(n)), where d(n) is the number of divisors of n. For n near 10^9 this is a few tens of millions of simple steps, well under a second. Memory is O(d(n)).
Common mistakes
Using k^n for each move. Symptom: for 4 beads and 2 colours the answer is 16 divided by 4, which prints 4, instead of 6. Each move fixes k^c colourings where c is the number of cycles, and only the identity has n cycles.
Using the odd reflection rule for even n. Symptom: bracelets for n = 4 and k = 2 print 5 instead of 6. If you use n times k^((n + 1) / 2) for all n, the reflection sum is 16 instead of 24, and 24 + 16 = 40, and 40 / 8 = 5. For even n you need the two kinds of axis.
Forgetting the division by |G|. The rotation sum for 4 beads and 2 colours is 24, not 6. Symptom: a number that is n times the right answer.
Overflow in k to the power d. Without the modulus inside the power loop, k^d for k = 10^9 overflows 64 bits almost at once. Take the modulus at every multiply, as pow_mod does.
Dividing by n when n is a multiple of the modulus. The inverse of n exists only when the modulus does not divide n. With the prime 1000000007 and n up to 10^9, this cannot happen. If you used 998244353 as the modulus instead, the input n = 998244353 would break the formula, because the modulus divides n. Check the limits against the prime.
Mixing up necklaces and bracelets. Symptom: n = 6 with 2 colours gives 14 instead of 13. Both answers are plausible, so the only safe check is an explicit list of the moves for small n.
Assuming symmetry is always the dihedral group. A square board with colours on its cells has a different group, and the same method applies, but the cycle counts change. Write down the moves first, then count the cycles.
Checklist
- Write the group of moves before anything else. Rotations give n moves, rotations plus reflections give 2n.
- For each move, count its cycles. Each cycle must be one colour, so the fixed count is k to the power of the cycle count.
- For reflections, split the even case into axes through two beads and axes through two edges.
- Check the sum is divisible by |G|, using exact integers on small inputs. If it is not, a cycle count is wrong.
- Compare the formula with an explicit list of the moves for n up to about 12.
- Compare the formula with a canonical-form brute force for n up to about 10 when k is 4, or 12 when k is 3.
- Use a prime modulus bigger than the largest n, so that the inverses exist.
- Read the statement for the group: "turn" means rotation only, "turn or flip" means dihedral.
Exercise
Count coloured necklaces of length n with k colours, for n from 1 to 12 and k from 1 to 4. Use Burnside, with the divisor formula. Then verify with a canonical-form brute force: for each string of k^n colourings, compute its smallest rotation, and count the distinct results. Print one line per (n, k) pair with both counts and a flag for any mismatch. The brute force has to be a separate function, so the check is not the formula checking itself.
Prompt to use with an AI tool, if you want help:
Write C++17 code that counts coloured necklaces of length n with k colours, where two
necklaces are the same if one is a rotation of the other. Use Burnside's lemma with
the divisor formula: sum over divisors e of n of phi(e) * k^(n/e), divided by n.
Compute phi by trial division. Then write a separate brute force that enumerates all
k^n strings, replaces each by its smallest rotation, and counts the distinct results.
Print one line per (n, k) for n from 1 to 10 and k from 1 to 3, with both counts and
whether they match. Use only the standard library.A good answer keeps the brute force independent of the formula, uses exact integers for small n, and handles n = 1 and k = 1 (the answer is 1 for k = 1). Check its output for n = 4 and k = 2: it should print 6. If the tool's formula gives 4 for that case, it has used k^n instead of the cycle count. If its brute force uses the same formula to compare, ask for a version that does not.
Your own table is the answer key. The 2-colour values in this lesson are a reference for n up to 12.
Practice problems
Problem 1. Count the necklaces of 6 beads with 2 colours, and the bracelets of 6 beads with 2 colours.
Hint: The table in this lesson lists both values for n = 6.
Show the answer
Necklaces: 14. Bracelets: 13. The bracelet count is smaller because a flip can make two necklaces the same bracelet.
Problem 2. Count the bracelets of 5 beads with 3 colours.
Hint: The rotation sum is 3^5 + 4 * 3 = 255, and each of the 5 reflections fixes one bead and has 3 cycles. Divide the total by 2n = 10.
Show the answer
- The rotation sum is 255. The reflection sum is 5 * 3^3 = 135. The total is 390, and 390 / 10 = 39. The Python formula above prints 39 as well.
Problem 3. A square has a colour on each corner, and there are 3 colours. Count the colourings up to rotation and reflection of the square.
Hint: This is the bracelet count for n = 4 and k = 3. Use the even-n rule for the reflections.
Show the answer
- The rotation sum is 3^4 + 3 + 9 + 3 = 96. The reflections give 2 * 3^3 + 2 * 3^2 = 72. The total is 168, and 168 / 8 = 21.
Problem 4. A row of 6 beads has 3 colours. Count the necklaces (rotation only), and then the bracelets (rotation and flip).
Hint: Use the Python functions above with n = 6 and k = 3.
Show the answer
Necklaces: 130. Bracelets: 92. The Python sample computes both, and the bracelet count is smaller as in Problem 1.
Summary
Burnside's lemma says the number of distinct objects up to a group of moves is the average number of fixed objects over the moves. For colourings, a move fixes k to the power of its cycle count, so the work is to count cycles. For rotations of n beads, the sum collapses to a divisor formula with Euler's totient, and reflections add a rule that depends on whether n is odd or even. The formulas are short, and the explicit group sum and a canonical-form brute force for small n are the two checks that catch a wrong cycle count.