Necklace Counting (draft)

June 9, 2013
Mathy Stuff, Music
1 Comment

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 2c-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:

NecklaceExample1

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:

NecklaceExample2

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:

NecklaceExample3

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:

NecklaceExample4

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:

NecklaceExample5

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):

necklace-counting-1

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:

necklace-counting-2

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

necklace-counting-3

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.

# white beads + # black beads # clumps possible white partitions possible black partitions
0+12 0/1 12
1+11 1 1 11
2+10 1 2 10
2+10 2 1+1 9+1, 8+2, 7+3, 6+4, 5+5
3+9 1 3 9
3+9 2 2+1 8+1, 7+2, 6+3, 5+4
3+9 3 1+1+1 7+1+1, 6+2+1, 5+3+1, 5+2+2, 4+3+2, 3+3+3
4+8 1 4 8
4+8 2 3+1, 2+2 7+1, 6+2, 5+3, 4+4
4+8 3 2+1+1 6+1+1, 5+2+1, 4+3+1, 4+2+2, 3+3+2
4+8 4 1+1+1+1 5+1+1+1, 4+2+1+1, 3+3+1+1, 3+2+2+1, 2+2+2+2
5+7 1 5 7
5+7 2 4+1, 3+2 6+1, 5+2, 4+3
5+7 3 3+1+1, 2+2+1 5+1+1, 4+2+1, 3+3+1, 3+2+2
5+7 4 2+1+1+1 4+1+1+1, 3+2+1+1, 2+2+2+1
5+7 5 1+1+1+1+1 3+1+1+1+1, 2+2+1+1+1
6+6 1 6 6
6+6 2 5+1, 4+2, 3+3 5+1, 4+2, 3+3
6+6 3 3+2+1, 4+1+1, 2+2+2 3+2+1, 4+1+1, 2+2+2
6+6 4 3+1+1+1, 2+2+1+1 3+1+1+1, 2+2+1+1
6+6 5 2+1+1+1+1 2+1+1+1+1
6+6 6 1+1+1+1+1+1 1+1+1+1+1+1

Here’s the same information in a diagram:

partitions

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:

white partitions black partitions
12 (1)
1 (1) 11 (1)
2 (1) 10 (1)
1+1 (2) 9+1 (1/1), 8+2 (1/1), 7+3 (1/1), 6+4 (1/1), 5+5 (2)
3 (1) 9 (1)
2+1 (1/1) 8+1 (1/1), 7+2 (1/1), 6+3 (1/1), 5+4 (1/1)
1+1+1 (1/1/1) 7+1+1 (2/1), 6+2+1 (1/1/1), 5+3+1 (1/1/1), 5+2+2 (2/1), 4+3+2 (1/1/1), 3+3+3 (3)
4 (1) 8 (1)
3+1 (1/1), 2+2 (2) 7+1 (1/1), 6+2 (1/1), 5+3 (1/1), 4+4 (2)
2+1+1 (2/1) 6+1+1 (2/1), 5+2+1 (1/1/1), 4+3+1 (1/1/1), 4+2+2 (2/1), 3+3+2 (2/1)
1+1+1+1 (4) 5+1+1+1 (3/1), 4+2+1+1 (2/1/1), 3+3+1+1 (2/2), 3+2+2+1 (2/1/1), 2+2+2+2 (4)
5 (1) 7 (1)
4+1 (1/1), 3+2 (1/1) 6+1 (1/1), 5+2 (1/1), 4+3 (1/1)
3+1+1 (2/1), 2+2+1 (2/1) 5+1+1 (2/1), 4+2+1 (1/1/1), 3+3+1 (2/1), 3+2+2 (2/1)
2+1+1+1 (3/1) 4+1+1+1 (3/1), 3+2+1+1 (2/1/1), 2+2+2+1 (3/1)
1+1+1+1+1 (5) 3+1+1+1+1 (4/1), 2+2+1+1+1 (3/2)
6 (1) 6 (1)
5+1 (1/1), 4+2 (1/1), 3+3 (2) 5+1 (1/1), 4+2 (1/1), 3+3 (2)
3+2+1 (1/1/1), 4+1+1 (2/1), 2+2+2 (3) 3+2+1 (1/1/1), 4+1+1 (2/1), 2+2+2 (3)
3+1+1+1 (3/1), 2+2+1+1 (2/2) 3+1+1+1 (3/1), 2+2+1+1 (2/2)
2+1+1+1+1 (4/1) 2+1+1+1+1 (4/1)
1+1+1+1+1+1 (6) 1+1+1+1+1+1 (6)

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:

