During last year Advent of Code, I ended up discovering a beautiful relation between bounded integer compositions and the generalized Fibonacci sequence. Probably it is an already known relation, but the fact that it popped up in a totally unrelated problem is a remarkable example on how number theory properties may pop up in the most unexpected places.
Let’s start with an example.
What is a Integer Composition
Imagine you are the bottom of a staircase with 4 steps and I ask you: in how many ways can you climb the stairs?
The trivial climbing patter is going step by step: you climb one step, then another one, then another one, and finally the final one. We can represent this case in this way:
$$\langle 1,1,1,1 \rangle$$However, there are more possibilities. For instance, you could do the first two steps with a single step, and then continue as usual.
$$\langle 2,1,1 \rangle$$Or we can climb 1 step, 2 steps and then the final step.
$$\langle 1,2,1 \rangle$$
Now, imagine for a moment that you have very long legs (infinitely long, to be precise) and you can do any number of stairs with a single step. In how many ways you can climb a staircase with N steps?
It is clear that the problem is equivalent to find the number of ways we can sum to \(N\) using any number of integers. Note that the order matters: \(1+2+1\) is different from \(2+1+1\).
In this scenario, the solution is \(2^{N-1}\) different “staircase climbing patterns”. This is easy to prove. In fact, for \(N\), we can write a “template” covering every pattern in this way:
$$\langle \overbrace{1 \square 1 \square \dots \square 1}^N \rangle$$We can see that there are \(N-1\) boxes and we can get every possibility by choosing for each box a “\(+\)” (plus) or a “\(,\)” (comma). Just find the possible combinations of “plus” and “commas” and you get the solution.
What is a n-Bounded Composition
Unfortunately, in reality we haven’t infinitely long legs. There is a maximum amount of stairs we can do with a single step.
Suppose that we can do at most 3 stairs with a single step. Now the number we are looking for is different. In our 4-stairs example, for instance, the \(\langle 4 \rangle\) solution is no longer valid because we cannot climb 4 stairs at once.
It is clear that the number is smaller than the total number of compositions of N. But what is this number? In the \(N=4\) case, the solution is easy: just remove the only invalid solution \(\langle 4 \rangle\). But for larger numbers? What about \(N=27\)?
We call these Bounded Compositions. In particular, if the maximum number we can have is \(n\), we call these n-Bounded Compositions of \(N\).
The Number of 3-Limited Compositions is the Tribonacci Sequence
In the rest of the article I will show you that the number of 3-Bounded Compositions of \(N\) is exactly equal to the \(N-th\) Tribonacci number.
$$|C_3(N)| = Tribonacci(N)$$A Constructive Proof
We start by manually looking for the number of compositions of basic integers.
We define that \(|C_3(0)| = 1\). It makes sense. There is only one way to sum integers to 0: doing nothing.
For \(N=1\) we trivially have that \(|C_3(1)| = 1\).
For \(N=2\) we have 2 compositions: \(\langle 1,1 \rangle\) and \(\langle 2 \rangle\). So \(|C_3(2)| = 2\).
For \(N=3\) we have 4 compositions: \(\langle 3 \rangle\), \(\langle 2,1 \rangle\), \(\langle 1,2 \rangle\) and \(\langle 1,1,1 \rangle\). So \(|C_3(3)| = 4\).
Up to this point there is no difference with the unconstrained compositions. Let’s look at \(N=4\). To construct the set of compositions let’s start from the one composed by only ones: \(\langle 1,1,1,1 \rangle\). Now we can split this in two parts: the first 3 number 1s and the last 1. For the first set, we can list the 3 compositions of \(N=3\).
| \(C_3(3)\) | One more \(1\) |
|---|---|
| \(\langle 1,1,1\) | \(1 \rangle\) |
| \(\langle 2,1\) | \(1 \rangle\) |
| \(\langle 1,2\) | \(1 \rangle\) |
| \(\langle 3\) | \(1 \rangle\) |
At this point we can already see that this tables shows 4 valid compositions of \(N=4\).
| \(C_3(4)\) based on \(C_3(3)\) |
|---|
| \(\langle 1,1,1,1 \rangle\) |
| \(\langle 2,1,1 \rangle\) |
| \(\langle 1,2,1 \rangle\) |
| \(\langle 3,1 \rangle\) |
To find the missing ones, we need to sum the last two numbers in each composition.
| \(C_3(4)\) based on \(C_3(3)\) | Obtained by Sum |
|---|---|
| \(\langle 1,1,1,1 \rangle\) | \(\langle 1,1,2 \rangle\) |
| \(\langle 2,1,1 \rangle\) | \(\langle 2,2 \rangle\) |
| \(\langle 1,2,1 \rangle\) | \(\langle 1,3 \rangle\) |
| \(\langle 3,1 \rangle\) | \(\langle 4 \rangle\) |
We can quickly see that there is an invalid composition: \(\langle 4 \rangle\). If we remove all the invalid compositions we obtain remain with every 3-bounded compositions for \(N=4\): therefore, \(|C_3(4)| = 7\).
At this point we can develop a quick relation between \(|C_3(N)|\) and \(|C_3(N-1)|\): the number of \(3\)-bounded compositions for \(N\) are 2 times the number of compositions for \(N-1\) minus the number of invalid compositions.
Not a big improvement eh? Don’t worry and follow me.
Now, we can note the fact that the number of invalid compositions depends on the number of compositions of \(N-1\) ending with \(3\). It is in fact easy to see that the only way to get an invalid composition when we sum the last two numbers of a composition is when the corresponding \(C_3(N-1)\) composition ends with a 3. In fact, in that case, adding the extra \(1\) during the “sum” step will overflow.
Let’s call \(\gamma_x(N)\) the number of composition of \(N\) ending with \(x\) and write the resulting formula:
$$|C_3(N)| = 2 |C_3(N-1)| - \gamma_3(N-1)$$At this point, we can reiterate the same intuition and think about the number \(\gamma_3(N-1)\). The number of compositions ending with \(3\) of \(N-1\) depends on the number of compositions ending with \(2\) in \(N-2\). We can then rewrite the above formula in this way:
$$|C_3(N)| = 2 |C_3(N-1)| - \gamma_2(N-2)$$And then again:
$$|C_3(N)| = 2 |C_3(N-1)| - \gamma_1(N-3)$$At this point we go back to the table and see that the only compositions ending with \(1\) are the one coming from the previous iteration. In fact, all the compositions after the “sum” step must be at least greater than 2.
$$\gamma_1(N-3) = |C_3(N-4)|$$We are now ready to rewrite the entire formula in function of \(|C_3|\):
$$|C_3(N)| = 2 |C_3(N)| - |C_3(N-4)|$$We can verify this for \(|C_3(4)|\):
$$|C_3(4)| = 2 |C_3(3)| - |C_3(0)| = 2 \cdot 4 - 1 = 7$$Equivalence with the Tribonacci Formula
In that format is hard to see, but the formula we got is another way to express the Tribonacci formula.
In the following section we will show that
$$f(n) = 2*f(n-1) - f(n-4)$$is equivalent to
$$f(n) = f(n-1) + f(n-2) + f(n-3)$$In fact, we can rewrite
$$f(n-1) = f(n-2) + f(n-3) + f(n-4)$$And then subtract the second from the first:
$$f(n) - f(n-1) = f(n-1) + f(n-2) - f(n-2) + f(n-3) - f(n-3) - f(n-4)$$The terms with \(n-2\) and \(n-3\) cancels out leaving us with:
$$f(n) - f(n-1) = f(n-1) - f(n-4)$$And, finally, moving things around:
$$f(n) = 2*f(n-1) - f(n-4)$$Corollary and Conclusions
Of course, there is nothing special about the number 3.
The same reasoning can be reiterated for any arbitrary maximum allowed integer. I already checked the 2-bounded compositions and, as predicted, they follow the classic Fibonacci sequence.
It is then easy to see that \(n\)-bounded compositions will follow the \(n\)-bonacci sequence. In fact, we can use the same same line of reasoning reaching the conclusion that the number of \(n\)-bounded compositions fall in the following pattern
$$|C_n(N)| = 2 |C_n(N)| - |C_n(N-(n+1))|$$And that any formula in the form:
$$f(n) = 2f(n-1) - f(n-(c+1))$$Is just an alternative way to write a generic \(c\)-bonacci formula:
$$f(n) = \sum_1^c f(n-c)$$This does not qualify as a rigorous proof, but I am happy with the result.
I am sorry if I feel excited for something that may be well known in the mathematical community. I just thought it was another surprising appearance of the Fibonacci sequence, and it was fun to share.
Photo by Jordan Cormack on Unsplash
