Intereting Posts

Pigeonhole Principle Question: Jessica the Combinatorics Student
Do torsionfree abelian groups form a (possibly many-sorted) algebraic category?
Special Differential Equation (continued-2)
For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$
Simple upper bound for $\binom{n}{k}$
Recurrence Relation Solving Problem
Is there any geometric explanation of relationship between Integral and derivative?
How do you show that $f(x) = e^{-x^2}$ is in the Schwartz space $\mathcal{S}(\Bbb{R})$?
Is any quotient of a Euclidean domain by a prime ideal a Euclidean domain?
Determinant of rank-one perturbations of (invertible) matrices
Reflections on math education
Without using prime factorization, find a prime factor of $\frac{(3^{41} -1)}{2}$
Sum of these quotient can not be integer
Measuring $\pi$ with alternate distance metrics (p-norm).
If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.

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.

- Maximum number of edges in a simple graph?
- How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$?
- All the ternary n-words with an even sum of digits and a zero.
- Wanted: Insight into formula involving binomial coefficients
- Induction proof of $\sum_{k=1}^{n} \binom n k = 2^n -1 $
- When adding zero really counts …

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

- How to solve $ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5\,$?
- Closed form of a partial sum of the power series of $\exp(x)$
- Combinatorial proof involving factorials
- 101 positive integers placed on a circle
- Mathematical proof for long-term behavior of a sequence of integer vectors
- Divisibility and Pigeonhole principle
- Choice Problem: choose 5 days in a month, consecutive days are forbidden
- How to understand the combination formula?
- Combinatorial Interpretation of a Certain Product of Factorials
- Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

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

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.

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.

- Size of a family of sets $F$ such that if $|A\cap X|=|B\cap X|$ for all $X\in F$, then $A=B$
- $\ell^p\subseteq\ell^q$ for $0<p<q<\infty$ and $\|\cdot\|_p<\|\cdot\|_q$
- Probability distribution in the coupon collector's problem
- If $(A-\lambda{I})$ is $\lambda$-equivalent to $(B-\lambda{I})$ then $A$ is similar to $B$
- Prove there is no contraction mapping from compact metric space onto itself
- How many field structures does $\mathbb{R}\times \mathbb{R}$ have?
- Computing $x^{2017}+\frac1{x^{2017}}$ given the value of $x+\frac1x$.
- Construction of an exact sequence $1 \to N_{16} \to G_{64} \to \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \to 1$
- Showing a compact metric space has a countable dense subset
- List of interesting integrals for early calculus students
- How to evaluate $ \sum\limits_{n=1}^{\infty} \left( \frac{H_{n}}{(n+1)^2.2^n} \right)$
- Why is the determinant equal to the index?
- Evaluating $\int P(\sin x, \cos x) \text{d}x$
- Can an eigenvalue (of an $n$ by $n$ matrix A) with algebraic multiplicity $n$ have an eigenspace with fewer than $n$ dimensions?
- Homeomorphism of the real line-Topology