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!
Follow