# Find a recurrence relation for the number of bit strings of length n that do not contain “0011”

So this is what I thought:

i) start with 1: $f(n-1)$

ii)start with 01: $f(n-2)$

iii) start with 000 : $f(n-3)$

iv) start with 0010: $f(n-4)$

Though I was told it's not true. I would like to know what did I did wrong, and what's the solution. Thanks

• E.g. Sequences of 000 type may begin 000-11... such that the string after - has no 0011 but this string has 0011 nonetheless. The reason why this "strings beginning with 1, 01, 001 etc" argument works for avoiding strings with consecutive 0s is because we consider the beginning part and the rest of the string together. If we want to avoid, say, 3 consecutive 0s then strings can begin 1, 01, 001 each followed by a shorter string obeying the same rule and we're okay because the 1 cuts short any string of consecutive 0s. Also the 3 types of beginning are mutually exclusive and exhaustive. – N. Shales May 10 '17 at 21:53
• "I would like to know what did I did wrong" I would like to know what you did. What is your solution? – leonbloy May 10 '17 at 23:00

The most straightforward way to start solving a problem like this is to begin by defining a recurrence relation with four variables: $$f_\varnothing(n), f_1(n), f_{11}(n), f_{011}(n)$$ where the subscript represents the longest initial part of the string that matches the end of $0011$. For example, the string $110110$ would be counted by $f_{11}(6)$. We will then have $f(n) = f_\varnothing(n) + f_1(n) + f_{11}(n) + f_{011}(n)$.

We can write recurrence relations for these in terms of each other: \begin{align} f_\varnothing(n+1) &= f_\varnothing(n) + f_1(n) \\ f_1(n+1) &= f_\varnothing(n) + f_{011}(n) \\ f_{11}(n+1) &= f_1(n) + f_{11}(n) \\ f_{011}(n+1) &= f_{11}(n) \end{align} Here's the idea for how to get this expression: if we have a string counted by $f_{11}(n)$, for example, we can either

• add a $0$ to the start, and get a string counted by $f_{011}(n+1)$, or
• add a $1$ to the start, and get a string counted by $f_{11}(n+1)$.

This means that both $f_{011}(n+1)$ and $f_{11}(n+1)$ should have an $f_{11}(n)$ term. We do the same thing for all three other cases.

