Find the generating function for this set of strings

Question

Let $a(n)$ be the number of $\{0,1\}$-strings of length $n$ which contain no $4$ consecutive $1$'s and no $4$ consecutive $0$'s (don't contain "$0000$" or "$1111$"). Find the generating function for this.

Thank you.

Answer 1

Let $a(n)$ denote the number of admissible binary strings of length $n$. First, note that precisely half of the strings of any length end in $\color{red}{0}$ (or $\color{green}{1}$). Now, for a string of length $n>4$, there are $8$ possible endings with the following numbers of occurrences:

$$\begin{align*} &\overbrace{\ldots???\color{green}{1}}^{\text{length }n-3}\color{red}{0}\color{red}{0}\color{red}{0}\quad\tfrac{1}{2}a(n-3)\\\ &\ldots????\color{red}{0}\color{red}{0}\color{green}{1}\quad\tfrac{1}{2}a(n-4)+\tfrac{1}{2}a(n-3)\\ &\ldots????\color{red}{0}\color{green}{1}\color{red}{0}\quad\tfrac{1}{2}a(n-2)\\ &\ldots????\color{red}{0}\color{green}{1}\color{green}{1}\quad\tfrac{1}{2}a(n-2)\\ &\ldots????\color{green}{1}\color{red}{0}\color{red}{0}\quad\tfrac{1}{2}a(n-2)\\ &\ldots????\color{green}{1}\color{red}{0}\color{green}{1}\quad\tfrac{1}{2}a(n-2)\\ &\ldots????\color{green}{1}\color{green}{1}\color{red}{0}\quad\tfrac{1}{2}a(n-4)+\tfrac{1}{2}a(n-3)\\ &\underbrace{\ldots???\color{red}{0}}_{\text{length }n-3}\color{green}{1}\color{green}{1}\color{green}{1}\quad\tfrac{1}{2}a(n-3) \end{align*}$$

Summing up, we obtain the following recursion formula:

$$a(n)=2a(n-2)+2a(n-3)+a(n-4)$$

Finally, we determine $a(n)$ from the initial values

$$a(1)=2, a(2)=4, a(3)=8, a(4)=14.$$

Reassuring note:

Substituting $a(n-1)=a(n-2)+a(n-3)+a(n-4)$ in $\textbf{Calvin Lin}$'s recurrence relation $a(n)=a(n-1)+a(n-2)+a(n-3)$, we obtain agreement.

Answer 2

Let $A_n$ be the number of ways to write $n$ with your conditions.

Hint: By considering the initial string of similar digits, show that $A_n = A_{n-1} + A_{n-2} + A_{n-3}$.

Use the initial conditions that $A_1 = 2, A_2 = 4, A_3 = 8 $.

Answer 3

Such a string consists of a (possibly empty) sequence of elements from {01, 011, 0111, 001, 0011, 00111, 0001, 00011, 000111} — i.e. {0|00|000}{1|11|111} — optionally preceded by 1, 11 or 111 and optionally followed by 0, 00 or 000. So the generating function is $$ \frac{(1+z+z^2+z^3)^2}{1-(z+z^2+z^3)^2}, $$ the numerator reflecting the optional prefix and suffix, and the denominator reflecting the sequence.

This is a related question.