Encontrar una fórmula para el número de $0$-$1$ secuencias de longitud $n$ con $0$ en cualquier consecutivas $m$ dígitos

Question

Deje $m, n$ ser enteros positivos. Deje $S(n,m)$ el número de secuencias de longitud $n$ y que consta de $0$ e $1$ en los que existe una $0$ en cualquier consecutivas $m$ dígitos. Encontrar una fórmula para $S(n,m)$.

Deje $P(n,m)$ denotar el número de cadenas en las que existe al menos un bloque de $m$ consecutivo $1$'s. Tenemos $S(n,m)=2^{n}-P(n,m)$.

Deje $P_i(n,m)$ denotar el número de cadenas en las que existe al menos un bloque de $m$ consecutivo $1$'s de izquierda a partir de la $(i+1)$'th posición y terminando en el $(i+m)$'th posición, sin bloques de $m$ $1$'s de partida antes de la $i+1$'th posición. Tendremos: $$P(n,m)=\sum_{i=0}^{n-m-1}{P_i(n,m)}$$

Tendremos el primer recuento $P_i(n,m)$. De la $1$'st posición a la $i-1$'th posición hay $S(i-1,m)$ formas de elegir los $1$'s y $0$'s. El $i$'th posición debe ser $0$, y a partir de la $i+1$'th a la $i+m$'th posición, no debe ser $m$ número $1$'s. De la $i+m+1$'th posición a la $n$'th posición, podemos elegir cualquiera de las $1$ o $0$hay $2^{n-m-i}$ formas para elegir. Por lo tanto: $$P_i(n,m)=2^{n-m-i}S(i-1,m)=2^{n-m-1}-2^{n-i-m}P(i-1,m)$$

Así $$P(n,m)=(n-m+1)2^{n-m-1}-\sum_{i=0}^{n-m}{2^{n-m-i}P(i-1,m)}$$ with $P(-1,m)=1$.

Aquí estoy atascado. ¿Cómo puedo progresar ? O hay una mejor manera de encontrar una fórmula general para $S(n,m)$ ? Qué tal fórmula existe?

(Por favor, hágamelo saber si esta pregunta debería ser cerrado. Lo siento por mi inglés gramática)

Answer 1

No creo que hay un fácil ormula cerrada para $S(n,m)$, pero debe cumplir con los siguientes lineal de recurrencia para $n>m>0$ $$S(n,m)=\sum_{k=1}^m S(n-k,m).$$ porque en la última parte de la secuencia que puede tener $0$, $01$, $011$, $\dots$, $0\underbrace{1\dots 1}_{m-1}$.

Por otra parte $S(n,1)=1$, $S(n,2)=F_{n+2}$ donde $F_k$ es el $k$-ésimo número de Fibonacci, $S(n,3)=F^{(3)}_{n+3}$ donde $F^{(3)}_{k}$ es el $k$-th Tribonacci número, $S(n,4)=F^{(4)}_{n+4}$ donde $F^{(4)}_{k}$ es el $k$-th Tetranacci número,

Answer 2

Deje $S(n,m)$ el número de secuencias de longitud $n$ y que consta de $0$ e $1$ en los que existe una $0$ en cualquier consecutivas $m$ dígitos.

Cactual proceso de pensamiento, las necesidades de mejora:

Tenga en cuenta que, $\#$ maneras de elegir un bloque continuo de tamaño $m$ a partir de una cadena binaria de longitud $n$ es $${n-m+1 \choose {1}} =\ (n-m+1)$$ Assume that you have chosen a random $m$-sized continuous block in a binary string of length $n$. Number of ways that this $m$-sized block will have $\color{red}{\text{al menos}}$ one zero is $\ (2^m-1)$, since we are only excluding the case where all entries are $1$s.

Anterior, aunque el proceso, las necesidades de mejora:

Deje $P(n,m)$ denotar el número de cadenas en las que existe al menos un bloque de $m$ consecutivo $1$'s. Entonces podemos escribir, $$S(n,m)=2^{n}-P(n,m)$$ We start computing $P(n,m)$. Let, $P(n,m)$ counts the sequences which comprise a set $A$. Then any element in $Un$ will be of the form $$a_n = \underbrace{\color{blue}{*\dots*} \underbrace{\color{red}{11\dots 1}}_{m} \color{blue}{*\dots*}}_{n}$$ If we take that consecutive sequence of $1$s as a single block, then $P(n,m)$ becomes ${n-m+1 \elegir \color{red}{1}}\ \color{blue}{2^{n-m}}$ , since the rest of the terms in the binary sequence can be anything. $$\therefore S(n,m) = 2^n - P(n,m) = 2^n - {n-m+1 \choose 1}\ 2^{n-m} \\ = 2^n - (n-m+1)\ 2^{n-m} \\ = \fbox{$2^{n-m}\ (2^m -n +m -1)$}$$