necklace type instances
1 X
2 XX
3 XXX
4 XXXX
5 XXXXX
6 XXXXXX
1/1 XY
2/1 XXY
3/1 XXXY
4/1 XXXXY
2/2 XXYY, XYXY
3/2 XXXYY, XYXYX
1/1/1 XYZ, XZY
2/1/1 XXYZ, XXZY, ZYXZ

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 3×3 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.)

Interleaving Type White Necklaces Black Necklaces Interleavings Partition Pairs Of This Type
2/1 x 2/1 XXY AAB XAXAYB, XAXBYA, XBXAYA (2+1+1, 6+1+1), (2+1+1, 4+2+2), (2+1+1, 3+3+2), (3+1+1, 3+1+1), (3+1+1, 3+3+1), (3+1+1, 3+2+2), (2+2+1, 5+1+1), (2+2+1, 3+3+1), (2+2+1, 3+2+2), (4+1+1, 4+1+1)
2/1 x 1/1/1 XXY ABC, ACB XAXBYC, XCXAYB, XBXCYA, XAXCYB, XBXAYC, XCXBYA (3+1+1, 4+2+1) (2+2+1, 4+2+1), (4+1+1, 3+2+1), (2+1+1, 5+2+1), (2+1+1, 4+3+1)
1/1/1 x 2/1 XYZ, XZY AAB XAYAZB, XBYAZA, XAYBZA, XAZAYB, XBZAYA, XAZBYA (3+2+1, 4+1+1)
4 x 3/1 XXXX AAAB XAXAXAXB (1+1+1+1, 5+1+1+1)
4 x 2/1/1 XXXX AABC XAXAXBXC, XAXAXCXB (1+1+1+1, 4+2+1+1), (1+1+1+1, 3+2+2+1)
4 x 2/2 XXXX AABB, ABAB XAXAXBXB, XAXBXAXB (1+1+1+1, 3+3+1+1)
4 x 4 XXXX AAAA XAXAXA (1+1+1+1, 2+2+2+2)
3/1 x 2/1/1 XXXY AABC,AACB, ABAC XAXAXBYC, XAXBXCYA, XBXCXAYA, XCXAXAYB, XAXAXCYB, XAXCXBYA, XCXBXAYA, XBXAXAYC, XAXBXAYC, XBXAXCYA, XAXCXAYB, XCXAXBYA (2+1+1+1, 3+2+1+1)
3/1 x 3/1 XXXY AAAB XAXAXAYB, XAXAXBYA, XAXBXAYA, XBXAXAYA (2+1+1+1, 4+1+1+1), (2+1+1+1, 2+2+2+1), (3+1+1+1, 3+1+1+1)
3/1 x 2/2 XXXY AABB, ABAB XAXAXBYB, XBXAXAYB, XBXBXAYA, XAXBXBYA, XAXBXAYB, XBXAXBYA (3+1+1+1, 2+2+1+1)
2/2 x 3/1 XXYY, XYXY AAAB XAXAYAYB, XAYAYAXB, YAYAXAXB, YAXAXAYB, XAYAXAYB, YAXAYAXB (2+2+1+1, 3+1+1+1)
5 x 4/1 XXXXX AAAAB XAXAXAXB (1+1+1+1+1, 3+1+1+1+1)
5 x 3/2 XXXXX AAABB, ABABA XAXAXAXBXB, XAXBXAXBXA (1+1+1+1+1, 2+2+1+1+1)
4/1 x 4/1 …. …. …. ….
6 x 6 …. …. …. ….
1/1/1 x 1/1/1 …. …. …. ….
2/1 x 3 …. …. …. ….
2/2 x 2/2 …. …. …. ….
_ x 1 …. …. …. ….
1 x 1 …. …. …. ….
2 x 1/1 …. …. …. ….
1/1 x 1/1 …. …. …. ….
3 x 3 …. …. …. ….
3 x 2/1 …. …. …. ….
3 x 1/1/1 …. …. …. ….
1/1/1 x 3 …. …. …. ….
2 x 2 …. …. …. ….
1/1 x 2 XY AA XAYA (3+1, 4+4), (5+1, 3+3), (4+2, 3+3)

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?

