November | 2017 | Organizing Chaos

As was derived in Part 2, $|c_{m,n}|=$ ${n-(m-1)}\choose{m}$ where $c_{m,n}$ denotes the set of binary strings of length $n$ with exactly $m$ non-adjacent ones.

Today we will analyze $c_{n}$ the set of binary strings of length $n$ with any number of non-adjacent ones. We will need some additional notation.

$c_{n,0}$ denote the the subset of $c_{n}$ ending with 0
$c_{n,1}$ denote the the subset of $c_{n}$ ending with 1

After some thought, we realize that $c_{n,0} =c_{n-1}$ and $c_{n-2}$ . We can then derive the recurrence $|c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|$ . After verifying the base case, we can conclude $|c_{n}| = F_{n+2}$ , the Fibonacci Numbers!

Another way to compute $|c_{n}|$ is $|c_{n}| = \sum_{m=0}^{\infty}$ ${n-(m-1)}\choose{m}$ .

Therefore $F_{n+2} =$ $\sum_{m=0}^{\infty}$ ${n-(m-1)}\choose{m}$ .

With some shifting, we can solve for the $n^{th}$ Fibonnaci number :

$F_{n} =$ $\sum_{m=0}^{\infty}$ ${n-m-1}\choose{m}$

While this formula can be quite easily verified inductively, its nice to construct it explicitly.

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!

Organizing Chaos

Undergrad Mathematics and Computer Science @ UBC

Monthly Archives: November 2017

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

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