How to express this bitstring sequence as an OGF?

Question

I am wondering how we can express this sequence $B_{101}$ as an ordinary generating function (OGF), where $B_{101}$ is defined as the set of bitstrings (i.e. strings formed from $0$ and $1$) that does not have $101$ as a substring.

For instance, for the bitstring $B_{00}$, which is defined as the set of bitstrings that do not have the substring $00$, we can have a generating function $G(z)$, where:

$$ G(z) = 1 + z + (z+z^2)G(z) $$

In this case, $G(z)=a_0z^0 + a_1z^1 + a_2z^2 + ...$, and the coefficient $a_k$ of $z^k$ gives the number of bitstrings of length $k$ that do not have the substring $00$...

Answer 1

The first few terms are $1,2,4,7,12,21$; I looked this up in OEIS, and the first return was OEIS $A005251$, $$\langle a_n:n\ge 0\rangle=\langle 0,1,1,1,2,4,7,12,21,\ldots\rangle\;,$$ of which we are told that $a_{n+3}$ is the number of $n$-bit sequences that avoid $010$. Thus, you want

$$G(z)=\sum_{n\ge 0}a_{n+3}z^n\;,$$

where

$$\sum_{n\ge 0}a_nz^n=\frac{z(1-z)}{1-2z+z^2-z^3}\;,$$

according to the OEIS entry. This generating function can be derived from the recurrence $a_n=2a_{n-1}-a_{n-2}+a_{n-3}$, with initial conditions $a_0=0$ and $a_1=a_2=1$. The recurrence isn’t hard to justify.

Here a sketch of how you could do it from scratch, without relying on OEIS. Say that a bit string is good if it avoids $101$, and let $b_n$ be the number of good $n$-bit strings; we’ll begin by finding a recurrence for $b_n$. As a first approximation, each good $(n-1)$-bit string $\sigma$ can be extended to two $n$-bit strings, $\sigma^\frown 0$ and $\sigma^\frown 1$; $\sigma^\frown 0$ is definitely good, and $\sigma^\frown 1$ is good unless $\sigma$ ends in $10$. Thus, $b_n$ is $2b_{n-1}$ minus the number of good $(n-1)$-bit strings that end in $10$.

Every good $(n-1)$-bit string that ends in $0$ is obtained by appending a $0$ to a good $(n-2)$-bit string, and every good $(n-2)$-bit string can be extended to a good $(n-1)$-bit string ending in $0$, so there are $b_{n-2}$ good $(n-1)$-bit strings that end in $0$. A similar argument shows that $b_{n-3}$ of them end in $00$, so $b_{n-2}-b_{n-3}$ of them end in $10$, and it follows that

$$b_n=2b_{n-1}-(b_{n-2}-b_{n-3})=2b_{n-1}-b_{n-2}+b_{n-3}\;.$$

One can now use this recurrence to derive the generating function in the usual way.

Answer 2

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $\mathcal{V}=\{0,1\}$ and the set $B=\{101\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $G(z)$ with the coefficient of $z^n$ being the number of valid words of length $n$.

According to the paper (p.7) the generating function $G(z)$ is \begin{align*} G(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \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}[101]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[101])&=-z^3-\text{weight}(\mathcal{C}[101])z^2\tag{2}\\ \end{align*} It follows from (1) and (2) \begin{align*} \color{blue}{G(z)}&\color{blue}{=\frac{1}{1-2z+\frac{z^3}{1+z^2}}}\\ &=\frac{1+z^2}{1-2z+z^2-z^3}\\ &=1 + 2 z + 4 z^2 + 7 z^3 + 12 z^4\\ &\qquad+ \color{blue}{21} z^5 + 37 z^6 + 65 z^7 + 114 z^8 \cdots \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $z^5$ for example shows there are $\color{blue}{21}$ valid words of length $5$ from the alphabet $\{0,1\}$ which do not contain the word $101$. The $2^5-21=11$ invalid words are \begin{align*} &\color{blue}{101}00\qquad 0\color{blue}{101}0\qquad 00\color{blue}{101}\\ &\color{blue}{101}01\qquad 0\color{blue}{101}1\qquad 01\color{blue}{101}\\ &\color{blue}{101}10\qquad 1\color{blue}{101}0\qquad \\ &\color{blue}{101}11\qquad 1\color{blue}{101}1\qquad 11\color{blue}{101}\\ \end{align*}