{"id":280,"date":"2017-11-15T20:40:38","date_gmt":"2017-11-16T04:40:38","guid":{"rendered":"https:\/\/blogs.ubc.ca\/organizingchaos\/?p=280"},"modified":"2017-11-15T21:28:25","modified_gmt":"2017-11-16T05:28:25","slug":"mathematical-aside-golden-mean-shift-and-pascals-triangle-part-2","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/organizingchaos\/2017\/11\/15\/mathematical-aside-golden-mean-shift-and-pascals-triangle-part-2\/","title":{"rendered":"Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 2)"},"content":{"rendered":"

As we discussed in Part 1<\/a>, we noticed a common pattern in the the m^{th} element in the n^{th} diagonal, d_{m,n},\u00a0 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.<\/p>\n

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,\u00a0c_{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}\u00a02(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}.<\/p>\n

Another way to see this requires knowledge of combinations.\u00a0 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\u00a0c_{m,n} as follows:<\/p>\n