Microtonal Notation and Playback In Finale

May 14, 2013
Music, Tech Support
1 Comment

I’ve been searching for information on how to notate microtonal music in Finale and get it to play back properly.  Since it’s hard to find good documentation on this, I wanted to share my findings.  (As a side note, I’ve come across a number of forum posts by people saying they only want to do microtonal notation and they don’t care about playback.  Really?)  Here’s the easiest approach that I’ve found so far, working with Finale 2012:

Step 1: Create a Nonstandard Key Signature with your preferred number of subdivisions of the octave, and assign accidental symbols as you like.  The best explanation of how to do this I’ve found is in this PDF by Ere Lievonen.

Step 2: Set up the Aria player that comes with Finale to use a Scala file that defines your tuning.  For this, you’ll need a recent version of the Aria player, since Scala integration seems to be a newer feature.  The basic process is as follows:

  • Set MIDI/Audio->Play Finale Through Audio Units
  • Open this dialog: MIDI/Audio->Audio Units Banks & Effects
  • Click the pencil icon for Bank 1 to open the Audio Unit Viewer
  • Select Settings from the tabs on the right and look for the area labeled Tuning
  • Import your chosen Scala file

That’s it (for this summary, at least).

Of course, if you only want to experiment with nonstandard tunings that have 12 notes per octave, you can skip Step 1 and go right to Step 2, selecting your Scale file in Aria Player.  There are a couple of Scala files included in the Aria installation, and you can download many more at the Scala site.  The neat thing is that if you do want more than 12 notes per octave, Step 1 and Step 2 work well together: if your nonstandard key signature has, say, 24 notes per octave and your Scala file has 24 notes, they’ll be matched during playback.  (This is how it should work, of course, but until I tested it tonight I wasn’t sure it actually would work.)  You can get any one of those 24 notes to play back properly by applying the appropriate accidental as you defined in Step 1.  It’s no longer necessary to use the older technique of creating pitch bend expressions.

I’ve just begun playing with this and will update this post as I learn more.

Twelve Glyph Challenge

May 1, 2013
Music, Visual Design
Leave a Comment

Challenge: design glyphs to represent the numbers one through twelve.

Consider the numbers arranged on a clock face.  Your glyph system should have the following properties:

  1. The glyphs for two numbers that are opposite on the clock face (like 12 and 6) should have some visual qualities that bind them together as a pair.
  2. If you look at the glyphs for any two numbers that are adjacent on the clock face (like 1 and 2), it should be easy to see which glyph represents the “lower” number in clockwise order, and which glyph represents the “higher” number.
  3. The glyphs for any three numbers that form an even division of the clock face into three parts (like 12, 4, and 8) should have some common visual feature that makes them recognizable as a group.
  4. The glyphs for any four numbers that form an even division of the clock face into four parts (like 12, 3, 6, and 9) should have some common visual feature that makes them recognizable as a group.
  5. The parity of a number (whether the number is odd or even) should be somehow discernible from its glyph.

Thinking of this problem in musical terms, the glyphs could represent the 12 notes of the octave (assuming 12TET).  Looking at any glyph, you should be able to quickly discern the following things about the note it represents: which of the four augmented triads does the note belongs to?  Which of three fully-diminished seventh chords does it belong to?  What is its tritone, and what is that tritone’s glyph? What are its upper and lower chromatic neighbors, and what are their glyphs?

I haven’t solved this.  But, to jog your imagination, here’s one of many glyph systems I’ve come up with while considering the problem.  Do you think it has any nice properties?  Can you do better?

12 Glyphs

