Imagina que construyes una cadena binaria de este tipo añadiendo $0$ o $1$ a una cadena más corta. La dificultad, por supuesto, es que no se puede estar seguro de poder añadir otra $1$ ya que podría violar la "condición consecutiva". Por lo tanto, hay que tener en cuenta los posibles finales. En consecuencia, defina $f(n,m,k,i)$ para ser el número de cadenas "buenas" que terminan exactamente en $i$ $1's$ . Por supuesto, podemos reescribir esta función en términos de la original... sabemos que las cadenas que cuenta terminan en $01^{i}$ pero lo que viene antes puede terminar en cualquier dígito, tiene exactamente $m-i$ $1's$ y sigue satisfaciendo la condición consecutiva. Por lo tanto, $$f(n,m,k,i)=f(n-i-1,m-i,k)$$ Volviendo al problema, obtenemos inmediatamente la recursión: $$f(n,m,k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-1,m-1,k,k-1)$$ Donde el primer término viene por la adición de un $0$ el segundo añadiendo un $1$ y la tercera eliminando aquellas cadenas que violarían la condición de consecutividad. Finalmente, entonces, obtenemos,
$$f(n,m,k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-1 -(k-1)- 1,m-1-(k-1),k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-k-1,m-k,k)$$
Nota: esto parece un buen candidato para un error del tipo "poste de la cerca". Es decir, no me sorprendería que algunos índices estuvieran desviados por $1$ . Yo lo revisaría cuidadosamente para ver si las cifras son razonablemente pequeñas.
