How many melodies are there in the universe?

After writing "Is music written or discovered?" I started thinking a little bit harder about how one might go about searching for new musical discoveries. specifically, short little melodies.

So I started wondering how many melodies of a given length are out there. Clearly it is a finite number. So I have set out to try to count them, or at least put an upper bound on their number.

First we have to limit things in some way, we can't allow infinitely long melodies. So, I'll arbitrarily draw the line at 32 notes, or rather, 1 measure's worth of 1/32 notes.

There are 12 notes total (in the Western scale, which for some very good reasons which I can't actually recall, has been shown to be the "best" scale, overall. There are other scales, but they all suffer from more problems than the 12 note scale does. The math seems to end up favoring the 12 note scale.) I will also ignore intervals larger than 1 octave, just because.

Further, each note may transition to the next note in a number of ways, "normally" (separately plucked and fretted), by sliding, by hammer-on by pull-off. I will allow for the possibility of sliding from a note to itself which enables 1/16th notes, 1/8th notes, (and even 3/8th notes).

So what does that leave?

Choose 1 note from 12, 32 times, and choose one of four methods of transitioning to the next note, 31 times.

Damn that's a big number.

1232 x 431:

% bc -l
4^31 * 12^32


I can probably divide that number by twelve because it would count each riff played in each key, and I would really only want to count each riff in one key. (Yeah, that helps).

12^31 * 4^31

Hmm, I still don't feel like I've accomplished anything. What is stil missing is a way to toss out even some proportion of the riffs as being "non-musical", I know there are plenty of non-musical riffs counted in there, but I have no idea how to toss them out.

Hmm, lets say I only allow two methods of transitioning between notes. After all, riffs that differ only by using a pull-off or a hammer-on vs. an ordinary plucking style aren't really all that different, it's more a matter of how well the riff is performed than a matter of it being a different riff altogether. I still have to allow for sliding though, to allow for the possibility of different time values for the notes and still have everything add up to just one measure.

So that would be:

12^31 * 2^31

A little better, but still a freakin' huge number, and I'm still counting too many duplicate riffs that differ only by "sliding" vs. normal plucking.

So thinking about it a little differently, for the first note, there, are 12 choices. For the remaining 31 notes, you really have 13 choices, you can just allow the previous note to continue uninterupted, or you can start new note, from a choice of 12. And once again, I can divide by 12 to limit each riff to one key.

So that gives us:

12 * 13^31 / 12

One problem I still see, most music has whole notes, half notes, quarter notes, eighth notes, sixteenth notes, and 32nd notes, which I have allowed for, but I have also allowed for 3/8th notes, 7/8th notes, etc... Well those would typically be written as a quarter note note tied to an eighth note, or a half note tied to a quarter note tied to an eighth note respectively, so I suppose I have to allow them.

But, suppose we limit things so that notes can only be 32nds, 16ths, 8ths, 4ths, halves, or whole notes, that is, no "3/8th" notes, no triplets, or other weird Chopin-esque stuff. (Chopin would do weird things like have the left hand play 17 notes in one measure while the right hand had to play 13 in the same amount of time, 17 against 13. What a bastard.)

Anyway, what would that kind of convenient blindness leave?

I imagined a measure, which you chop up in a number of pieces (at most 32 pieces) and as you cut it up, you could make as many as 31 cuts, or as few as zero, and each cut would have to slice one of the remaining pieces exactly in half. Being rather bad at combinatorics and discrete math I wrote a little brute force C program:

#include < stdio.h>

struct measure
        int length;
        struct measure *left, *right;

ways_to_cut(struct measure *m, int cuts)

        long ways_cut = 0;
        long left_cut;
        long right_cut;
        struct measure m1, m2;

        int i;

        if (m->length <= cuts) return(0L);
        if (cuts == 0) return(1L);
        if (cuts == 1) return 1L;

        m1.length = (m->length >> 1);
        m2.length = (m->length >> 1);
        m->left = &m1;
        m->right = &m2;


        for (i=0;i<=cuts;i++)
                left_cut = ways_to_cut(m->left, i);
                right_cut = ways_to_cut(m->right, cuts-i);
                ways_cut += left_cut * right_cut;


int main(int argc, char **argv)
        long wtc;
        struct measure m;
        int i;
        long total=0L;

        m.left = NULL;
        m.right = NULL;
        m.length = 32;

        for (i=0;i < 32;i++)
                wtc = ways_to_cut(&m, i);
                total += wtc;
                printf("ways to make %d cuts = %ld\n", i, wtc);

        printf("Total ways to cut: %ld\n", total);

And the output:

ways to make 0 cuts = 1
ways to make 1 cuts = 1
ways to make 2 cuts = 2
ways to make 3 cuts = 5
ways to make 4 cuts = 14
ways to make 5 cuts = 42
ways to make 6 cuts = 100
ways to make 7 cuts = 221
ways to make 8 cuts = 470
ways to make 9 cuts = 958
ways to make 10 cuts = 1860
ways to make 11 cuts = 3434
ways to make 12 cuts = 6036
ways to make 13 cuts = 10068
ways to make 14 cuts = 15864
ways to make 15 cuts = 23461
ways to make 16 cuts = 32398
ways to make 17 cuts = 41658
ways to make 18 cuts = 49700
ways to make 19 cuts = 54746
ways to make 20 cuts = 55308
ways to make 21 cuts = 50788
ways to make 22 cuts = 41944
ways to make 23 cuts = 30782
ways to make 24 cuts = 19788
ways to make 25 cuts = 10948
ways to make 26 cuts = 5096
ways to make 27 cuts = 1932
ways to make 28 cuts = 568
ways to make 29 cuts = 120
ways to make 30 cuts = 16
ways to make 31 cuts = 1
Total ways to cut: 458330

Pipe that through a short filter:
./cuts | awk '/ways to make/ { printf("%d * 12 ^ (%d+1)\n", $7, $4 );}' | bc -l

which yields a very pretty sequence:


the sum of which is some kind of answer:
./cuts | awk '/ways to make/ { printf("%d * 12 ^ (%d+1)\n", $7, $4 );}' |\ bc -l | ( awk 'BEGIN { printf("0 ");} { printf(" + %s ", $0); }' ;\ echo ) | bc -l

Ok, so if you listened to one measure per second, how long could you go without repeating a measure?

% bc -l

That's 3916514807686766283344588049 YEARS folks!

Jebus help me!

So there you have it. Boy was this node a waste of time or what? But it does demonstrate how cool awk and bc are.