Número de conteos diferentes de$1$ s en ventanas deslizantes

Question

Considere la posibilidad de una tupla $A = (a_1, \dots, a_{2n-1})$ donde $a_i \in \{0,1\}$. Para cada sub-tupla de la longitud de la $n$, en orden de izquierda a derecha, que es $(a_i, \dots, a_{i+n-1})$ todos los $i$, podemos contar el número de $1$s de salida y el resultado como un "recuento de tupla". Por ejemplo, si $n = 3$ $A= (1,0,1,1,1)$ el resultado de contar tupla es $C_A = (2,2,3)$.

No todos los diferentes tupla $A$ da una diferente de contar tupla. Por ejemplo, para $n = 3$ si $A= (1,0,1,1,0)$ tenemos el recuento de tupla $C_A = (2,2,2)$ que es la misma que tenemos para $A' = (0,1,1,0,1)$.

Para un determinado$n$, ¿cuál es el número total de los distintos contar tuplas $C_A$ tomado todas las $2^{2n-1}$ posible entrada de tuplas $A$?

---

@orlp ha encontrado que $3^{n-2}(n+5)$ encaja a la perfección en $n \leq 13$. Es posible demostrar que esta es la fórmula correcta? La secuencia también se produce en https://oeis.org/A038765 .

Answer 1

Escribir la tupla $A$ en dos filas. Por ejemplo, para $n=8$, usted podría tener $$\begin{array}{rccccccc}(0&1&1&0&0&1&0&0)\\1&0&1&0&0&1&1\end{array}$$ El recuento de tupla en este ejemplo debe comenzar con $3$, el número de unos en la primera fila. Cuando la ventana se desplaza un lugar a la derecha, el primer bit en la primera fila de a gotas, mientras que el primer bit en la segunda fila entra en: $$\begin{array}{lrcccccc}\bf0&(1&1&0&0&1&0&0\\\bf1)&0&1&0&0&1&1\end{array}$$ El siguiente número en el recuento tupla debe ser uno menos, uno más, o igual que el número anterior, dependiendo del contenido de la columna: $$\begin{array}{crrc}{0\atop0}&{0\atop1}&{1\atop0}&{1\atop1 }\\\hline\text{same}&+1&-1&\text{same}\end{array}$$ Por lo que el conteo de tupla es un caminar con pasos de $-1,0,$$+1$. En este ejemplo, el pie es $(3,4,3,3,3,3,3,4)$. Sin embargo, el pie tiene condiciones: el número de $+1$ pasos no puede ser mayor que el número de ceros en la primera fila (omitiendo el final de bits), y el número de $-1$ pasos no puede ser más que el número de unos en la primera fila (omitiendo el final de bits).

Eso significa que, si el recuento de tupla se inicia con $k$, entonces:

• Si el último bit de la primera fila es $0$, luego de la caminata no contiene más de $k$ pasos hacia abajo y $n-1-k$ pasos.
• Si el último bit de la primera fila es $1$, luego de la caminata no contiene más de $k-1$ pasos hacia abajo y $n-k$ pasos.

Por lo tanto, una solución viable contar tupla se inicia con un número$k$, y es seguido por un pie de longitud $n-1$ con no más de $k$ pasos hacia abajo y no más de $n-k$ pasos. En lugar de tratar de contar en estos directamente por $k$, en lugar de imaginar que usted tiene cubiertos hasta la primera fila de algunos tupla $A$, y debe escribir un segundo. En cada paso, hay dos opciones: preguntar por el contrario poco a lo que aparece en la primera fila, o el mismo bit. Si siempre pregunte por el contrario bits, a continuación, $k$ sólo pueden tomar uno de dos valores posibles. Si usted pide una coincidencia poco en $m$ ocasiones, a continuación, $k$ puede adoptar una de las $m+2$ valores posibles. Por lo tanto, el número de posibles contar tuplas con $m$ horizontal de los pasos es $$(m+2)\cdot\binom{n-1}{m}\cdot 2^{n-1-m}$$ Suma más de $m$, se puede conseguir algo de la forma $$f(n)=2\cdot\tbinom{n-1}0\cdot 2^{n-1}+3\cdot\tbinom{n-1}1\cdot 2^{n-2}+4\cdot\tbinom{n-1}2\cdot 2^{n-3}+\cdots$$

Para simplificar esta respuesta, considere la siguiente expresión, con su expansión binomial: $$x^2(2+x)^{n-1}=2^{n-1}x^2+\tbinom{n-1}12^{n-2}x^3+\cdots$$

La diferenciación de ambos lados con respecto a $x$, consigue $$2x(2+x)^{n-1}+x^2(n-1)(2+x)^{n-2}=2x\cdot 2^{n-1}+3x^2\cdot\tbinom{n-1}1\cdot 2^{n-2}+\cdots$$

Configuración $x=1$, $$2\cdot 3^{n-1}+(n-1)\cdot 3^{n-2}=f(n)$$

Simplificando, el resultado final es $$f(n)=(n+5)\cdot 3^{n-2}$$

Answer 2

Conjetura,$f(n) = 3^{n-2}(n+5)$.

Los primeros valores reales de$f(1), f(2), \dots$ son, que son todos correctos:

ps

Mirando hacia arriba en OEIS da la fórmula anterior, y la relaciona con la cantidad de formas diferentes en que podemos tener un $$[2, 7, 24, 81, 270, 891, 2916, 9477, 30618, 98415, 314928, 1003833, 3188646]$ - catafusene , con un solo tetragón en la cadena en alguna parte.

No puedo probar la relación o la fórmula en este momento, pero parece bastante plausible.

Answer 3

Descargo de responsabilidad: lo Siento que no es correcto.

Mi conjetura es $t_n=2^{n-1}$ una vez $n>2$:

• $t_3=4=2^2$ es sólo el posible número de $1$s en tres sets.

• Si $t_n$ es conocida, entonces para cualquier tupla $A$ de la longitud de la $n$ dando un recuento $C_A$, podemos construir dos tuplas $B=A\cup \{1\}$ $B'=A\cup \{0\}$ de la longitud de la $n+1$ que darán diferentes recuentos $C_{B}$$C_{B'}$. Obviamente, todas las cuentas de construir en esa forma, con una representativos de cada uno de los cargos de la longitud de la $n$ será diferente cuenta de la longitud de la $n+1$ (n-2 primer número de diferentes, o el último difiere). Por lo tanto $t_{n+1}>=2*t_n$.

edit: la parte en negrita es malo. Voy a tratar de arreglar eso pronto...

• Inversamente, si $C_B$ es un recuento de la longitud de la $n+1$, luego se retira el último elemento de $B$ le dará una tupla de longitud $n$ $A$, por lo $t_{n+1}<=2*t_n$

• Finalmente, $t_{n+1}=2*t_n$ $t_n=2^{n-1}$ una vez $n>2$