Jam Session — 3/18/2013

March 18, 2013
Music, Photography
Leave a Comment

I asked my friend Dan Koff of New Relic Media to help me make a video about my photography.  We wanted to do our own soundtrack so we met today for our second jam session, which was lots of fun.  Some of this material will probably make it into the video, but we decided we just wanted to make some music and not force it to fit.  In these clips, Dan is playing in his own style on a dholak that Kathir and I got from a street vendor in Pondicherry a few years ago.  I’m playing on my Eastman archtop.  (Amplification is new for me, as I generally prefer completely “unplugged” playing, but the Acoustic Image Corus I’m using at a low level here is changing my mind and opening some new possibilities.)  Both clips are improvised without rehearsal, though the first one (15 minutes) is more structured — it explores the “Charupriya” concept that I’ve been developing recently:

This second clip (20 minutes) was pure experiment.  It takes a little while to get into a groove, but one of my favorite parts is the craziness that ensues between 3:00 and 4:00, and resurfaces again towards the end:

Read More

cantu a tenore newsflash

March 15, 2013
Music
Leave a Comment

I used to go to record stores–back when there still were record stores–with the sense that my life could change depending what I stumbled across.  One such moment was discovering cantu a tenore, a style of vocal music from Sardinia, which I first heard at a listening station in Tower Records in 1996: the album was S’amore ‘e Mama by Tenores di Bitti.  Of course, it wasn’t so much the particulars of my life that changed in hearing this (or any other powerful recording), as it was my ear, and my sense of possibility.  The guttural sonorities of cantu a tenore were unlike anything I had experienced in music before, although they reminded me of sounds I had heard in the natural world, in particular the bleating of sheep and the lowing of cows.  Sardinian singers evoke these ambient animal sounds in a way that is startling and beautiful.  I call it “startling” because, to a mainstream listener (I’ll punt on trying to define “mainstream” here) the sounds of livestock probably occupy a separate mental category from “music,” and if one is familiar with the loose concept of bel canto singing (an operatic style favoring smoothness or legato, lightness, and agility) the bleating of sheep could be seen as its diametrical opposite.  How interesting to consider that Italy, which gave us bel canto, also gave us cantu a tenore.  I call it “beautiful” not only because of the visceral appeal of its sonic “mass,” but also because the voices sustain a sort of rhythmic, melodic, and timbral contrast that gives me the same rush I get from more formal contrapuntal music: at times it’s like hearing a bit of Bach somehow waft up from the grounds of a farm.

After ’96 I would always check for the “Sardinia” section whenever I stopped in a record store, and if I found such a section, it was usually stocked with the recording I already owned.  Through the sort of physical-world-sleuthing that was necessary in those days, I did gradually expand my collection to five or six albums, but at some point I had to concede that there just wasn’t much to do as an American fan of Sardinian polyphony: no new releases, no local performances, and practically no one in my circle of acquaintance who had heard of it.  So I stopped checking for “news.”  But just the other day some fortuitous web browsing led me the best Sardinian-polyphony news I’ve come across in a decade.   There’s a group of American singers, Tenores de Aterúe, who have taken the adventurous step of studying and performing traditional cantu a tenore, and their footage on YouTube sounds great.  (Where’s your website, guys?)  In reading a little about their background, I enjoyed the story of a 2008 ephiphany, when one member who had dreamed of learning Sardinian music found a video of Tenores di Bitti demonstrating how each voice part in cantu a tenore sounds by itself, and then in ensemble.  This video became a sort of Rosetta stone that exposed the workings of the music and opened the path for a group of experienced but non-Sardinian musicians to actually learn it.  I encourage you check out Tenores de Aterúe on YouTube and see if they might be performing near you (I’ll be doing the same).  Here, I wanted to post that revealing Tenores di Bitti video, as it’s probably the best short introduction to cantu a tenore one can find (replete with charming features like the onlooker who appears in the background near 3:50, and of course, some great singing).
When I sent it to my classical voice teacher, she emailed back: “This just blew my mind.”  Specifically, she was amazed at how these musicians create — in a way that appears relaxed and free from vocal strain — a completely different set of sounds from those we work to produce in “mainstream” Western vocal practice.

