As we discussed in Part 1, we noticed a common pattern in the the element in the diagonal, , of Pascal’s Triangle and the function , denoting the set of binary strings of length with exactly non-adjacent ones. Today we derive an explicit formula for in two ways.
Firstly, some more notation. The element in row and column in Pascal’s Triangle is denoted by . Then we can see . Unfortunately, is at a slight shift. To see this, we think about how long the string needs to be just so can fit in ones. The answer is . While the is non-zero straight away, it takes increments to the length before it is non-zero. Therefore, .
Another way to see this requires knowledge of combinations. If we consider the unconstrained system, the clearly we have options. We can construct a bijection from to as follows:
- For every element in , we can add append a 0 to all but the rightmost 1 and construct a unique element in
- For every element in , we can add delete a 0 from the right side of all but the rightmost 1 and construct a unique element in
Thus as required.
We will use this to find an intriguing connection to the Fibonacci numbers in Part 3!