Generating function for binary strings not containing $0110$ or $11010$ as a substring

Question

Find the generating function for the binary strings that do not contain $0110$ or $11010$ as a substring.

I am familiar with proofs similar to this post, where the 'symbolic method' is used for counting combinatorial objects. As such I would be able to find generating functions for binary strings not containing $0110$ as a substring and the binary strings not containing $11010$ as a substring.

But I'm having a hard time finding the generating function for the binary strings not containing either of these as substrings. I have tried to consider where they overlap? Perhaps the symbolic method as in the linked post is not applicable and another approach is necessary, but I'm not sure what exactly. Any help is appreciated. Thanks in advance.

Answer 1

This answer is based upon the Goulden-Jackson Cluster Method. We consider the set of words of length $n\geq 0$ built from a binary alphabet $\mathcal{V}=\{0,1\}$ and the set $$B=\{0110,11010\}$$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $A(z)$ with the coefficient of $z^n$ being the number of wanted words of length $n$. According to the paper (p.7) the generating function $A(z)$ is \begin{align*} \color{blue}{A(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}$ is the weight-numerator of bad words with \begin{align*} \color{blue}{\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[0110])+\text{weight}(\mathcal{C}[11010])}\tag{2} \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[0110])&=-z^4-z^3\cdot\text{weight}(\mathcal{C}[0110])-z\cdot\text{weight}(\mathcal{C}[11010])\\ &\qquad\qquad\qquad\qquad 011\color{blue}{\underline{0}}110\qquad\qquad\qquad 0\color{blue}{\underline{110}}10\\ \text{weight}(\mathcal{C}[11010])&=-z^5-z^4\cdot\text{weight}(\mathcal{C}[0110])\tag{3}\\ &\qquad\qquad\qquad\qquad 1101\color{blue}{\underline{0}}110 \end{align*}

The additional terms on the right-hand side of (3) take into account overlaps, which are indicated by the blue letters of the overlapping bad words in the lines below. It follows \begin{align*} \text{weight}(\mathcal{C}[0110])=\frac{-z^4+z^6}{1+z^3-z^5}\qquad \text{weight}(\mathcal{C}[11010])=\frac{-z^5}{1+z^3-z^5} \end{align*} so that we get from (2) \begin{align*} \text{weight}(\mathcal{C})=\frac{-z^4-z^5+z^6}{1+z^3-z^5} \end{align*}

We obtain according to (1) and (3) \begin{align*} \color{blue}{A(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2z-\frac{-z^4-z^5+z^6}{1+z^3-z^5}}\\ &=\color{blue}{\frac{1+z^3-z^5}{1-2z+z^3-z^4+z^6}}\\ &=1+2z+4z^2+8z^3+15z^4+27z^5+\color{blue}{49}z^6+89z^7+\cdots \end{align*} where the last line was calculated with the help of Wolfram Alpha.

Result: The blue marked coefficient of $z^{6}$ shows there are $\color{blue}{49}$ words of length $6$ over the alphabet $\mathcal{V}$ which do not contain $0110$ or $11010$. These $49$ words are \begin{align*} \begin{array}{cccccc} 000000&000001&000010&000011&000100&000101\\ 000111&001000&001001&001010&001011&001110\\ 001111&010000&010001&010010&010011&010100\\ 010101&010111&011100&011101&011110&011111\\ 100000&100001&100010&100011&100100&100101\\ 100111&101000&101001&101010&101011&101110\\ 101111&110000&110001&110010&110011&110111\\ 111000&111001&111011&111100&111101&111110\\ 111111 \end{array} \end{align*} which were calculated with a few lines of code in R.