# Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 2)

As we discussed in Part 1, we noticed a common pattern in the the $m^{th}$ element in the $n^{th}$ diagonal, $d_{m,n}$,  of Pascal’s Triangle and the function $c_{m,n}$, denoting the set of binary strings of length $n$ with exactly $m$ non-adjacent ones. Today we derive an explicit formula for $c_{m,n}$ in two ways.

Firstly, some more notation. The element in $r^{th}$ row and $k^{th}$ column in Pascal’s Triangle is denoted by ${r}\choose{k}$. Then we can see $d_{m,n} = {n+m-1,m}$. Unfortunately, $c_{m,n}$ is at a slight shift. To see this, we think about how long the string needs to be just so can fit in $m$ ones. The answer is $2(m-1)$. While the $d_{m,n}$ is non-zero straight away, it takes $c_{m,n}$ $2(m-1)$ increments to the length before it is non-zero. Therefore, $|c_{m,n}|=d_{m,n-2(m-1)}=$ ${n-(m-1)}\choose{m}$.

Another way to see this requires knowledge of combinations.  If we consider the unconstrained system, the clearly we have $u_{m,n} {n}\choose{m}$ options. We can construct a bijection from $u_{m,n-(m-1)}$ to $c_{m,n}$ as follows:

• For every element in $u_{m,n-(m-1)}$, we can add append a 0 to all but the rightmost 1 and construct a unique element in $c_{m,n}$
• For every element in $c_{m,n}$, we can add delete a 0 from the right side of all but the rightmost 1 and construct a unique element in $u_{m,n-(m-1)}$

Thus $|c_{m,n}| = |u_{m,n-(m-1)}|=$ ${n-(m-1)}\choose{m}$ as required.

We will use this to find an intriguing connection to the Fibonacci numbers in Part 3!