Counting binary sequences with no more than $2$ equal consecutive numbers

Question

I invented the following problem, but I can't solve it.

There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers.

So for instance, $n=3$ gives 001011, 001101, 010011, 010101, 010110, 011001, 011010, and the same sequences that start with $1$, that's $14$ in total. The first values are: $2,6,14,34,84,208$. (starting with $n=1$) It seems to be almost an exponential function.

I started defining the function $N(a,b)$ which gives all possible sequences with $a$ zeroes and $b$ ones such that no $3$ consecutive numbers are equal, and that begin with a $0$. The same for $E(a,b)$ which gives all possible sequences with $a$ zeroes and $b$ ones such that no $3$ consecutive numbers are equal, and that begin with a $1$. It's not hard to see that $N(a,b)=E(b,a)$.

I found a kind of recursive formula for $N(a,b)$.

Such a sequence can start with $00$. The rest of it is a sequence that starts with a $1$, that gives $E(a-2,b)=N(b,a-2)$ possibilities.

If it starts with $01$, every tail is possible unless those that start with $11$. The question is what this number of sequences is that start with $11$. But because after these two $1$'s comes a $0$, it's simply $N(a-1,b-3)$.

Adding everything up gives $$N(a,b)=N(a-1,b-1)+N(b-1,a-1)+N(b,a-2)-N(a-1,b-3).$$

This is another approach of mine:

Every sequence consists a certain number of series of $1$'s and of $0$'s. Let $n$ be divisible by $2$ (The other case is almost the same.)

The number of series is at least $n/2$ and at most $n$. The number of $0$-series can be equal to or one more then the number of $1$-series. Because every series has at least one element, the total is $$N(a,a)=1+\sum_{k=n/2}^{n-1}\binom{k}{n-k}\left(\binom{k}{n-k}+\binom{k+1}{n-k-1}\right)$$ but this summation is not worth being called a solution. And I can't simplify it.

That's all I have found. Maybe these OEIS references may help you answering my question:

http://oeis.org/A177790

http://oeis.org/A003440

And here's a list of $N(a,b)$ for $a,b\leq 10$. ($a$ increases to the right and $b$ increases downwards)

$$\begin{array}{|c|c|} \hline b\backslash a&0&1&2&3&4&5&6&7&8&9&10\\ \hline 0&&1&1&0&0&0&0&0&0&0&0\\ \hline 1&0&1&2&2&1&0&0&0&0&0&0\\ \hline 2&0&1&3&5&5&3&1&0&0&0&0\\ \hline 3&0&0&2&7&12&13&9&4&1&0&0\\ \hline 4&0&0&1&6&17&29&33&26&14&5&1\\ \hline 5&0&0&0&3&16&42&71&84&72&45&20\\ \hline 6&0&0&0&1&10&42&104&175&214&196&136\\ \hline 7&0&0&0&0&4&30&110&259&434&545&527\\ \hline 8&0&0&0&0&1&15&86&286&648&1082&1389\\ \hline 9&0&0&0&0&0&5&50&241&741&1627&2709\\ \hline 10&0&0&0&0&0&1&21&156&663&1916&4098\\ \hline \end{array}$$

(I can always make it longer if someone asks me to.)

Answer 1

I'll complete the work begun by Christian Blatter:

Let $$ s(x,y) \;=\; \frac {\left(1+x+x^2\right) \left(1+y+y^2\right)} {1-\left(x+x^2\right) \left(y+y^2\right)} $$ as above.

Note, that this follows immediately from the fact that allowed words consist of a sequence of elements from {01, 011, 001, 0011} optionally preceded by 1 or 11 and followed by 0 or 00. Hence the class of allowed words is $$ \mathcal{S}\;=\; (\mathcal{E}+\mathcal{Z_1}+\mathcal{Z_1}^2) \times \text{SEQ}((\mathcal{Z_0}+\mathcal{Z_0}^2)\times(\mathcal{Z_1}+\mathcal{Z_1}^2)) \times (\mathcal{E}+\mathcal{Z_0}+\mathcal{Z_0}^2) $$ which translates directly to give $s(x,y)$.

