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!