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.

  • $\begingroup$ I guess you need to reconsider the problem. there are no room left for any zero now! $\endgroup$ – Maesumi Jun 12 '13 at 23:18
  • $\begingroup$ 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. $\endgroup$ – nonion Jun 12 '13 at 23:22
  • $\begingroup$ What is a decomposition? Do you mean representation? $\endgroup$ – apnorton Jun 12 '13 at 23:26
  • $\begingroup$ Yes that is what I mean, for example, a list of binary strings can be presented as {0}*{1} = 01,001,0001,etc $\endgroup$ – 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.

This is a related question.


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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.