If we let $$ g(x) \;=\; g(z,x) \;=\; s(x\sqrt{z},\sqrt{z}/x) \;=\; \frac {\left(x^2+x \sqrt{z}+z\right) \left(1+x \sqrt{z}+x^2 z\right)} {x^2 (1 - z - z^2) - x (1 + x^2) z \sqrt{z}},$$ then the constant term of $g(x)$ (i.e. coefficient of $x^0$ in the expansion of $g(x)$) gives the generating function $h(z)$ for sequences with the same number of $0$s and $1$s where the exponent of $z$ records the half-length. This is what we require.

Now, the constant term in a function $g(x)=g(z,x)$ is given by the sum of the residues of $g(x)/x$ at those poles $\alpha$ of $g(x)$ for which $\lim\limits_{z\rightarrow0}\alpha(z)=0$ (see e.g. Stanley, Enumerative Combinatorics II Sect. 6.3).

It simply remains to work through the details. There are two suitable poles (at $x=0$ and $x=\frac{1-z-z^2-\sqrt{1-2 z-z^2-2 z^3+z^4}}{2 z \sqrt{z}}$). Summing the residues of $g(x)/x$ at these values gives $$ h(z)\;=\; \frac{(1-z)^2 \sqrt{1+z+z^2}}{z^2 \sqrt{1-3 z+z^2 }} -\frac{1}{z^2}. $$ Since the radius of convergence of $h(z)$ is $\frac{1}{2} \left(3-\sqrt{5}\right)$, the growth rate is its reciprocal $\frac{1}{2} \left(3+\sqrt{5}\right) \approx 2.56126$.

Answer 2

The following is a first step to remove the combinatorics out of the way.

We work in the realm of formal power series. Let $x$, $y$ be indeterminates and assign any $01$-word with $r$ zeros and $s$ ones the "worth" $x^r y^s$. Denote by $f_0(x,y)$ and $f_1(x,y)$ the total worth of the allowed words ending in $0$, resp. $1$. Then $$f_0(x,y)=\bigl(1+f_1(x,y)\bigr)(x+x^2)\ ,\qquad f_1(x,y)=\bigl(1+f_0(x,y)\bigr)(y+y^2)\ .\qquad(*)$$ These equations can be explained as follows: You get any allowed word ending with $0$ by writing $0$ or $00$ after the empty word or after an allowed word ending with $1$. Thereby the worth of each affected word takes up a factor $x$ or $x^2$. The total worth of all words created in this way is the right side of the first equation. The second equation is explained similarly.

One can solve the equations $(*)$ for the $f_i(x,y)$. It follows that the total worth of all allowed words is given by $$s(x,y)=1 +f_0(x,y)+f_1(x,y)={(1+x+x^2)(1+y+y^2)\over1- (x+x^2)(y+y^2)}\ .$$ It remains to compute the coefficient $g_n$ of $x^n y^n$ in the Taylor series of $s(x,y)$. In his answer David Bevan has determined the generating function of the $g_n$, namely $$1+\sum_{n=1}^\infty g_n(z)= h(z)\;=\; \frac{(1-z)^2 \sqrt{1+z+z^2}}{z^2 \sqrt{1-3 z+z^2 }} -\frac{1}{z^2}\ .$$

It is not difficult to verify that the function $g(z):=h(z)-1$ satisfies the quadratic equation

$$(1-3z+z^2) g(z)\Bigl(1+z^2 +{z^2\over2}g(z)\Bigr)-2z\equiv0\ .$$

From this equation we can distill a recursion formula for the $g_n$: One has $$g_n=0\quad (n\leq 0),\quad g_1=2\ ,$$ and then $$g_n=3 g_{n-1}-2 g_{n-2}+3 g_{n-3}- g_{n-4}-{1\over2}\sum_{k=1}^{n-3}\bigl(g_k-3 g_{k-1}+g_{k-2}\bigr) g_{n-k-2}\qquad(n\geq2)\ .$$ This formula produces for $n\geq1$ the values $$2, 6, 14, 34, 84,208, 518, 1296, \ldots\quad,$$ as listed in http://oeis.org/A177790, quoted by the OP.

Answer 3

Here's some asymptotics from a (not very rigorous) probabilistic argument:

