Fraction of length-$n$ binary numbers satisfying a constraint

Question

Problem: Derive an expression for the fraction of length-$n$ binary numbers that do not contain the subsequence $010$.

Background: The total number of $n$-bit binary numbers is of course $2^n$. Some of these numbers have the sequence $010$ within it; others do not. In short, the problem is to determine, for a given $n$:

${{\rm number\ of\ sequences\ without\ 010} \over 2^n}$.

Although it is a simple matter to determine this fraction through simulation and curve fitting, it is rather tricky to determine the fraction through combinatorics or other rigorous means.

Clearly for $n=3$, there are $2^3 = 8$ possible binary numbers of length $3$ and only one of them is $010$. Thus for $n=3$, the fraction is:

${7 \over 8}$.

Background reading: Binary strings without zigzags and a related question.

Answer 1

The sequence is given in OEIS A005251 with a recurrence $a(n)=a(n-1)+a(n-2)+a(n-4)$ and begins $1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525$ It grows about as $1.7549^n$ so the fraction is about $0.8774^n$

Answer 2

Let $a_n$ be the number of admissible sequences ending in $0$, let $b_n$ be the number of admissible sequences ending in $01$, and let $c_n$ be the number of admissible sequences ending in $11$. Then

\begin{align} a_{n+1}&=a_n+c_n\;,\\ b_{n+1}&=a_n\;,\\ c_{n+1}&=b_n+c_n\;, \end{align}

or

$$ \pmatrix{a\\b\\c}_{n+1}=\pmatrix{1&0&1\\1&0&0\\0&1&1}\pmatrix{a\\b\\c}_n\;. $$

Then with $d_n=a_n+b_n+c_n$ the total number of admissible sequences, we have

\begin{align} d_{n+1}&=d_n+a_n+c_n\\ &=d_n+a_{n-1}+c_{n-1}+b_{n-1}+c_{n-1}\\ &=d_n+d_{n-1}+c_{n-1}\\ &=d_n+d_{n-1}+b_{n-2}+c_{n-2}\\ &=d_n+d_{n-1}+a_{n-3}+b_{n-3}+c_{n-3}\\ &=d_n+d_{n-1}+d_{n-3}\;, \end{align}

the recurrence that Ross quoted from OEIS. The growth rate is then obtained as the solution of the characteristic equation

$$ \lambda^4-\lambda^3-\lambda^2-1=0 $$

with highest magnitude. The solution $\lambda=-1$ can be guessed, and the factored equation

$$ (\lambda^3-2\lambda^2+\lambda-1)(\lambda+1)=0 $$

has, according to Wolfram|Alpha, the real solution

$$ \lambda=\frac16\left(4+\sqrt[3]{100-12\sqrt{69}}+\sqrt[3]{100+12\sqrt{69}}\right)\approx1.7549\;. $$

Answer 3

I upvoted the answer by @Joriki which is exemplary.

This can also be done using generating functions.

We get

$$G(z) = \frac{1}{1-z} + \frac{1}{1-z} \frac{z}{1-z} \sum_{q\ge 0} \left(\frac{z^2}{1-z}\frac{z}{1-z}\right)^q \frac{1}{1-z}.$$

Explanation: first term a string of ones. Remaining term: admissible sequences containing at least one zero. This is

$$1^* 0^+ (11^+ 0^+)^* 1^*.$$

We thus obtain

$$G(z) = \frac{1}{1-z} + \frac{z}{(1-z)^3} \frac{1}{1-z^3/(1-z)^2} = \frac{1}{1-z} + \frac{z}{1-z} \frac{1}{1-2z+z^2-z^3} \\ = \frac{z+1-2z+z^2-z^3}{1-z} \frac{1}{1-2z+z^2-z^3} = \frac{1-z+z^2-z^3}{1-z} \frac{1}{1-2z+z^2-z^3} \\ = \frac{1+z^2}{1-2z+z^2-z^3}.$$

Now the dominant contribution (the asymptotical factor being sought) emerges from the inverses of the poles, i.e. the roots of

$$z^3(1-2/z+1/z^2+1/z^3) = z^3-2z^2+z-1.$$

Using a computer algebra system we find the dominant root to be $$1.754877667$$ and the rest continues as before.

The dominant contribution emerges from the inverses because the poles are all simple and hence we have

$$\frac{1+z^2}{1-2z+z^2-z^3} = \sum_{1-2\rho+\rho^2-\rho^3 = 0} \frac{1}{z-\rho} \mathrm{Res}_{z=\rho} \frac{1+z^2}{1-2z+z^2-z^3}$$

and

$$\frac{1}{z-\rho} = - \frac{1}{\rho} \frac{1}{1-z/\rho}.$$