Generating function for special string 11100

Question

Let $S$ be the set of $\{0,1\}$-strings that do not contain $11100$ as a string. Find the generating function of S where the weight of a string is its length.

I tried this way :

Consider all blocks that end with $0$. There are two types of such blocks: $A$ which is either $0$ or $10$, and $B$ which is $1111*0$. (∗ means repeat one or more times).

Now, every sequence of $0$'s and $1$′s can be constructed as $\{A;B\}∗1\,∗$. The resulting sequence does not contain $=11100$ iff two conditions are met: we don't have two consecutive blocks $BA$, i. e. $BA$ is forbidden.

But I am not sure this concept. Please help me.

Thanks your idea.

Answer 1

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=\{11100\}$ 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^n$ being the number of valid words of length $n$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\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}[11100]) \end{align*}

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

It follows from (1) and (2)

\begin{align*} \color{blue}{f(s)}&\color{blue}{=\frac{1}{1-2s+s^5}}\\ &=1 + 2 s + 4 s^2 + 8 s^3 + 16 s^4\\ &\qquad+ 31 s^5 + \color{blue}{60} s^6 + 116 s^7 + 224 s^8 \cdots \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $s^6$ for example shows there are $\color{blue}{60}$ valid words of length $6$ from the alphabet $\{0,1\}$ which do not contain the word $11100$. The invalid $2^6-60=4$ words are \begin{align*} \color{blue}{0}11100,\quad \color{blue}{1}11100,\quad 11100\color{blue}{0},\quad 11100\color{blue}{1} \end{align*}

Answer 2

We use the symbolic method to derive a generating function $f(s)$.

Let $\mathcal{F}$ denote the set of all valid words, i.e. the set of all binary words which do not contain the word $11100$. We have \begin{align*} \color{blue}{\varepsilon+\mathcal{F}\{0,1\}=\mathcal{F}+\mathcal{F}\{11100\}}\tag{1} \end{align*}

The left-hand side of (1) consists of

• $\mathcal{F}\{0,1\}$: The set of all valid words which have additionally appended either a $0$ or a $1$ at the end. These words have all length at least $1$.

• $\varepsilon$: We add the empty word which is not part of $\mathcal{F}\{0,1\}$.

The right-hand side of (1):

• Note that $\mathcal{F}\{0,1\}$ contains the set of all valid words $\mathcal{F}$, but not the empty word $\varepsilon$.

• Invalid words contained in $\mathcal{F}\{0,1\}$ occur at the end only due to the appended $\{0,1\}$ at the end, resulting in $\mathcal{F}\{11100\}$.

Note that \begin{align}\varepsilon\cap \mathcal{F}\{0,1\}=\emptyset\qquad\text{ and }\qquad\mathcal{F}\cap \mathcal{F}\{11100\}=\emptyset.\end{align} So, we have at both sides of (1) a partition which avoids multiple counting of words.

From (1) we obtain the generating function $f(s)$ in the form

\begin{align*} 1+f(s)\cdot (s+s)&=f(s)+f(s)s^5\\ \end{align*} which results in \begin{align*} \color{blue}{f(s)}&\color{blue}{=\frac{1}{1-2s+s^5}}\\ \end{align*}