Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Good work. The lack of an explicit formula in oeis.org/A177790 suggests that finding one is hard. –  Ross Millikan Dec 8 '12 at 18:27
    
By an probabilistic argument, I'm getting $ \log(N(n)) \to (n /2) \log(27/4) $. If you are interested in asymptotics, I'll post details. –  leonbloy Dec 9 '12 at 12:59
    
@leonboy sure I am interested in them. If you would be so kind to post some extra –  barto Dec 10 '12 at 16:27

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
Starting from your $h(z)$ (which I had also obtained by other means) it is possible to obtain a recursion formula for the number $g_n$ of such sequences of length $2n$. See my edit. –  Christian Blatter Dec 16 '12 at 14:46

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.

share|improve this answer
    
This kind of approach is new to me. Could you please explain me what is exactly meant with $f_{00}$, $f_{01}$, ... ? –  barto Dec 10 '12 at 21:21
    
@barto: See my edit. –  Christian Blatter Dec 11 '12 at 10:16
    
@ChristianBlatter: It is indeed possible to get an expression for the coefficient of $x^n y^n$. I've added an answer with the details. –  David Bevan Dec 14 '12 at 9:39

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.

share|improve this answer
    
$\lim\limits_{n\rightarrow\infty}\log(N(n))= n\log\left(\frac{1}{2}(3+\sqrt{5})\right)\approx 0.962424 n$; for details see my answer below. –  David Bevan Dec 14 '12 at 10:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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