Janya Ragas: 34,776 or 26,864?

March 15, 2013
Music
13 Comments

Prasanna mentioned to me that there are 34,776 theoretically possible janya ragas in the South Indian melakarta system and he asked if I could see how that number arises. I looked into the question and thought I’d post the details here for anyone who’s interested.

Recall that a janya raga is one that is somehow derived from one of the 72 melakarta ragas. The 34,776 figure refers to one specific class of janya ragas: those that are created by omitting notes from the parent. In forming such “varja” ragas, we can omit up to two notes from the arohanam (ascent), the avarohanam (descent), or both. (And it’s permissible to omit different notes in the ascent from those we omit in the descent.) We can’t apply other processes of derivation like reordering notes or borrowing notes from other ragas: these processes lead to many more possibilities!

So where does the number 34,776 come from?  Well, if we decide to omit one note from the arohanam of a melakarta raga, there are 6 ways to do it: any note besides sa is fair game for omission. If we’re going to omit two notes, there are (6 choose 2) = 15 possibilities. And of course, if we omit no notes, there’s only 1 way to do that. This gives 6+15+1=22 options. The same 22 options exist for the avarohanam, giving 22*22=484 ways of omitting notes from a parent raga to create a janya. Except, we don’t want to count the case where no notes are omitted in the arohanam and the avarohaman both, because this leaves us with the original raga. So, the total number of janya possibilities for each melakarta raga is actually 484-1 = 483. Multiplying this by the total number of melakarta ragas, we get 483*72 = 34,776. But there’s a catch…

The process of omitting notes from two distinct parent ragas can give us two janya ragas with the same notes. For example, we can get S R2 G3 P D2 (Mohanam), by omitting M1 and N2 from S R2 G3 M1 P D2 N2 (Harikambhoji), or by omitting M2 and N3 from S R2 G3 M2 P D2 N3 (Kalyani). In Western terms, one would say you can get 1 2 3 5 6 (major pentatonic) by omitting 4 and b7 from 1 2 3 4 5 6 b7 (Mixolydian) or by omitting #4 and 7 from 1 2 3 #4 5 6 7 (Lydian). So, the 34,776 figure contains many janya ragas that actually have identical swaras. Now, if the parent raga (including its mood, characteristic phrases, ornamentation patterns, and additional swaras) is kept in mind when performing the derived raga, then two ragas derived from different parents might be perceived as distinct even though the derived ragas happen to have the same notes. In this way of looking at raga derviation, 34,776 is a plausible theoretical count. However, if we’re only interested in janya possibilities that are distinct in their notes, and we’re not considering attachments to parent ragas, then 34,776 is an overcount.

Enumerating the janya possibilities that are note-wise distinct is more complicated. The rest of the post describes an approach I came up with when I first started thinking about the problem.  After I published the post, I received a comment from Narayana Santhanam pointing out that the technique of generating functions from enumerative combinatorics is another, more compact approach to counting janyas; and, in searching further, I found a 2002 paper by K. Balasubramanian that uses this approach.  Finally, I learned that P. Sriram and V. N. Jambunathan had investigated this question and published similar findings in a 1991 paper in the Journal of the Madras Music Academy.  (See the notes and comments at the end of this post for more details.)  Although the approach I present here is more verbose than some of the others, I hope it will be interesting to readers looking for insight into how all the possibilities arise.

In what follows, I assume R2=G1, R3=G2, D2=N1, and D3=N2 even though one could say those swaras would be performed with different ornamentation and/or intonation.  In this count, for example, an arohanam of S R2 M1 P D2 S will be considered equivalent to S G1 M1 P D2 as since we treat R2=G1.

To organize our count, we’ll consider how many notes occur in the union of the ascent and the descent of a janya raga. This union might have 5, 6 or 7 notes.

