Pólya Enumeration

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

When two arrangements count as "the same" under symmetry, naive counting overcounts. Burnside's lemma fixes it: the number of distinct objects equals the average number of arrangements left unchanged by each symmetry. Pólya's theorem packages this for colorings.

Average over the symmetry group

Count colorings, then average over all symmetries the number each one fixes. For a necklace of n beads under rotation, the rotation by d fixes exactly c^gcd(d,n) colorings with c colors. Average over all n rotations and you have counted necklaces, not strings.

Scheme

(define (gcd2 a b)
  (if (= b 0) a (gcd2 b (modulo a b))))

; Burnside over the cyclic group: necklaces of n beads, c colors, up to rotation.
; rotation by d fixes c^gcd(d,n) colorings; average over the n rotations.
(define (necklaces n c)
  (let loop ((d 0) (sum 0))
    (if (>= d n)
        (/ sum n)
        (loop (+ d 1) (+ sum (expt c (gcd2 d n)))))))

(display "2-color, 4 beads = ") (display (necklaces 4 2)) (newline)  ; 6
(display "2-color, 6 beads = ") (display (necklaces 6 2)) (newline)  ; 14
(display "3-color, 4 beads = ") (display (necklaces 4 3)) (newline)  ; 24

Neighbors

🔗 Abstract Algebra — Burnside counts orbits of a group action
🧮 Ch.1 Counting Foundations — what overcounting means, now corrected

← Graph Theory · 8 of 10 by june.kim Probabilistic & Extremal Methods · 10 of 10 →