Burnside's Lemma & Pólya Enumeration

Average the fixed colorings over every symmetry → the number of distinct necklaces

|Fix(g)| = k^(#cycles) #orbits = (1/|G|) Σ |Fix(g)| Necklace: (1/n) Σd|n φ(d) k^(n/d)

Necklace under symmetry

cycle arc
beads forced equal (one cycle)

Controls

Slow Fast

Live Burnside accumulation

Symmetry
0 / 0
#cycles c(g)
0
|Fix(g)| = k^c
0
Σ |Fix|
0
|G|
0
avg = #orbits
—
Press Play to sweep through each symmetry, or Step one at a time. Each symmetry's |Fix(g)| = k^(#cycles) is added; the running average is the orbit count.

Complexity

OperationTimeNotes
Count cycles of one symmetryO(n)visited-array walk
|Fix(g)| = k^(c(g))O(log c)fast power
General Burnside loopO(|G|·n)over all group elements
Necklace closed formO(√n)(1/n)Σd|nφ(d)k^(n/d)
Brute-force orbit countO(k^n·n)oracle only

Operation Log