If the union contains 5 notes, then the ascent and descent must contain those same 5 notes. To find the number of janya ragas of this kind, we need to consider all the ways of choosing 4 notes from 11 possibilities without violating the melakarta rules. Note that we’re choosing 4 notes out of 11, not 5 out of 12, because one note, sa, is mandated. Unfortunately, we can’t use a simple formula for (11 choose 4) because this would count “illegal” cases where there are two ma’s, or where there are more than two notes betwen sa and ma.  One way to count only the legal possibilities is to divide the scale above sa into four sections. The first section contains ri and ga. The second section contains ma. The third section contains pa. The fourth section contains da and ni. Now there are 6 ways of filling the first section (i.e. ri and ga can be R1/G1, R1/G2, R1/G3, R2/G2, R2/G3, or R3/G3), two ways of filling the second section (i.e. ma can be M1 or M2), one way of filling third section (pa is always Pa), and six ways of filling the fourth section.  (This is how we get 6*2*1*6 = 72 melakarta ragas.) If we omit some notes, then one or more of the scale sections will no longer be full. (In particular, if the first section has only one note in it, there are 4 possibilities for its identity: R1, R2=G1, R3=G2, or G3.) If we write 2|1|1|2 to indicate a scale with all sections full, then here are the possibilities distributions of sections sizes for a five-note derived scale where the sections are not all full: 2|1|1|0, 2|0|1|1, 2|0|0|2, 2|1|0|1, 1|1|1|1, 1|0|1|2, 1|1|0|2, 0|1|1|2. Taking this list and substituting the sections sizes with the number of ways of filling each section to the designated size, we get the following count: 6*2*1*1 + 6*1*1*4 + 6*1*1*6 + 6*2*1*4 + 4*2*1*4 + 4*1*1*6 + 4*2*1*6 + 1*2*1*6 = 236.

