Musical and combinatorial proof

Question

How many distinct rhythms can a musical measure have?

Obviously the answer is not "$\infty$", so to answer this question we set a minimum rhythm $\frac{1}{4}$. We will consider both notes and rests and not consider irregular groups like triplets and others. So we'll consider notes and rests as $\frac{1}{4 }$, $\frac{2}{4}$, $\frac{3}{4 }$ ... As regards musical measure we'll consider $\frac{L}{4}$ where $L$ is the length of measure and consider only $L>0$. Then calculate the number of combinations of rhythms in a measure:

So the sequence found is: $1,2,5,13,34,...$ and this is a possible relation with Fibonacci's bisection: $$ F(0)=1 $$ $$ F(1)=2 $$ $$F(L)= 3 \cdot F(L-1) - F(L-2); \quad L>1$$ How is it possible to proof that this recurrence relation is valid for each $L>1$?

IMPORTANT EDIT: Sorry i have forgotten to write that we consider rhythms from the acoustic view point, so we consider for example that two rests of $\frac{1}{4}$ acoustically equal to a rest of $\frac{2}{4}$ and so we will consider only the rest of $\frac{2}{4}$.
Furthermore rhythms of arbitrary duration are allowed, for example we can have a note of $\frac{5}{4}$ with a invented symbol.

Answer 1

There are three cases:

• A rhythm ends with something which lasts longer than a quarter note. There are $F(n-1)$ of these: we can get each of them by taking an arbitrary rhythm of length $n-1$ and lengthening the last symbol by one beat.
• A rhythm ends with a quarter note. Then anything can come before the quarter note, so there are also $F(n-1)$ of these.
• A rhythm ends with a quarter rest. Then the next-to-last symbol must continue with a note and not a rest (as we are not allowed to have two uncombined adjacent rests). The number of rhythms of length $n-1$ which end with a rest is $F(n-2)$, as any one of them can be obtained by performing a rhythm of length $n-2$ and then resting for a quarter-beat. So there are $F(n-1)-F(n-2)$ rhythms of length $n-1$ which do not end in a rest.

This gives the order 2 recurrence relation $$ F(n)=3F(n-1)-F(n-2) $$ as you conjectured.

---

Another way to split things up that may be easier to think about:

• We might end with a rest of any length. In this case we can perform an arbitrary rhythm of length $n-1$ and then rest for a beat. So there are $F(n-1)$ possibilities.
• We might end with a quarter note. Again in this case we can perform an arbitrary rhythm of length $n-1$ and then a quarter note, so there are $F(n-1)$ possibilities.
• Finally, we might end with a longer note (not a rest). Then we can shorten this note by $1$ beat, to get an arbitrary rhythm of length $n-1$ that ends with a note. As in the first bullet point, there are $F(n-2)$ rhythms of length $n-1$ that end with a rest, so there are $F(n-1)-F(n-2)$ rhythms of length $n-1$ that end with a note.

Answer 2

Here's a different proof, which makes the connection to the Fibonacci numbers explicit as well as using some basic musical concepts. If people have trouble with unicode musical notes, let me know and I'll try to replace them with images, but they have fairly low code points, so hopefully it'll be okay as is. (Rests seem to be more poorly supported, so I'm using images for the examples at the end which involve them.)

The standard combinatorial interpretation of the Fibonacci numbers is that $f_k$ (suitably indexed) counts the number of ways of tiling a path of length $n$ with tiles of length either $1$ or $2$. In musical terms, $f_k$ counts the number of possible rhythms which are $k$ eighth-notes long, using only eighth notes and quarter notes (and no rests). If we let the quarter note have the beat and consider sequences which are $n$ beats long, it follows that there are $f_{2n}$ such sequences — the same number as there are of the types of rhythm you are trying to count.

Given this observation, it's very natural to look for a bijection between these two types of rhythm. And in fact we can find one.

Any sequence of quarter and eighth notes can be divided into:

• Syncopated sections: These consist of an eighth note that falls on the quarter-note beat (i.e., is preceded by an even number of eighth notes), followed by some number of quarter notes, followed by an offbeat eighth note (e.g., ♪♩♩♩♪).
• Unsyncopated sections: These consist of some number of quarter notes, all of which fall on the quarter-note beat (♩♩♩♩♩$\dots$).

Each of these sections takes up an integer number of quarter-note beats. Note that it is convenient for our purposes to regard a pair of adjacent eighth notes on the beat (♫) as a very short syncopated section, even though in musical terms it would not be considered syncopated.

Note that it is possible for one syncopated section to follow another (e.g., ♪♩♩♪♪♩♩♩♪). But if you concatenate two unsyncopated sections, you just get a single longer unsyncopated section (e.g., ♩♩ + ♩♩♩ = ♩♩♩♩♩). This is exactly analogous to the unrestricted rhythms in the question! In that case, you can play two notes in sequence, but if you "play" two rests in sequence, you just get a longer rest.

So our bijection will work as follows: given a sequence of eighth notes and quarter notes, we replace each syncopated section with a single note of the same length, and each unsyncopated section by a rest of the same length. Going in the other direction, if we have a sequence of notes and rests, all of which are some integer number of quarter-notes long, replace each note with a syncopated section of the same length, and each rest with an unsyncopated section of each length. These are clearly well-defined and inverse to each other, which completes the proof.

For concreteness, here are the $n=2$ examples of this bijection (quarter notes and eighth notes in the first measure of each line, longer notes and rests in the second measure):

and a longer example: