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
157637523953697211105908171958186454333476434685722624
```

Wow!

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
13136460329474767592159014329848871194456369557143552
```

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
6117141027690268863066571918245810640257024
```

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
34059943367449284484947168626829637
```

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;
};

long
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;

cuts--;

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;
}

return(ways_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:

```12
144
3456
103680
3483648
125411328
3583180800
95025954816
2425096765440
59316834926592
1381995569479680
30617888939311104
645810987668078592
12926491101077962752
244416990259238141952
4337569597936449355776
71878562636176677666816
1109074817815117490552832
15878155968719959464345600
209883024546529473038647296
2544451171947419448687722496
28038096359484820776730755072
277867979924918797194422648832
2447071950614776964115597361152
18877003349528376284550493372416
125327733578312106466500182802432
700040332826172993664543220563968
3184798876813578234913416410038272
11235812186522437499570313794420736
28485157655972376759474034971770880
45576252249555802815158455954833408
34182189187166852111368841966125056
```

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
123511210975209861511554928715787036

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

```% bc -l
123511210975209861511554928715787036/3600/24/365
3916514807686766283344588049
```

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.