Now if the union of the ascent and descent contains 6 notes, the respective sizes of the ascent/descent might be 6/6, 5/6, 6/5, or 5/5. The 6/6 case is similar to above: we know the ascent and descent use the same six notes, and we need to consider the number of ways of choosing 5 out of 11 notes without violating the melakarta rules. Following the logic above, the possible distributions of section sizes are 1|1|1|2, 2|0|1|2, 2|1|0|2, and 2|1|1|1. This gives 4*2*1*6 + 6*1*1*6 + 6*2*1*6 + 6*2*1*4 = 204 possibilities. In the 5/6 or 6/5 case, we can see that side containing 5 notes must be a proper subset of the side containing 6. The number of possibilities here can be calculated as (# ways of choosing 5 out of 11 notes legally)*(# ways of removing one of those 5 notes to create the smaller side) = 204*5 = 1020. Since we can make the smaller side the ascent or the descent, we multiply the last figure by two, giving 2040. Finally, in the 5/5 case, we can see that the ascent and descent must share precisely 4 notes including sa (each side contains a note that’s not in the other, creating a union of size 6). The number of possibilities can be calculated as (# ways of choosing 5 out of 11 notes legally, to create the 6-note union including Sa)*(# ways of picking 3 notes from those 5 to be shared by the ascent and descent)*(# ways of picking one of the remaining 2 notes to be in the ascent, while the other goes in the descent) = 204*(5 choose 3)*2 = 4080.

The last situation is where the union of the ascent and descent contains 7 notes. Here, the respective sizes of the ascent/descent might be 5/5, 6/5, 5/6, 6/6, 5/7, 7/5, 6/7, or 7/6.  In the 5/5 case, the intersection must contain 3 notes. The number of possibilities is: (# of ways of choosing 6 out of 11 notes following the melakarta rules, to create a 7-note parent raga including Sa)*(# ways of choosing 2 out of those 6, to create a 3-note intersection including Sa)*(# ways of picking two from outside the intersection to be in the ascent, while the other 2 go in the descent) = 72*(6 choose 2)*(4 choose 2) = 72*15*6 = 6480. In the 5/6 or 6/5 case, the intersection is size 4, and we can choose 3 out of six notes to form it. By similar logic to the previous case, the number of possibilities is 72*(6 choose 3)*(3 choose 2) = 72*20*3 = 4320 for each case by itself.  In the 6/6 case the intersection must be size 5, and the number of possibilities is 72*(6 choose 4)*2 = 72*15*2 = 2160. In the 5/7 and 7/5 cases, the smaller side of the scale must be a proper subset of the larger one, and we can form the smaller side by omitting two out of six notes from the larger. This gives 72*(6 choose 2) = 1080 possibilities for each case. And in the 6/7 and 7/6 cases, the smaller side again must be a proper subset of the larger one, so the number of possibilities is 72*(6 choose 1) = 432 for each case.

Here’s a recap of the cases we considered and the possibilities that exist in each case:

Union size 5.  Case 5/5: 236 possibilities.

Union size 6.  Case 6/6: 204 possibilities. Cases 5/6 and 6/5: 2040 possibilities together. Case 5/5: 4080 possibilities.

Union size 7.  Case 5/5: 6480 possibilities. Cases 5/6 and 6/5: 8640 possibilities together. Case 6/6: 2160 possibilities. Cases 5/7 and 7/5: 2160 possibilities together. Cases 6/7 and 7/6: 864 possibilities together.

The grand total is 236+204+2040+4080+6480+8640+2160+2160+864= 26864.

Now, how can we be sure that 26864 correct? In fact, I made many calculation errors as I was working through this the first time, leaving me in a state of great suspicion.  However, after I spotted and corrected my mistakes, I gained further confidence by writing a Groovy script that generates all distinct janya possibilities by brute force, and also yields… 26864!  (Warning: this is script-style code, meant for one-time use and not designed to be maintainable or easy to read, but it gets the job done.)

// this script is written in Groovy 2.1.0

// generate all melakarta ragas, representing each
// raga as a list of 11 ones and zeros
melakartas = []
for (riGa in [1,1,0,0].permutations()) {
    for (ma in [0,1].permutations()) {
        for (daNi in [1,1,0,0].permutations()) {
            melakartas.add(riGa + ma + [1] + daNi)
        }
    }
}
assert melakartas.size()==72

// generate all ways of deleting up to two notes from
// the ascent and descent of a raga
deletions = ([0..5,0..5].combinations()).collect( {it as Set} ) as Set
deletions.add([])
deletionPairs = [deletions,deletions].combinations()
deletionPairs.remove([[],[]])

// generate all possible janyas as ascending/descending scale pairs,
// by applying all possible deletions to each melakarta raga;
// keep the janyas in a set so that identical janyas will
// not be double-counted
janyas = [] as Set
for (mela in melakartas) {
    def noteIndices = (0..(mela.size()-1)).findAll({mela[it]==1})
    for (deletionPair in deletionPairs) {
        def ascending = mela.clone()
        def descending = mela.clone()
        deletionPair[0].each { ascending[noteIndices[it]]=0 }
        deletionPair[1].each { descending[noteIndices[it]]=0 }
        janyas.add([ascending, descending])
    }
}

println "Number of Distinct Janyas: ${janyas.size()}"

Read More

A Musical Meditation

March 1, 2013
Music
Leave a Comment

This clip is the outline or “seed” of a composition I’m working on.  The seed is nothing but a sequence of ascending and descending scales over a fixed bass, arranged in a cycle that returns to the starting point. I arrived at it through a fairly theoretical process (see my other posts with geometric diagrams of the octave to get a sense for the kind of stuff I’ve been up to). But for me, it’s one of those cases where an essentially mathematical idea, translated into sound, produces something that’s eerily compelling. For my ear this pattern is prism-like: it seems to unlock a whole spectrum of colors and moods, and at times it has held me in a trance. I’m posting it here for two reasons: first, even though it’s just a bare pattern, I hope you might find it interesting to listen to as a sort of musical meditation. Second, I’ve found that in many of my creative projects, when I get excited about an idea, I form great ambitions around it and keep it to myself until I feel I’ve done it justice. This has led to many cases in my life where I’ve poured effort and passion into a project but never released it because my goals were too big for me. So I’m trying a different approach, which is to share things early, especially when I come upon something that strikes me as a gem–something that I might otherwise get lost in polishing endlessly. So here is “Charupriya Cycle,” played on my steel string guitar a few hours after the idea came together the other day:

Follow

Get every new post delivered to your Inbox.

Join 321 other followers

%d bloggers like this: