8 Counting Necklaces — Burnside’s Lemma Visualized
How many distinct necklaces can you make with \(n\) beads and \(k\) colors, if two necklaces that differ only by rotation are considered the same? What if flipping the necklace over also counts as “the same”?
The answers come from Burnside’s lemma and the cycle index polynomial — tools from group theory that turn symmetry into a counting formula.
The key idea: a group acts on colorings by permuting bead positions. Two colorings in the same orbit — reachable from each other by group elements — are the same necklace. Burnside’s lemma counts orbits without enumerating them.
(ns harmonica-book.counting-necklaces
(:require
[scicloj.harmonica :as hm]
[tablecloth.api :as tc]
[scicloj.tableplot.v1.plotly :as plotly]
[scicloj.kindly.v4.kind :as kind]))We’ll use rotation-action and dihedral-vertex-action as point actions on bead positions, then lift them to colorings with hm/coloring-action.
(defn rotation-action [n]
(fn [g x] (mod (+ x g) n)))(defn dihedral-vertex-action [n]
(fn [[t k] x]
(case t
:r (mod (+ x k) n)
:s (mod (- k x) n))))Drawing Necklaces
Before we count, let’s learn to draw. A necklace is a circle of colored beads — we’ll represent it as a Plotly scatter plot with beads at equally spaced angles.
(defn necklace-traces
"Plotly traces for a single necklace centered at (cx, cy) with radius r.
coloring is a vector of color indices, e.g. [0 1 0 1]."
[coloring cx cy r]
(let [n (count coloring)
bead-colors ["#e74c3c" "#3498db" "#2ecc71" "#f39c12" "#9b59b6" "#e67e22"]
angles (mapv (fn [i] (- (* 2 Math/PI (/ (double i) n)) (/ Math/PI 2)))
(range n))
bxs (mapv (fn [a] (+ cx (* r (Math/cos a)))) angles)
bys (mapv (fn [a] (+ cy (* r (Math/sin a)))) angles)]
[{:type "scatter" :mode "lines"
:x (conj (vec bxs) (first bxs))
:y (conj (vec bys) (first bys))
:line {:color "#bdc3c7" :width 1}
:showlegend false :hoverinfo "skip"}
{:type "scatter" :mode "markers"
:x (vec bxs) :y (vec bys)
:marker {:size 16
:color (mapv #(get bead-colors % "#7f8c8d") coloring)
:line {:color "#2c3e50" :width 1}}
:showlegend false :hoverinfo "skip"}]))(defn necklaces-row
"Draw necklaces in a single horizontal row."
[colorings & {:keys [title bead-radius spacing width height]
:or {bead-radius 0.35 spacing 1.2}}]
(let [nc (count colorings)
w (or width (max 250 (long (* nc spacing 85))))
h (or height 120)
traces (vec (mapcat (fn [i c]
(necklace-traces c (* spacing (+ i 0.5)) 0 bead-radius))
(range) colorings))]
(kind/plotly
{:data traces
:layout (cond-> {:xaxis {:visible false :scaleanchor "y"}
:yaxis {:visible false}
:width w :height h
:margin {:t (if title 35 10) :b 10 :l 10 :r 10}}
title (assoc :title title))})))(defn necklaces-grid
"Draw necklaces in a grid. `rows` is a seq of seqs of coloring vectors.
Each inner seq becomes one horizontal row."
[rows & {:keys [title bead-radius spacing width height row-labels]
:or {bead-radius 0.35 spacing 1.2}}]
(let [max-cols (apply max (map count rows))
n-rows (count rows)
w (or width (max 300 (long (* (+ max-cols (if row-labels 1.5 0)) spacing 80))))
h (or height (max 150 (long (* n-rows spacing 90))))
label-offset (if row-labels 1.5 0)
necklace-traces*
(vec (for [[ri row] (map-indexed vector rows)
[ci coloring] (map-indexed vector row)]
(necklace-traces coloring
(* spacing (+ ci 0.5 label-offset))
(* spacing (- (dec n-rows) ri))
bead-radius)))
all-traces (vec (apply concat necklace-traces*))
label-traces (when row-labels
(mapv (fn [ri label]
{:type "scatter" :mode "text"
:x [(* spacing 0.6)]
:y [(* spacing (- (dec n-rows) ri))]
:text [label]
:textfont {:size 11 :color "#2c3e50"}
:showlegend false :hoverinfo "skip"})
(range) row-labels))]
(kind/plotly
{:data (vec (concat all-traces label-traces))
:layout (cond-> {:xaxis {:visible false :scaleanchor "y"}
:yaxis {:visible false}
:width w :height h
:margin {:t (if title 35 10) :b 10 :l 10 :r 10}}
title (assoc :title title))})))The Setup
A “necklace” with \(n\) beads and \(k\) colors is an equivalence class of colorings under rotation. Two colorings are the same necklace if one can be rotated into the other.
The cyclic group \(C_n\) acts on colorings by rotating all bead positions. Two colorings in the same orbit under this action are the same necklace.
Brute Force for Small Cases
Let’s start with \(n = 4\) beads and \(k = 2\) colors. There are \(2^4 = 16\) colorings total.
(let [n 4
G (hm/cyclic-group n)
{:keys [domain act]} (hm/coloring-action (rotation-action n) n 2)
orbs (hm/orbits G act domain)]
(kind/table
{:column-names ["Orbit #" "Size" "Representative"]
:row-vectors (mapv (fn [i orb]
[(inc i) (count orb) (str (first (sort orb)))])
(range) (sort-by #(first (sort %)) orbs))})) clojure.core/eval core.clj: 3232
...
harmonica-book.counting-necklaces/eval122033 REPL Input:
scicloj.harmonica.action/orbits action.clj: 35
scicloj.harmonica.action/orbit action.clj: 24
scicloj.harmonica.protocols/eval102277/fn/G protocols.clj: 14
clojure.core/-cache-protocol-fn core_deftype.clj: 585
java.lang.IllegalArgumentException: No implementation of method: :elements of protocol: #'scicloj.harmonica.protocols/FiniteGroup found for class: scicloj.harmonica.group.cyclic.CyclicGroup