Contando las secuencias binarias con no más de $2$, iguales y consecutivas de números

Question

Yo inventé el siguiente problema, pero no puedo resolverlo.

Hay $n$ $1$'s y $n$ $0$'s y mi pregunta es ¿cuál es el número de maneras de organizar ellos evitando $3$ igualdad de números consecutivos.

Así, por ejemplo, $n=3$ da 001011, 001101, 010011, 010101, 010110, 011001, 011010, y las mismas secuencias que comienzan con $1$, $14$ en total. Los primeros valores son: $2,6,14,34,84,208$. (a partir de la con $n=1$) parece ser casi una función exponencial.

Empecé a definir la función $N(a,b)$ que da a todas las posibles secuencias con $a$ ceros y $b$, que no $3$ números consecutivos son iguales, y que comienzan con una $0$. El mismo para $E(a,b)$ que da a todas las posibles secuencias con $a$ ceros y $b$, que no $3$ números consecutivos son iguales, y que comienzan con una $1$. No es difícil ver que $N(a,b)=E(b,a)$.

He encontrado una especie de fórmula recursiva para $N(a,b)$.

Dicha secuencia puede comenzar con $00$. El resto es una secuencia que comienza con un $1$, lo que da $E(a-2,b)=N(b,a-2)$ posibilidades.

Si se inicia con $01$, cada cola es posible a menos que aquellos que comienzan con $11$. La pregunta es ¿este número de secuencias que comienzan con $11$. Pero debido a que después de estos dos $1$'s viene de una $0$, es simplemente $N(a-1,b-3)$.

La adición de todo lo que hasta da $$N(a,b)=N(a-1,b-1)+N(b-1,a-1)+N(b,a-2)-N(a-1,b-3).$$

Este es otro enfoque de la mina:

Cada secuencia se compone de un cierto número de serie de $1$'s y de $0$'s. Deje $n$ ser divisible por $2$ (El otro caso es casi el mismo.)

El número de serie es, al menos, $n/2$ y en la mayoría de las $n$. El número de $0$-de la serie puede ser igual o más, a continuación, el número de $1$de la serie. Debido a que cada serie tiene al menos un elemento, el total es de $$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)$$, pero esta suma no es digno de ser llamado a una solución. Y yo no se puede simplificar.

Eso es todo lo que he encontrado. Tal vez estos OEIS referencias pueden ayudarle a responder a mi pregunta:

http://oeis.org/A177790

http://oeis.org/A003440

Y aquí está una lista de $N(a,b)$ $a,b\leq 10$. ($a$ aumenta a la derecha y $b$ aumenta hacia abajo)

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

(Siempre se puede hacer más, si alguien me lo pide.)

Answer 1

Voy a completar el trabajo iniciado por Christian Blatter:

Vamos $$ 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)} $$ como se indicó anteriormente.

Tenga en cuenta, que de esta manera se sigue inmediatamente del hecho de que permitió palabras constan de una secuencia de elementos de {01, 011, 001, 0011} opcionalmente precedido por 1 o 11 y seguido por 0 o 00. Por lo tanto la clase de palabras es $$ \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) $$ lo que se traduce directamente para dar a $s(x,y)$.

Si nos vamos a $$ 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}},$$ a continuación, el término constante de $g(x)$ (es decir, el coeficiente de $x^0$ en la expansión de $g(x)$) da a la generación de la función $h(z)$ para las secuencias con el mismo número de $0$s y $1$s donde el exponente de $z$ registros de la mitad de longitud. Esto es lo que requerimos.

Ahora, el término constante en función de $g(x)=g(z,x)$ está dada por la suma de los residuos de $g(x)/x$ en los polos $\alpha$ $g(x)$ que $\lim\limits_{z\rightarrow0}\alpha(z)=0$ (ver, por ejemplo, Stanley, la Combinatoria Enumerativa II Secc. 6.3).

Sigue siendo simplemente para trabajar a través de los detalles. Hay dos adecuada polos (en$x=0$$x=\frac{1-z-z^2-\sqrt{1-2 z-z^2-2 z^3+z^4}}{2 z \sqrt{z}}$). Sumando los residuos de $g(x)/x$ en estos valores da $$ h(z)\;=\; \frac{(1-z)^2 \sqrt{1+z+z^2}}{z^2 \sqrt{1-3 z+z^2 }} -\frac{1}{z^2}. $$ Dado que el radio de convergencia de $h(z)$$\frac{1}{2} \left(3-\sqrt{5}\right)$, la tasa de crecimiento es su recíproco $\frac{1}{2} \left(3+\sqrt{5}\right) \approx 2.56126$.

Answer 2

El siguiente es un primer paso para eliminar la combinatoria de la forma.

Trabajamos en el ámbito del poder formal de la serie. Vamos $x$, $y$ ser indeterminates y asignar los $01$-palabra con $r$ ceros y $s$ que "vale la pena" $x^r y^s$. Denotan por $f_0(x,y)$ $f_1(x,y)$ el valor total de los permitidos palabras que terminan en $0$, resp. $1$. Entonces $$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(*)$$ Estas ecuaciones pueden explicarse de la siguiente manera: Usted obtener cualquier permitido palabra que termina con $0$ escrito $0$ o $00$ después de la palabra vacía o después de una palabra que termina con $1$. Así el valor de cada uno de los afectados palabra toma un factor de $x$ o $x^2$. El valor total de todas las palabras creadas de esta manera es el lado derecho de la primera ecuación. La segunda ecuación se explica de manera similar.

Uno puede resolver las ecuaciones $(*)$$f_i(x,y)$. De ello se deduce que el valor total de todos los permitidos palabras está dada por $$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)}\ .$$ Se sigue para calcular el coeficiente de $g_n$ $x^n y^n$ en la serie de Taylor de $s(x,y)$. En su respuesta, David Bevan ha determinado la generación de la función de la $g_n$, es decir, $A$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}\ .$$

No es difícil comprobar que la función $g(z):=h(z)-1$ satisface la ecuación cuadrática

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

A partir de esta ecuación podemos extraer una fórmula de recursión para el $g_n$: Uno tiene $$g_n=0\quad (n\leq 0),\quad g_1=2\ ,$$ y, a continuación, $$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)\ .$$ Esta fórmula produce por $n\geq1$ los valores $$2, 6, 14, 34, 84,208, 518, 1296, \ldots\quad,$$ como se enumeran en http://oeis.org/A177790, citado por el OP.

Answer 3

He aquí algunos asymptotics de un (no muy riguroso) probabilístico argumento:

Deje ${\bf x} = (x_i), \;i= 1,2, \dots 2m$, se $2m$ geométrica iid variables con $p=1/2$, $p(x_i)=2^{-x_i}$, $x_i \in \{ 1,2,3, \dots\}$ (estos corresponden a la ejecución de las longitudes de 0s y 1s en el problema original).

Vamos $s_1=\sum_{i=1}^m x_i$ , $s_2=\sum_{i=m+1}^{2m} x_i$ ser la suma de cada mitad, y definir los conjuntos de eventos:

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

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

Tenga en cuenta que $p({\bf x})= 2^{-s}$, por lo tanto los puntos dentro de $A$ (fija $s=s_1+s_2=2n$) son equiprobables.

También tenga en cuenta que el condicionado de la variable $x_i | x_i\le 2$ es decir $4/3$ y la varianza $2/9$.

Ahora,

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

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

Because the set $$ se compone de equiprobables puntos, tenemos $P(A) = 2^{-2n} |A |$

Y por el mismo hecho (equiprobables puntos), $$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 de cada color (factor 2 es tener en cuenta la simetría de colores). Estamos interesados en

$$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$, la suma de cada mitad puede ser aproximada (CLT) por una normal $ \mathcal{N}(\frac{4}{3}m,\frac{2}{9}m) $ Por lo tanto

$$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 $=\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) \aprox 2 \sum {k \elegir n-k}^2$ with ${m \elegir p m} \approx \exp(m H(p))$, el cambio de la suma integral y el uso de la misma y la sustitución de Laplace método. Da el mismo resultado como la de David respuesta.