¿Cuántas cadenas de n bits tienen a lo sumo m 0s posteriores?

Question

El título ya es la pregunta completa, pero me gustaría añadir algunos detalles para dejar claro lo que quiero decir.

A $n$ -La cadena de bits es un elemento de $\{0,1\}^n$ . Todas las posibles cadenas de 3 bits son:

• 0: 000
• 1: 001
• 2: 010
• 3: 011
• 4: 100
• 5: 101
• 6: 110
• 7: 111

Como se pueden codificar como números binarios, hay $2^n$ $n$ -cadenas de bits. Si quiero como máximo $m=1$ subsecuentes 0s, las secuencias permitidas son:

• 2: 010
• 3: 011
• 5: 101
• 6: 110
• 7: 111

Por lo tanto, para $n=3, m=1$ la respuesta es 5.

¿Cuál es la respuesta a la arbitrariedad? $n \in \mathbb{N}$ y $m \in \{0, \dots, n\}$ ? ¿Cuál es la respuesta para $n=30, m=4$ ?

Antecedentes de la cuestión

Este es el fondo de mi pregunta. No es necesario entenderlo / responderlo.

He desarrollado una aplicación de reconocimiento de símbolos (ver http://write-math.com ) y ahora estoy pensando en diferentes posibilidades para ampliarlo al reconocimiento de fórmulas. Una parte del reconocimiento de fórmulas consiste en reconocer los símbolos individuales.

Obtengo datos en línea, lo que significa que obtengo la información de cómo se escribe el símbolo (en contraste con los datos fuera de línea, donde sólo tienes píxeles). Mis datos son una lista de trazos, donde cada trazo es un punto. Un punto tiene coordenadas x/y y un tiempo:

[[(x=12, y=21, t=0), (x=7, y=13, t=3), ((x=7, y= 21, t=5), ...],
 [(x=0, y=0, t=6)],
 [...], ...]

Ahora sé que la gente siempre segmenta perfectamente sus símbolos. Eso significa que un símbolo puede tener varios trazos, pero un trazo siempre pertenece exactamente a un símbolo. Como tengo un reconocedor de símbolos que funciona bastante bien, sería posible utilizarlo simplemente para reconocer múltiples símbolos probando todas las segmentaciones posibles. Esto se puede modelar tomando un $n$ -cadena de bits para $n+1$ golpes. Si un bit determinado es 0, los trazos vecinos están conectados:

stroke1   stroke2   stroke3
        0         1

Stroke1 and stroke2 are connected, but separated from stroke3
Hence the first symbol has the first 2 strokes,
the second symbol has the last stroke

Sé que los símbolos con más de 4 golpes son muy raros. Tan raros que no utilizo ningún trazo después del cuarto para reconocerlos. Por lo tanto, no necesito comprobar $2^n$ segmentación, pero menos. Mi pregunta es cuántas segmentaciones tengo que comprobar.

Answer 1

Fijemos el valor de $m$ sólo para que quede claro. Por ejemplo, dejemos que $m=3$ .

Dejemos que $E_n$ sea el conjunto de cadenas binarias con $n$ bits y sin $m$ ceros consecutivos. Sea $A_n=|E_n|$ .

Tenemos $A_0=1,A_1=2,A_2=4$ ya que la restricción del número de ceros no afecta a las cadenas con menos de tres bits. Supongamos que $n\geq 3$ y que $\sigma$ sea un elemento de $E_n$ . $\sigma$ puede ser sólo:

• a $1$ seguido de un elemento de $E_{n-1}$ ;
• a $01$ seguido de un elemento de $E_{n-2}$ ;
• a $001$ seguido de un elemento de $E_{n-3}$

de ahí que tengamos la recursión: $$ A_{n} = A_{n-1}+A_{n-2}+A_{n-3} $$ con el polinomio característico $x^3-(x^2+x+1)$ . Una fórmula explícita para $A_n$ por lo tanto, se puede derivar de la misma manera que obtenemos una fórmula cerrada para los números de Fibonacci:

$$ A_n = k_1 \zeta_1^n + k_2 \zeta_2^n + k_3 \zeta_3^n $$ donde $\zeta_1,\zeta_2,\zeta_3$ son las raíces del polinomio característico y $k_1,k_2,k_3$ dependen de las condiciones iniciales $A_0=1,A_1=2,A_2=4$ .

También es interesante observar que la raíz dominante $\zeta_1$ se puede acotar multiplicando el polinomio característico por $x-1$ y luego hacer un paso del método de Newton con punto de partida $x_0=2$ . Eso nos lleva a:

$$ \zeta_1 \leq 2-\frac{1}{2^m}. $$