Ordered binary sequences of length n with no two consecutive 0's without using recursion

Solution 1:

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

We consider words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $\mathcal{B}=\{00\}$ of bad words which are not allowed to be part of the words we are looking for.

We derive a function $F(x)$ with the coefficient of $x^n$ being the number of wanted words of length $n$. According to the paper (p.7) the generating function $F(x)$ is \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[00]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[00])&=-x^2-\text{weight}(\mathcal{C}[00])x \end{align*} \begin{align*} \text{weight}(\mathcal{C}[00])=-\frac{x^2}{1+x}\\ \end{align*}

It follows:

A generating function $F(x)$ for the number of words built from $\{0,1\}$ which do not contain the subword $00$ is \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x+\frac{x^2}{1+x}}\\ &=\frac{1+x}{1-x-x^2}\\ &=1+2x+3x^2+5x^3+8x^4+13x^5\\ &\qquad+21x^6+34x^7+55x^8+89x^9+144x^{10}+\cdots\tag{1} \end{align*}

The last line (1) was calculated with Wolfram Alpha and we see the coefficients are the Fibonacci numbers $F_n$ starting with $F_2=1$.

We conclude: The generating function $F(x)$ is

\begin{align*} \bbox[10px,border:2px solid blue]{ F(x)=\frac{1+x}{1-x-x^2}=\sum_{n=0}^\infty F_{n+2}x^n } \end{align*}

and the number of binary strings of length $n=25$ which do not contain the substring $00$ is the Fibonacci number

$$ \bbox[10px,border:2px solid blue]{ F_{27}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{27}-\left(\frac{1-\sqrt{5}}{2}\right)^{27}\right)=196148 } $$

$$ $$

Addon 2016-09-01: Due to a comment of OP some details regarding the calculation of \begin{align*} \text{weight}(\mathcal{C}[00])=-\frac{x^2}{1+x}\tag{1} \end{align*}

A shortcut of the following is indicated in a note at the end.

The main theme is to properly cope with overlaps of bad words. In order to do so we introduce some terminology. Let $w=w_1w_2\ldots w_n$ be a word consisting of $n$ characters. We define \begin{align*} weight(w)&:=x^{length(w)}=x^n\\ HEAD(w)&:=\{w_1,w_1w_2,\ldots,w_1w_2\ldots w_{n-1}\}\\ TAIL(w)&:=\{w_n,w_{n-1}w_n,\ldots,w_nw_{n-1}\ldots w_2\}\\ OVERLAP(u,v)&:=HEAD(u)\cap TAIL(v) \end{align*}

Example: $w=00$

Since we have to consider only one bad word $00$ we look at an example with $w=u=v=00$.

We obtain \begin{align*} weight(00)&=x^{length(00)}=x^2\\ HEAD(00)&=\{0\}\\ TAIL(00)&=\{0\}\\ OVERLAP(00,00)&:=HEAD(00)\cap TAIL(00)=\{0\}\tag{2} \end{align*}

If $x\in HEAD(v)$ we write \begin{align*} v&=xx^\prime\\ v/x&:=x^\prime \end{align*} and we define for convenience $u:v$ as sum over all overlaps of two words $u$ and $v$. We sum up the weighted left-over parts $v/x$ when chopping overlaps. \begin{align*} u:v:=\sum_{x\in OVERLAP(u,v)}weight(v/x) \end{align*}

Note that according to (2) $$OVERLAP(00,00)=\{0\}$$ So, the calculation of $u:v$ with $u=v=00$ results in \begin{align*} 00:00&=\sum_{x\in \{0\}}weight(00/x)\\ &=weight(00/0)\\ &=weight(0)\\ &=x^{length(0)}\\ &=x^1 \end{align*}

Finally we find at the beginning of page 9 of the paper an identity for $weight(\mathcal{C}[v])$ with $Comp(v)$ defined as the set of bad words $u\in \mathcal{B}$ for which $OVERLAP(u,v)$ is non-empty. \begin{align*} weight(\mathcal{C}[v])=-weight(v)-\sum_{u\in Comp(v)}(u:v)\cdot weight\left(\mathcal{C}[u]\right) \end{align*}

We obtain with $v=00$ \begin{align*} weight(\mathcal{C}[00])&=-weight(00)-\sum_{u\in Comp(00)}(u:00)\cdot weight\left(\mathcal{C}[u]\right)\\ &=-x^{length(00)}-\sum_{u\in \{00\}}(u:00)\cdot weight\left(\mathcal{C}[u]\right)\\ &=-x^{length(00)}-(00:00)\cdot weight\left(\mathcal{C}[00]\right)\\ &=-x^2-x^1\cdot weight\left(\mathcal{C}[00]\right)\tag{3}\\ \end{align*} and the claim (1) follows.

Note: Although the notation looks somewhat complicated. With some routine you can skip nearly all of the calculations. We can deduce (3) quickly by observing that there is just one bad word $00$ resulting in a term $x^2$ and one overlap \begin{align*} 0&0\\ 00&\\ \end{align*} resulting in a term $x^{length(0)}=x$.

Note: Another description of $HEAD, TAIL$ and $OVERLAP$ with the bad word $ABBA$ can be found in this answer.

Solution 2:

Just to put in a defense of recursive methods:

Let $A_n$ be the number of "good" sequences of length $n$. It is reasonably clear that any good sequence (of length at least $2$) ends in either $0$ or $01$. Of course what precedes that ending must be a good sequence of shorter length. Conversely, any good sequence of length $n-1$ becomes a good sequence of length $n$ if you append a $0$ and any good sequence of length $n-2$ becomes a good sequence of length $n$ if you append $01$. Thus we see that $$A_n=A_{n-1}+A_{n-2}$$ Which we recognize as the Fibonacci recursion. Since $A_1=2$ and $A_2=3$ it is easy to generate $A_n$ for any modest $n$. No need to solve the recursion (though of course that is possible).