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!

Leave a Reply

Your email address will not be published.