Music Math

Yesterday, Feb 18, 1999, I was thinking about music. From my experience, the sequence of durations of notes in a melody are often as unique as the melody itself. "The heart of rock and roll is the beat," I muttered. The question presented itself: If I could have at most x beats in a melody, how many different combinations of note durations can I squeeze out?

Here comes the math.

Let x be an element of the Natural numbers. I am trying to find all combinations of natural numbers such that the sum of these numbers is x. The order of these numbers is significant.

Here are the numbers 1 through 5 broken down in such a manner:

1	2	3	4	5
1	1 + 1 2	1 + 1 + 1 2 + 1 1 + 2 3	1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 2 + 2 3 + 1 1 + 3 4	1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 3 + 1 + 1 1 + 3 + 1 1 + 1 + 3 3 + 2 2 + 3 4 + 1 1 + 4 5

It appears that the number of combinations that sum to x is 2^{x - 1}. Why is this? Well, let's think about it for a moment. A different way to represent the problem will show us the answer. Let # mean that we add 1 to the previous number in a list. For example, {1,#,1,1,1} is another means of representing {2,1,1,1} and {1,1,#,#,1} is another way of representing {1,3,1}. Using this method we can see that every combination can be represented. Let us note that each element can have only 2 values (1 and #) except for the first element which has to be a 1. From this information we can derive that the number of possible combinations is 2^{x - 1}, where x is the number of elements.

Not enough for you? Look:
Let f_k be the k^th element of the fibbonacci sequence, {1,1,2,3,5,..}. If one is only allowed the use of 1 and 2 to additively compose x, the number of combinations appears to be f_{(x + 1)}

Not nifty enough for you? Here is something else: For every x, count the number of candidates that have 1 member. Count those that have 2 members... and so on. I'll do it for you:

	1	2	3	4	5
1	1
2	1	1
3	1	2	1
4	1	3	3	1
5	1	4	6	4	1

The rows indicate our x. The columns show how many combinations that sum to x have y elements, where y is the number at the top of the column. If we look in row 5, column 3, we can see that there are 6 different combinations of numbers with 3 members that sum to 5.

Do you see the pattern? It's Pascal's Triangle!

BRIARSKIN

[news] - [media] - [humanity] - [humor] - [information]
[music] - [theory] - [programming] - [web design]