All binary strings of length n that do not contain 3 consecutive 0's

Question

I'm a bit stuck with this problem and I'm sorry if this sounds newbie, I havent had much practice with recurrence relations. My approach was to split the problem into two cases, we let $a_n$ denote all legal binary strings of length $n$

1. Appending $1$ to the front of a string, this case is simple because no illegal strings can be made by appending $1$ in front of a legal string, so by appending $1$ to all legal strings of length $n-1$ we get $a_{n-1}$ legal strings.
2. Appending $0$ to the front of a string, this is where I get stuck.

My idea was to split the second case into even further cases so that each case would deal with the following prefixes: $00$, $01$, $10$ and $11$

The problem is that I can not find any good way to determine how many of each prefix occurs in the set of legal strings of length $n-1$. Any advice on this problem (or this subject in general) would be greatly appreciated since there is clearly something that I'm misunderstanding.

Answer 1

Let $a_n$ be the number of n-length sequences ending with $1$, $b_n$ the number of n-length sequences ending with $0$, but not with $00$ and $c_n$ the number of n-length sequences ending with $00$, but not with $000$. Obviously the wanted number is $a_n+b_n+c_n$.

Now we can take any of the sequence of the valid sequences of length $n$ and add $1$ to it and it will be a valid sequence of length $(n+1)$. Hence:

$$a_{n+1} = a_n + b_n + c_n$$

Now the only way to "construct" a sequence ending in a single zero is to take any of the $a_n$ sequences and append $0$ to it. Similarly the only way to "construct" a sequence ending in two zeroes is to take any of the $b_n$ sequences and append $0$ to it. Hence:

$$b_{n+1} = a_n; \quad \quad c_{n+1} = b_n = a_{n-1}$$

Therefore finally we have that:

$$a_{n+1} = a_n + a_{n-1} + a_{n-2}$$

Solving this recurrence relation for $a_1 = 1, a_2 = 2, a_3=4$ we can easily find the wanted answer.

Answer 2

The so-called Goulden-Jackson Cluster Method is a convenient technique to derive a generating function for problems of this kind.

We consider the set of binary words of length $n\geq 0$ and the set $B=\{000\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a function $f(s)$ with the coefficient of $s^n$ being the number of wanted words of length $n$.

According to the paper (p.7) from Goulden and Jackson the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=2$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[000]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[000])&=-\frac{s^3}{1+s+s^2}=-\frac{s^3(1-s)}{1-s^3} \end{align*}

We obtain the generating function $f(s)$ for the binary words which do not contain the substring $000$ as \begin{align*} f(s)&=\frac{1}{1-2s+\frac{s^3(1-s)}{1-s^3}}\\ &=\frac{1-s^3}{1-2s+s^4}\tag{2}\\ &=1+2s+4s^2+7s^3+13s^4+24s^5+44s^6+81s^7+\cdots \end{align*}

Note: The entries in the sequence $(1,2,4,7,13,24,44,81,149,274,\ldots)$ are the so-called Tribonacci numbers stored as A000073 in OEIS.

An explicit formula for the Tribonacci numbers is

\begin{align*} [s^n]f(s)&=\sum_{{k=0}\atop{k\equiv n(\bmod 3)}}^{2}\binom{k}{\frac{n-k}{3}}(-1)^{\frac{n-k}{3}}2^{k-\frac{n-k}{3}}\\ &\qquad+\sum_{{k=3}\atop{k\equiv n(\bmod 3)}}^{n-3} \left(\binom{k}{\frac{n-k}{3}}-\frac{1}{8}\binom{k-3}{\frac{n-k}{3}}\right)(-1)^{\frac{n-k}{3}}2^{k-\frac{n-k}{3}}\\ \end{align*}

A calculation can be found in this answer.

Answer 3

The DFA method including a Maple implementation was presented at the following MSE link. In the present case we obtain the following session.

> GFNC([[0,0,0]], 2, true);
                               [[0, 0, 0]]

                              Q[], 0, Q[0]

                               Q[], 1, Q[]

                            Q[0], 0, Q[0, 0]

                              Q[0], 1, Q[]

                         Q[0, 0], 0, Q[0, 0, 0]

                             Q[0, 0], 1, Q[]

                        Q[0, 0, 0], 0, Q[0, 0, 0]

                        Q[0, 0, 0], 1, Q[0, 0, 0]

                                 2
                                z  + z + 1
                            - ---------------
                               3    2
                              z  + z  + z - 1

This is the same as what Markus Scheuer obtained with a common factor of $s-1$ being canceled.

Answer 4

Let $u_n$ be the number of legal sequences of length $n$ beginning with 1. Then the number beginning with 01 and 00 is $u_{n-1}$ and $u_{n-2}$ respectively. Hence the total number of length $n$ is $t_n = u_n + u_{n-1} + u_{n-2}$. But clearly $u_{n+1} = t_n$. Hence $u_n$, and therefore $t_n$, satisfies the "Tribonnaci" recurrence. Similarly we get the "Tetranacci" recurrence if 0000 is forbidden, and so on.