How many different binary strings of length n are there that do not contain 3 consecutive 0’s and 2 consecutive 1’s

combinatoricspermutations

Restrictions:

  1. First and the last digit has to be 1.
  2. Contain no two consecutive 1's and
  3. Contain no three consecutive 0's

From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11… or …11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got
For 

n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways

I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting.
I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1

Best Answer

Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $\binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is $$ \sum_{\substack{k=0}}^{\lfloor (n-1)/2\rfloor}\binom{\frac{n+k-1}3}{k} $$ where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.

It is also possible to get a "closed form" by solving the linear recurrence $$ a_n=a_{n-2}+a_{n-3},\\ a_2=0,\\ a_1=1,\\ a_0=0. $$ To solve this, see for example:

https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.

Related Question