Depending on how you want to solve the recurrence, this is good enough. For example, we can write this down as a matrix recurrence $$\begin{bmatrix} f_\varnothing(n+1) \\ f_1(n+1) \\ f_{11}(n+1) \\ f_{011}(n+1)\end{bmatrix} = \begin{bmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0\end{bmatrix}\begin{bmatrix} f_\varnothing(n) \\ f_1(n) \\ f_{11}(n) \\ f_{011}(n)\end{bmatrix}$$ and one way to solve a linear recurrence is to put everything into a matrix anyway.

• (+1) And this yields right away that each component $f_\alpha(n)$ and their sum $f(n)$ itself are such that $$\lim \lambda^{-n}f_\alpha(n)=g_\alpha$$ for some finite positive $g_\alpha$, where $\lambda$ denotes the largest root of $$\lambda^3-\lambda^2-\lambda-1=0$$ that is, $$\lambda\approx1.8393$$ – Did May 15 '17 at 16:50

One way to solve this is with generating functions.

The generating function for binary words not containing $0011$ is given by $f^{\text{c}}(x)$ (this is the generating function we want to find).

Call the generating function for binary words that do contain $0011$ $f(x)$ and the generating function for all binary words $g(x)=1/(1-2x)$ then

$$g(x) = f(x) + f^{\text{c}}(x)=(1-2x)^{-1}$$

but any word (represented by $f(x)$) that does contain $0011$ has some leftmost occurrence of $0011$ (these $4$ digits are represented by $x^4$ in our generating function). Left of this there are no occurrences of $0011$ (this is represented by $f^{\text{c}}(x)$) and to the right is any binary word (represented by $g(x)$). So

$$f(x) = f^{\text{c}}(x)\cdot x^4 \cdot g(x)$$

and therefore

$$g(x)=f^{\text{c}}(x)g(x)x^4 + f^{\text{c}}(x)$$

$$\implies f^{\text{c}}(x) = \frac{g(x)}{1+g(x)x^4}=\frac{1}{1-2x+x^4}\tag{Answer 1}$$

Using sage to expand the first 20 terms gives

\begin{align}\frac{1}{1-2x+x^4}&=\ldots+\, 266079 \, x^{20} + 144664 \, x^{19} + 78652 \, x^{18} + 42762 \, x^{17} \\&+ 23249 \, x^{16} + 12640 \, x^{15} + 6872 \, x^{14} + 3736 \, x^{13} + 2031 \, x^{12}\\[1ex]& + 1104 \, x^{11} + 600 \, x^{10} + 326 \, x^{9} + 177 \, x^{8} + 96 \, x^{7} \\[1ex]&+ 52 \, x^{6} + 28 \, x^{5} + 15 \, x^{4} + 8 \, x^{3} + 4 \, x^{2} + 2 \, x + 1\end{align}

The recurrence relation can be recovered from the generating function if need be since

$$f^{\text{c}}(x)=\sum_{k\ge 0}f_kx^k$$

rearranging the generating function gives

$$f^{\text{c}}(x) = 1 + 2xf^{\text{c}}(x)-x^4f^{\text{c}}(x)$$ $$\implies f_k = 2f_{k-1} - f_{k-4} \tag{Answer 2}$$

with initial value $f_0=1$ and $f_k=0$ for $k>0$.

Here $f_k$ is the number of valid binary words that avoid the string $0011$.

Many thanks to @Marko Riedel for proof-reading my answer up to this point. I think I got 'em all!... Now.

Roughly defined, a regular expression is a list of strings separated by $+$ signs, so for example the regular expression G for all binary strings looks like

$$G=\epsilon\, + \, 0 \, + \, 1 \, + \, 00\, + \, 01\, +\, 11\, +\, 10\, +\, 000\, +\, 001\, +\, 010\, +\, 100\, +\, 011\, +\, 101\, +\, 110\, + 111\, +\cdots$$

Regular expressions, to an extent behave like algebraic sums in that terms can be added, subtracted and factored (as long as the order of symbols is maintained). Regular expressions become generating functions on replacement of symbols with indeterminates which commute. So by replacing $1\rightarrow x$, $2\rightarrow x$ and $\epsilon\rightarrow 1$ then $G$ becomes $g(x)$

$$g(x) = 1\, +\, x\, +\, x\, +\, x^2\, +\, x^2\,+\, x^2\,+\, x^2\, +\, x^3\, +\, x^3\, +\, x^3\, +\, x^3\, +\, x^3\, +\, x^3\, +\, x^3\, +\, x^3\, +\cdots$$ $$\implies g(x) = 1\, +\, 2x\, +\, 4x^2\, +\, 8x^3\, +\cdots$$ $$\implies g(x) = 1\, +\, 2^1x\, +\, 2^2x^2\, +\, 2^3x^3\, +\cdots=\frac{1}{1-2x}$$

The effect of replacing symbols with indeterminates such as $x$ is to enumerate numbers of strings of a given length with a sum of terms of the form $(\text{# of strings of length$k$})x^k$.

A note of caution

It is to be noted carefully that the method in the answer works here because the string $0011$ has an empty intersection between it's "head" set $\mathrm{head}(0011)=\{0,00,001\}$ and it's "tail" set $\mathrm{tail}(0011)=\{1,11, 011\}$ i.e. $\mathrm{head}(0011)\cap\mathrm{tail}(0011)=\emptyset$.

This implies that the regular expression $F^{\text{c}}$ for $f^{\text{c}}(x)$ may contain strings ending with any elements from $\mathrm{tail}(0011)$ without contradicting the assertion that $0011$ in $F^{\text{c}}0011G$ is the first such occurrence.

A more complicated example

Take an example where an empty intersection is not the case. Let's find the generating function which enumerates binary strings that avoid the substring $0110$ in all binary words, we will call this generating function $f^{\neg(0110)}(x)$. (I have decided to change the notation here so that the regular expression and associated generating functions describe the set of sequences they represent)

The head and tail set for $0110$ are $\mathrm{head}(0110)=\{0,01,011\}$ and $\mathrm{tail}(0110)=\{0,10,110\}$ has intersection $\mathrm{head}(0110)\cap\mathrm{tail}(0110)=\{0\}$. This means that if we argue that the regular expression for all binary words $G$ either contains the string $0110$ or it doesn't then it is the sum of regular expressions $F^{0110}+F^{\neg(0110)}$. We might continue to argue that, analogous to before, any sequence containing $0110$ has some first occurrence left of which there is no string $0110$ and right of which is any string, this would give the regular expression $F^{0110}=F^{\neg(0110)}0110G$ and hence

$$F^{\neg(0110)}0110G + F^{\neg(0110)}=G$$

However we do not need $F^{\neg(0110)}$ to contain the full string $0110$ in order to contradict the assertion that $0110$ is the first such occurrence. Reason as follows: since any sequence belonging to $F^{(0110)}$ that ends with the $011$ will complete $011\underline{0}$ by the first $0$ of our so-called "first occurrence" of $\underline{0}110$. This happens when the first $0$ of our string $\underline{0}110$ is appended (note that this is the string belonging to $\mathrm{head}(0110)\cap\mathrm{tail}(0110)=\{0\}$), hence we have contradicted our assertion that the $0110$ in $F^{\neg(0110)}0110G$ is the first such occurrence.

We can get over this problem by insisting that the first part of the sequence not only avoids $0110$ but also avoids ending in the string $011$. Denote such a regular expression as $F_{\neg(011)}^{\neg(0110)}$, then our amended regular expression equation looks like

$$F_{\neg(011)}^{\neg(0110)}0110G + F^{\neg(0110)}=G\tag{\star}$$

Our next task is to determine $F_{\neg(011)}^{\neg(0110)}$.

A little reasoning will convince the reader that

$$F^{\neg(0110)}=F_{\neg(011)}^{\neg(0110)} + F_{\neg(011)}^{\neg(0110)}011\tag{\star\star}$$

as any sequence that avoids $0110$ can be considered the sum of sequences that avoid $0110$ and don't end with $011$ and sequences that avoid $0110$ and do end in $011$. The latter case must clearly be represented by $F_{\neg(011)}^{\neg(0110)}011$, it cannot be $F^{\neg(0110)}011$ for the same reason we replaced $F^{\neg(0110)}0110G$ with $F_{\neg(011)}^{\neg(0110)}0110G$ earlier.

At this point we can transform our regular expression in to generating functions to give

$$f_{\neg(011)}^{\neg(0110)}(x)x^4g(x) + f^{\neg(0110)}(x)=g(x)\tag{\star}$$ $$f^{\neg(0110)}(x)=F_{\neg(011)}^{\neg(0110)}(x) + f_{\neg(011)}^{\neg(0110)}(x)x^3\tag{\star\star}$$ $$\implies f_{\neg(011)}^{\neg(0110)}(x)=f^{\neg(0110)}(x)(1+x^3)^{-1}$$

Using this last result with $(\star)$

$$f^{\neg(0110)}(x)(1+x^3)^{-1}x^4g(x) + f^{\neg(0110)}(x)=g(x)$$ $$\implies f^{\neg(0110)}(x)=g(x)\left(1+g(x)\frac{x^4}{1+x^3}\right)^{-1}\tag{\star\star\star}$$

Summary

It is now possible to see that this question is a special case of a more general problem of pattern avoidance, we can see that the reason why we were able to use the generating function equivalent of $F^{\neg(0011)}$ in the original question is because it is indistinguishable from $F_{s}^{\neg(0011)}$ for $s\in \mathrm{head}(0011)\cap\mathrm{tail}(0011)$ since $\mathrm{head}(0011)\cap\mathrm{tail}(0011)=\emptyset$.

In general for pattern avoidance problems we are required to use this (generally non-empty) intersection set. The denominator in $(\star\star)$ (i.e. $1+x^3$) is sometimes referred to as the autocorrelation polynomial and can be calculated for two strings quite easily once we have found the set $\mathrm{head}(\text{string 1})\cap\mathrm{tail}(\text{string 2})$.

For further details see the MSElink provided by @Marko Riedel in the comments. In that link I particularly recommend the paper on the Goulden-Jackson Cluster Method linked in @Markus Scheuer's answer as it is surprisingly easy reading and a very versatile tool.

• Did you define $f(x)$ and $f^c(x)$ to be the same in your intro by any chance? – Marko Riedel May 10 '17 at 22:56
• This is section 8.4 "Flipping coins" from Concrete Mathematics. (1989 edition). They solve a slightly different problem, flipping coins until a pattern appears. On page 391 we see the DFA method deployed and on page 392 the trick with the split into the set of admissible strings and its complement. – Marko Riedel May 10 '17 at 23:38
• Did you mix your $f(x)$ and $f^c(x)$ in your derivation of the recurrence at the conclusion? – Marko Riedel May 10 '17 at 23:55
• This is the MSE link for $0110$ that I cited. – Marko Riedel May 11 '17 at 20:17
• I think I can explain it. Translating a regular expression into generating functions only works if the path through the regex is unique, because these paths are what the generating function counts. Suppose we have a prefix followed by $0110110$ as the first ocurrence followed by some suffix. We can parse this in two ways (which is not possible with the pattern $0011$). (...) – Marko Riedel May 12 '17 at 0:37

This answer is based upon the Goulden-Jackson Cluster Method which is a convenient technique to derive a generating function for problems of this kind. A recurrence relation can then be derived easily.

We consider words of length $m\geq 0$ built from a binary alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{0011\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^m$ being the number of searched words of length $m$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[0011]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[0011])&=-s^4\\ \end{align*}

and obtain

\begin{align*} \color{blue}{f(s)}&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &\color{blue}{=\frac{1}{1-2s+s^4}}\tag{1}\\ \end{align*}

From the generating function $f(s)=\sum_{m=0}^\infty a_m s^m$ stated in (1) we can derive the recurrence relation easily.

We obtain from (1) \begin{align*} f(s)=1+(2s-s^4)f(s) \end{align*}

and we conclude \begin{align*} \color{blue}{a_m}&=[s^m]f(s)\\ &=[s^m]\left(1+(2s-s^4)f(s)\right)\\ &= \begin{cases} &\color{blue}{=1}&\qquad m=0\\ 2[s^{m-1}]f(s)&\color{blue}{=2a_{m-1}}&\qquad m=1,2,3\\ (2[s^{m-1}]-[s^{m-4}])f(s)&\color{blue}{=2a_{m-1}-a_{m-4}}&\qquad m\geq 4 \end{cases} \end{align*}

One problem is with iii): the $f(n-3)$ includes strings starting with 11... (and otherwise contain no 0011), but putting 000 in front of that gives you 00011... i.e. it contains a 0011

Likewise, for iv): $f(n-4)$ includes strings starting with 011... and putting 0010 in front of that gives you 0010011... i.e. also a 0011

• There are $177$ strings of length $8$ not containing the subsequence $0011$. So you will have some trouble if your expression for $f(9)$ includes a term of the form $\frac78 f(8)$, since $f(9)$ should be an integer. (The problem with your argument is that, even though $\frac18$ of all length $n-1$ strings start with $011$, the same does not necessarily hold for strings not containing $0011$.) – Misha Lavrov May 10 '17 at 18:23
• @MishaLavrov Quite right, thanks!! OK, so that doesn't work either ... ;P – Bram28 May 10 '17 at 18:25