# Find the generating function for this set of strings

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.

• I guess you need to reconsider the problem. there are no room left for any zero now! – Maesumi Jun 12 '13 at 23:18
• Sorry that isn't what I meant. What I meant was just to get a binary decomposition, such that the number of 0's + number of 1's = n, given that there can be no 4 consecutive 0's and no 4 consecutive 1's. – nonion Jun 12 '13 at 23:22
• What is a decomposition? Do you mean representation? – apnorton Jun 12 '13 at 23:26
• Yes that is what I mean, for example, a list of binary strings can be presented as {0}*{1} = 01,001,0001,etc – nonion Jun 12 '13 at 23:29

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$.

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.

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.