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

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!

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

[news] - [media] - [humanity] - [humor] - [information]

[music] - [theory] - [programming] -