2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by 'fraction'? And what is your question? $\endgroup$ – Stefan Mesken Feb 23 '16 at 23:01
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks. Excellent answer... but this is still an act of curve fitting (albeit a principled one). (I found the same answer by simple simulation and curve fitting.) I was hoping for an exact relation, so that I could find the rational number for arbitrary $n$, rather than an excellent approximation. Upvote, but not (yet) fully accepted. $\endgroup$ – David G. Stork Feb 23 '16 at 23:15
  • 1
    $\begingroup$ The fraction is the real root of the polynomial $z^3 - z^2 + z/4 - 1/8$. $\endgroup$ – Robert Israel Feb 23 '16 at 23:19
  • $\begingroup$ I don't understand what you mean by curve fitting. The recurrence is derived from the rule and is exact. You can then get exact expressions for the roots of the associated fourth degree polynomial as here from Alpha and get an exact expression using the first four values as with a standard recurrence relation. It is a mess. I just picked off the largest approximate root for the last sentence. $\endgroup$ – Ross Millikan Feb 23 '16 at 23:20
  • 1
    $\begingroup$ Not so bad: it's a cubic, not a quartic (look at the generating function). Expressed in radicals, that is $$ \dfrac{1}{3} + \dfrac{1}{12} (100 + 12 \sqrt{69})^{1/3} + \dfrac{1}{3} (100 + 12 \sqrt{69})^{-1/3}$$ $\endgroup$ – Robert Israel Feb 23 '16 at 23:23
  • $\begingroup$ Ross: OK... Using a recurrence relation one can find the terms and divide the appropriate one by $2^n$ to get that fraction. I suppose this is the best that can be achieved. Thanks. [Accepted] $\endgroup$ – David G. Stork Feb 23 '16 at 23:24
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.