Let ${\bf x} = (x_i), \;i= 1,2, \dots 2m$, be $2m$ geometric iid variables with $p=1/2$, $p(x_i)=2^{-x_i}$, $x_i \in \{ 1,2,3, \dots\}$ (these correspond to the run lengths of 0s and 1s in the original problem).

Let $s_1=\sum_{i=1}^m x_i$ , $s_2=\sum_{i=m+1}^{2m} x_i$ be the sums of each half, and define the sets-events:

$A: s_1=n \cap s_2=n$

$C: x_i \le 2 \,\, \forall i$

Note that $p({\bf x})= 2^{-s}$, hence the points inside $A$ (fixed $s=s_1+s_2=2n$) are equiprobable.

Also note that the conditioned variable $x_i | x_i\le 2$ has mean $4/3$ and variance $2/9$.

Now,

$$ P(C| A) = \frac{P(A |C)\, P(C)}{P(A)}$$

where $P(C)= \left(3/4\right)^{2m} $

Because the set $A$ is composed of equiprobable points, we have $P(A) = 2^{-2n} |A |$

And because of the same fact (equiprobable points), $$P(C| A ) = \frac{|A \cap C|}{|A|}$$

Then $$ |A \cap C| = 4^n \left(3/4\right)^{2m} P(A|C) =N(n,m)$$

where $2 N(n,m)$ counts all the valid configurations with $m$ runlengths of each color (factor 2 is to account for symmetry of colours). We are interested in

$$N(n)=\sum_m 4 N(n,m)$$

(the extra 2 factor accounts -approximation that could be refined- for the configurations which runlengths differ in one).

First approximation: $P(A|C)$ is peaked around $ 4/3 m=n$. Just replacing we get

$$ \log N(n) \approx \frac{n}{2} \log (27/4) $$

but this is very rough.

Better approximation:

For each fixed $m$, the sum of each half can be approximated (CLT) by a normal $ \mathcal{N}(\frac{4}{3}m,\frac{2}{9}m) $ Hence

$$P(A|C) \approx \left( \frac{1}{\sqrt{2 \pi 2 m/9}} \exp{[-\frac{(3n-4m)^2}{4m}}]\right)^2$$

We approximate the sum on $m$ by a integral, and substitute $m=r n$.

$$N(r) \approx \alpha 4^n \int \frac{1}{r} (3/4)^{rn} e^{-n\frac{(3-4r)^2}{2r}} dr= \alpha \int \frac{1}{r} exp\left(n \left[ b + 2 a r -\frac{(3-4r)^2}{2r} \right] \right) dr= $$

with $a=\log(3/4)$, $b=\log(4)$. Applying Laplace method, the function inside the exponential has maximum at $r_0=\frac{3}{2\,\sqrt{4-\mathrm{log}\left( \frac{3}{4}\right) }}=0.7244...$ and its value is $$f_0 = \mathrm{log}\left( 4\right) -6\,\sqrt{4-\mathrm{log}\left( \frac{3}{4}\right) }+12 =0.96226302631297$$

Then,

$\log(N(n)) = 0.96226302631297 n - \frac{1}{2}\log(n) + o(\log(n))$

Some computed exact values of $log(N)$ and the error of the approximation above (and the "zero order" one.

  n    exact      apr    apr0
 10    9.0114  -0.5401   0.5363
 20   18.3564  -0.609    0.739
 30   27.802   -0.6347   0.8411
 40   37.2947  -0.6486   0.8962
 50   46.8149  -0.6578   0.9237
100   94.6049  -0.6812   0.8722
150  142.5286  -0.6945   0.6871
250  238.5197  -0.7147   0.1731
350  334.5956  -0.7325  -0.4257
450  430.7133  -0.7496  -1.0662
550  526.8560  -0.7663  -1.7318
650  623.0153  -0.7828  -2.414
750  719.1864  -0.7992  -3.108

Update: a much simpler (and perhaps more precise) asymptotic can be obtained by using $N(n) \approx 2 \sum {k \choose n-k}^2$ with ${m \choose p m} \approx \exp(m H(p))$, changing sum by integral and using the same substitution and Laplace method. It gives the same result as David's answer.