Necklace Counting (draft)

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.

The Idea

The basic idea behind this approach is to view a size-12 binary necklace as an interleaving of two smaller necklaces built from partitions of two integers summing to 12. I’ll try to explain this by describing a process for assembling a necklace from scratch:

1. First, decide how many white beads to include in your necklace. Call this n. Obviously, the number of black beads will be 12-n. (n and 12-n are the two numbers we’ll be partitioning later.)
2. Now decide how many separate “clumps” the white beads will fall into. I’m using the term “clump” to mean a sequence or strip of beads of one color (with no beads of the other color between them). Call the number of white clumps c. It’s possible to see that the number of black clumps must be the same as the number of white clumps, unless the necklace is all-black or all-white.
3. Now decide how many beads will go into each clump. For the white beads, this is the same as choosing an integer partition of n with c parts (that is, a way of writing n as the sum of c positive integers). For the black beads, select an integer partition of 12-n with c parts.
4. Now treat each integer in the partitions from step 3 as a distinct type (or “color”) of bead, and arrange each partition into a necklace of c beads. The number of possibilities here will depend on the number of colors in each necklace, and how many beads there are of each color: later, we’ll refer to these two pieces of information together as the “necklace type.” At the end of this step, we have two necklaces, one of which will contribute all the white beads to our final necklace, and the other of which will contribute all the black beads.
5. Take the two c-bead necklaces from step 4 and interleave them. This means that you’ll create a single 2_c_-bead necklace by taking one bead from the first necklace, then one bead from the second, then one bead from the first, then one bead from the second, until you’ve used up all the beads in both necklaces. In doing this, you’ll need to choose a position on each necklace to start pulling the beads from, and you have to pull the beads from each necklace in a clockwise order.
6. Finally, take each integer-labeled bead in the interleaved necklace from step 5 and “expand” it into the corresponding number of black or white beads, giving a 12-bead binary necklace.

The Idea Illustrated

Here’s an example of how the process works.  In Step 1, we choose how many white beads to include in our necklace.  Let’s go with six white beads, meaning there will also be six black beads:

In Step 2, we choose a number of clumps (we’ll go with three), and in Step 3 we partition the white and black beads into that many clumps.  Here we’ll break the white beads into clumps of size 3, 2, and 1, and we’ll break the black beads into clumps of size 4, 1, and 1:

In Step 4, we form necklaces from the clumps.  There are two distinct necklaces we can make from the white clumps, and there’s only one necklace we can make from the black clumps.  The arrow indicates the white necklace that we’ll choose:

In Step 5, we interleave the white and black necklaces.  There are 3 distinct interleavings possible between the white necklace we selected above and the only black option; the arrow indicates which of those interleavings we’ll choose:

In Step 6 we expand our fused beads back into individual beads, giving this particular one of the 352 possible binary necklaces of size 12:

If you go back through these steps, it should be easy to verify that making any of our choices in a different way would necessarily have yielded a different necklace in the end.

The Idea Illustrated Backwards

Now let’s try the process in reverse. We’ll start with a binary necklace such as would be obtained in Step 6, and then we’ll break it apart into its pieces so as to unwind the previous steps.

Let’s consider a different necklace from before–we’ll use a necklace which corresponds to the major scale and its modes.  (If white represents a scale tone and black represents an excluded tone, the interval pattern here starting from 12 o’clock is whole-whole-semi-whole-whole-whole-semi):

First we’ll collapse each clump, reversing Step 6.  Here we’ll use numbered beads as opposed to rectangular “jumbo” beads like we did above, but the idea is the same:

Now we’ll break the “interleaved” necklace above into two separate necklaces, reversing step 5:

Finally we can see that our two necklaces 21211 and 11111 (formed in step 4) were based on partitions 2+2+1+1+1=7 and 1+1+1+1+1=5 (chosen in step 3), and of course we must have chosen c=5 (in step 2), and n=7 (in step 1).

The Idea Iterated: Steps 1-3

Now if we want to enumerate all possible size-12 binary necklaces, we just need to iterate Steps 1 through 6, making the choices at each step in every possible way; as we do this, we’ll see that it’s not hard to size up the full range of possibilities at each step. Furthermore, we’ll be able to “save” some of the work we do in Steps 4 and 5 and reuse it when we return to those steps the next time.

