Cuántos $a$ -secuencias narias de longitud $b$ nunca han $c$ ¿ocurrencias consecutivas de un dígito?

Question

Dejemos que $S(a,b,c): = \#\{a$ -secuencias narias de longitud $b$ sin $c$ apariciones consecutivas de un dígito $\}$ .

Por ejemplo, $S(2,n,3)$ sería el número de secuencias binarias de longitud $n$ sin $3$ ocurrencias consecutivas de un $0$ o $1$ . En particular, $S(2,n,3) = 2f_{n+1}$ El doble de $(n+1)$ El primer número de Fibonacci.

Más adelante se puede encontrar un poco más sobre este ejemplo, pero mi pregunta es:

Cuántos $a$ -secuencias narias de longitud $b$ nunca han $c$ ¿ocurrencias consecutivas de un dígito?

Reformulado,

¿Cuál es una fórmula concisa para $S(a,b,c)$ ?

Aunque hay preguntas relacionadas que se han planteado en MSE, no he visto que se plantee esta en particular con toda la generalidad.

---

Para $S(2,n,3)$ , dejemos que $f_n$ denotan el $n$ El número de Fibonacci y observa lo siguiente:

$n = 1$ : $\{0, 1\}$ . Total: $2$ es decir, $2f_{2} = 2\cdot1$ .

$n = 2$ : $\{00, 01, 10, 11\}.$ Total: $4$ es decir, $2f_{3} = 2\cdot2$ .

$n = 3$ : $\{001, 010, 011, 100, 101, 110\}.$ Total: $6$ es decir, $2f_{4} = 2\cdot3$ .

$n = 4$ : $\{0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101\}.$ Total: $10$ es decir, $2f_{5} = 2\cdot5$ .

He escrito una prueba un poco extensa de que el patrón anterior continúa, pero la omito aquí en aras de la brevedad. (Si fuera útil, podría incluirla en el post; pero una respuesta a mi principal pregunta por supuesto, subsumiría este resultado particular).

Answer 1

Para $a=2$ obtienes los números c-bonacci.

De forma más general, basta con establecer la relación de recurrencia y resolverla para $F_b$ .

$$F_n = (a-1)[F_{n-1}+ \ldots +F_{n-c}]$$

Con una condición inicial de $F_1 = a, F_0 = 1, F_{-i} =0$

Por la teoría de las recurrencias lineales, sabemos que $F_n = F_n = \sum A_i \alpha_i^n$ , donde $\alpha_i$ son las raíces de la ecuación característica. Sin embargo, como no tiene raíces inmediatamente evidentes, me sorprendería que hubiera una respuesta general compacta.

Answer 2

En Odlyzko "Enumeración de cadenas" (en "Combinatorial Algorithms on Words", Apostolico y Galil (eds), Springer, 1985) uno de los problemas tratados es una generalización de éste. El resultado es que la función generadora de los números que se buscan es: $$\sum_{b \ge 0} S(a, b, c) z^b = \frac{1 - z^c}{1 - a z + a z^{c + 1}}$$ Lo que se podría hacer a partir de aquí es expandir el denominador como una serie geométrica en $a z - a z^{c + 1}$ pero eso no dará ningún tipo de forma cerrada.

Los números de Fibonacci $F_0 = 0, F_1 = 1, F_{n + 2} = F_{n+1} + F_n$ tienen una función generadora $F(z) = \frac{z}{1 - z - z^2}$ . Así que tienes: $$\sum_{n \ge 0} n F_n z^n = z \frac{\mathrm{d} F}{\mathrm{d} z} = \frac{z (1 + z^2)}{(1 - z - z^2)^2}$$ Sus valores anteriores son sólo una coincidencia.

Añadido más tarde: Los términos de la secuencia se pueden recuperar a partir de la expansión de la fracción parcial de la función generadora, cada uno de cuyos ceros da un término de la forma $a \rho^n$ si $1/\rho$ es un cero del denominador, y los ceros múltiples dan polinomios en $n$ multiplicado por el $\rho^n$ . Algunos términos pueden no estar presentes para determinados valores iniciales (que se codifican en el denominador).

Tenga en cuenta que este es la forma cerrada de la secuencia, no puede haber otra (en esencia, los coeficientes de la serie de Maclaurin son únicos). Para determinados valores de $a$ y $c$ existen expresiones conocidas para los ceros (hasta $c = 3$ a través de la fórmula de la cuartica). Estoy seguro de que el polinomio correspondiente $1 - a z + a z^{c + 1}$ no tiene expresión para los ceros de las raíces (al menos para $c = 4$ el quintento resultante no lo ha hecho). Así que, al menos para ese caso concreto (y muy probablemente para todos los casos superiores $c$ también) hay no "bonita fórmula" (y un monstruo con $c + 1$ términos no es muy "agradable" de todos modos).