Cuántas cadenas de longitud $n$ con $m$ $1$s no tienen más de $k$ consecutivo $1$s? - de generatingfunctionology

Question

Aquí es un problema de generatingfunctionology que estoy atascado en:

Estoy tratando de empezar en la parte (a). Se me rompió la cadena como esta. Si el último dígito es $0$, el número de cadenas posibles es, a continuación,$f(n-1,m,k)$. Si el último dígito es $1$, hay dos subcases. Si el $n-1^{th}$ dígito es $0$, entonces podemos cortarlas en off y el número de cuerdas es $f(n-2,m-1,k)$. Sin embargo, si el $n-1^{th}$ dígito es $1$, entonces no sé qué decir, ya que incluso si me corte los dos últimos $1$s off, que no puede tener la última $k-2$ números de mi $n-2$ largo de la cadena ser $1$s, pero es muy posible que yo pudiera tener $k-2$ $1$s anterior en la cadena. Así que tengo algo así como: $$ f(n,m,k)=f(n-1,m,k)+f(n-2,m-1,k)+??? $$ y no sé qué tercer término, para poner allí. ¿Cuál es el tercer término? Gracias.

Si no es molestia, me pueden hacer preguntas en las partes (b) y (c) cuando yo llegue.

Answer 1

Suponga $m$ $n$ son grandes, digamos de más de $k$. Si usted continúa su lo-que-es-el-final-de-la-cadena del argumento, usted conseguirá $f(n,m,k)$ como la suma de $f(n-i,m-i+1,k)$$i=1$$i=k$, cada uno de estos términos contar las cadenas que terminan por $01^{i-1}$. Ahora, esta suma ha $k$ términos y desea sólo tres.

Comparar el $k$ términos de sumas de dinero para $f(n,m,k)$$f(n-1,m-1,k)$.

Los mismos términos que aparecen en ambas sumas con dos excepciones: el primer término de $f(n,m,k)$$f(n-1,m,k)$, que no es en $f(n-1,m-1,k)$, y el último término de la $f(n-1,m-1,k)$$f(n-1-k,m-k,k)$, que no es en $f(n,m,k)$. Por supuesto, esto refleja una combinatoria hecho, que te deje explícito.

Por lo tanto, al menos lo suficientemente grande como $n$$m$, $$ f(n,m,k)=f(n-1,m-1,k)+f(n-1,m,k)-f(n-1-k m-k,k). $$