To save time, observe that we never need to explore necklaces with more than 6 white beads. Once we’re done generating all the necklaces with up to 6 white beads, we can find the necklaces with more than 6 white beads by simply taking the complements all of the necklaces with fewer than 6 white beads (here, “taking the complement” means swapping white beads with black, and vice versa). So, each necklace that we visit with <6 white beads will contribute 2 to our total count (1 for the necklace itself, 1 for its complement); while each necklace with exactly 6 beads will only contribute 1 to the total count.

Now, looking at Step 1, we have the option to include 0, 1, 2, 3, 4, 5, or 6 white beads, and in Step 2 we can choose any number of clumps that’s less than or equal to the number of white beads. This table shows all of the possible partitions of n and 12-n into c parts, where 0<n<=6 and c<=n. All of the choices that can be made in Steps 1 through 3 are represented in this table.

Here’s the same information in a diagram:

The Idea Iterated: Step 4

In the previous section we looked at all the choices that can be made in Steps 1 through 3 of our procedure: all the ways of choosing a number of n of white beads, a number c of clumps, and a pair of integer partitions of n and 12-n into c parts each.  Now we’re going to consider all possible ways of taking those pairs of partitions, arranging each partition into a necklace (Step 4 of our procedure), and finally interleaving the necklaces (Step 5 of our procedure, covered in the next section).

The obvious way to proceed would be to consider all the pairs of white and black partitions that can be made from any single row of our table.  We could consider each pair separately (for example, let’s take the pair 4+1+1 and 3+2+1), create all possible necklaces for each member of that pair (eg. {411} and {321, 312}), and then create all the interleavings of those necklaces (e.g. 431211, 421113, 411312, 431112, 411213, 421311), repeating this process until we’ve exhausted all the pairs.

However, we can save work by observing that the same types of necklaces, and hence the same types of necklace pairs, occur repeatedly in the table.  Once we’ve done the work of finding all interleavings of two particular necklace types, we can reapply that work wherever we encounter those same necklace types in a partition pair.

What exactly do we mean by necklace type?  A partition like 4+1+1 contains two distinct integers (4 and 1) which we can think of as two distinct bead colors. There’s 1 bead of the first color and 2 beads of the second color. So we’ll say any necklace formed from 4+1+1 would be a necklace of type 2/1.  (We’ll adopt a convention of writing the necklace type in order starting from the most frequent to the least frequent color, so we’ll write 2/1 here instead of 1/2.)  Can you find another partition in the table that falls into the 2/1 necklace type?  The partition 3+1+1 fits the bill, as again there are two distinct integers (this time 3 and 1) and there’s 1 of one kind and 2 of the other kind. You won’t see it in this table, but 200+25+25 would be another example fitting the 2/1 necklace type.  Going back to our example, we’ll call all the interleavings formed from necklaces of 4+1+1 and 3+2+1 a _type 2/1 x 1/1/1 interleaving (_or a type 2/1 x 1/1/1 necklace).

Here are the last two columns from the table of partitions above, with each partition now annotated with its necklace type in red:

Looking at the table, we can see there are only 14 necklace types at play here, and each of them generates only a few simple necklace instances.  For example, if we consider the 2/1/1 necklace type, this means there are two beads of one color, call it X, one bead of another color, call it Y, and one bead of a third color, call it Z. There are only three ways of arranging these beads into distinct necklaces: XXYZ, XXZY, and XYXZ. (Here I’m representing a necklace as a string like XXYZ – you should imagine those beads on a circle from which you could also read them as XYZX, YZXX, ZXXY – all equivalent to XXYZ.) Here is a summary of the necklace types we’re dealing with, and their corresponding necklace instances in string form:

Looking back at our table of partitions, we can see that certain kinds of interleavings occur in our space of possibilities, while others don’t. For example, we’ve already seen that 4+1+1 and 3+2+1 make a type 2/1 x 1/1/1 interleaving, and so do 3+1+1 and 4+2+1.  But you won’t find any type 2/2 x 2/1/1 interleavings in the table.

The Idea Iterated: Step 5

Our next step will be to consider all of the interleaving types represented in our partition table and list all possible instances of each interleaving type.

