The Problem
A combinatorial necklace is an arrangement of colored beads on circle (or circular string). Imagine the necklace is lying flat on a table and you can’t pick it up to turn it over. Two necklaces are considered equivalent if there’s a way to rotate one necklace so that its beads align with those of the other. (Another way to say this is that you could find positions on each necklace so that if you started at those positions and called out the bead colors in clockwise order, the two sequences of colors would be identical.) So, how many distinct 12-bead necklaces could you create if you had an unlimited supply of black and white beads? That’s the problem we’ll address in this post.
I’m interested in such black/white or binary necklaces because they correspond to musical constructs like chord types or scale families. If you want to know, for example, how many distinct chord types there are in 12-tone equal temperament (where a chord type may have any number of notes from 0 to 12), this turns out to be equivalent to the question we just posed about necklaces.
In mathematical discussions of musical chords and scales, when “the necklace question” comes up, it’s usually addressed in one of two ways. Some authors present an exhaustive list of necklaces/chords/scales obtained by brute force (presumably, the author wrote a computer program to generate all 2^12 binary strings and eliminate pairs of strings that represent equivalent necklaces). Other authors point out that you can obtain a count of the necklaces by invoking a piece of mathematical machinery called the Polya Enumeration Theorem. Feed some numbers into Polya’s formula and we learn that there are 352 binary necklaces of size 12.
When I started thinking about necklaces I was looking for something that neither approach seemed to provide: I wanted to gain an intuitive understanding of how the possibilities arise. Where do those 352 necklaces “come from,” and why aren’t there more of them, or fewer of them, for that matter? Presumably, such intuition could be obtained by exploring the inner workings of the Polya Enumeration Theorem, but I was looking for a more direct path, using only elementary mathematical concepts, so I started trying to devise a method that would help me list all the necklaces by hand, without having to explore and eliminate duplicates. It turns out there are a number of algorithms for generating necklaces in the literature, including one due to Fredricksen, Kessler and Maiorana, and more recent work by Cattell, Ruskey, Sawada, and Serra. The method I came up with is different from approaches I’ve seen elsewhere, so I’ve decided to present it here in hopes that the right reader might find it interesting. In this post, I’m not aiming to present it as a general purpose algorithm for enumerating necklaces of arbitrary size (to do this would require some refinement) or to analyze its performance in contrast to the other algorithms — I’m just offering it as an interesting way to generate and/or categorize the possibilities for size-12 necklaces, a way that hopefully provides some intuition into the problem space, and that is amenable to execution by hand for those crazy enough to want to do it. That said, I’d be interested to collaborate with anyone who thinks this approach could be expanded into something more generally useful, or who could point out where it might already have been explored.
Rudi Seitz 