[Math] All binary strings of length n that do not contain 3 consecutive 0’s

discrete mathematicsrecurrence-relations

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.

Best Answer

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.

Related Question