For simple interleaving types, the instances are obvious.  For example, let’s consider the 3x3 interleaving type.  There’s only one necklace of type 3, which we’ll write as XXX, and there’s only one way we can interleave it with another necklace of type 3, which we’ll write as AAA.  This single instance of 3 x 3 could be written as XAXAXA.  But, when the interleaving types get more complex, how can we find all the possibilities?  The brute force approach would to look at every pair of instances of the two necklace types, and apply the following procedure: keep one necklace fixed, and place the second necklace on top of it so that the beads of the second necklace fall into the gaps between the beads of the first; then rotate the second necklace clockwise in steps of one bead, until we’ve visited all possible positions around the circle.  Finally, eliminate interleavings that turn out to be rotationally equivalent.

Do we actually need to rotate the second necklace so it lands in every possible position, and then go through the elimination step?  No.  Let’s say first necklace can be decomposed into repeating blocks of a fixed size, like ABC (i.e. the entire necklace is ABCABCABC) while the second necklace cannot be decomposed into repeating blocks of a fixed size smaller than the necklace itself (say the necklace is XXXXXXXXY). You’d only need to rotate the second necklace through the length of one repeating block of the first necklace.  I will leave a discussion of this principle for a separate post.

Now, it turns out that there are 28 distinct interleaving types that occur in our partition table, listed below with all their instances, and all the partition pairs that fall into each type.  (Note: some of this table is currently TBD, but I think you’ll get the idea.)

The Idea Iterated: Step 6

The next step is to make all possible necklaces from each partition pair in the table above: we can do this by substituting the partition members into the precomputed necklaces of the appropriate type.  For example, let’s return to the pair (4+1+1, 3+2+1) that we considered before.  This pair is of type 2/1 x 1/1/1, and our table tells us the possible interleaved necklaces of that type are: XAXBYC, XCXAYB, XBXCYA, XAXCYB, XBXAYC, XCXBYA.  If we take X=1, Y=4, A=3, B=2, C=1 we get necklaces 131241, 111342, 121143, 131142, 121341, 111243. The requirement for setting up our substitutions is that if a letter X in occurs m times in each precomputed necklace, we need to map it to an integer that occurs m times in the partition it belongs to.

The final step is to unpack the integers in each necklace into the corresponding number of white or black beads.  Our necklace 131241, for example, would translate into white-black-black-black-white-black-black-white-white-white-white-black, or 100010011110.

If we go through this process for every partition pair in the table, and then add all the complements of necklaces with <6 white beads, we’ll get all 352 binary necklaces of size 12.  I might post them here at some point when I’m feeling up to it, but now you know one way to find them yourself (and if you don’t want to go through the labor, you can get your free necklaces here or here).  Well, I didn’t say this approach would make the enumeration easy or free from tedium, but I think it does provide a systematic process for doing it, along with a compact way of describing the structure of any necklace you encounter.

Recap: Intuition?

My main reason for going on this excursion was not that I had a pressing practical need to enumerate necklaces, but that I wanted a better intuitive understanding of the space of possibilities: I wanted to get a feel for how necklaces “arise” and how their structure can be analyzed.  Have I succeeded in obtaining, and hopefully sharing, such intuition?

Well, now if you see a necklace like 100110011100, you can view it as an “expansion” of the necklace 122232, which is built from the partition pair (1+2+3, 2+2+2), and you can observe that this pair is of type 1/1/1 x 3.  You could observe that there are in fact two interleavings of type 1/1/1 x 3 (they are XAYAZA and XAZAYA), and that 123222 (or 100111001100) is a “close relative” of the given necklace.  Finally you could observe that these two necklaces are special in that they happen to be the only interleavings of type 1/1/1 x 3 in the problem space.

Followup Questions

This section includes some followup questions which I’d like to address when I have time: hopefully soon, but quite possibly never.  I will be motivated to get around to them before never if you drop me a note letting me know what topics you’d like to see explored here, or how you think this post could be improved.

1. Can this approach be made into a recursive algorithm for generating binary necklaces of arbitrary size?  The catch is that in Step 4, we need to find necklaces of more than two colors; in this post where we were specifically dealing with 12-bead necklaces, it was possible to build these component necklaces by hand.  If we wanted to do it with a recursive call to the procedure, we’d need to generalize the procedure to handle necklaces with an arbitrary number of colors.  Perhaps this could be done using an encoding scheme where binary necklaces of a larger size get mapped to necklaces with fewer beads and more colors?
2. How does this approach relate to other necklace algorithms in the literature and does it offer any advantages?
3. Is it possible to find some kind of conceptual mapping between the steps of this procedure and the things that happen “inside” the Polya Enumeration Theorem.
4. How can this approach be applied in the context of combinatorial music theory, if at all?