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

Question

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

Answer 1

I can find a recursive formula, but a general formula is tricky.

$f(x) = f(x-2) + f(x-3)$

That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.

Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)

For a general formula as a function of N, we can assume

$f(x)=\sum{n^x}$ for some values of a and then

$n^x=n^{x-2}+n^{x-3}$

Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.

Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.

In your case, we have

• f(0) = 0 (trivial case)
• f(1) = 1 (1)
• f(2) = 0 (again trivial to check none work)
• f(3) = 1 (1-01)
• f(4) = 1 (1-001)
• f(5) = 1 (101-01)
• f(6) = 2 (101-001, 1001-01)
• f(7) = 2 (1001-001, 10101-01)
• f(8) = 2+1=3
• f(9) = 2+2=4

So your calculations are right.

Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.

Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=\sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.

Answer 2

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.