Finding a combinatorial recurrence relation with three variables

Question

This question is from the generating functionology textbook,

Let $f(n, m,k)$ be the number of strings of n $0$’s and $1$’s that contain exactly $m$ $1$’s, no $k$ of which are consecutive.

Find a recurrence formula for $f$. It should have $f(n, m,k)$ on the left side, and exactly three terms on the right.

There were previous examples involving binomial coefficients and partitions, so I am sure the method of finding the recurrence is similar (splitting the total into piles with n and without n etc)

This just seems on another level of complexity, any help would be much appreciated.

Answer 1

Imagine that you build such a binary string by appending $0$ or $1$ to a string one shorter. The difficulty, of course, is that you can't be sure you can safely add another $1$ as you might violate the "consecutive condition". Thus, you need to keep track of the possible endings. Accordingly, define $f(n,m,k,i)$ to be the number of "good" strings that end in exactly $i$ $1's$. Of course we can rewrite this function in terms of the original one...we know that the strings it counts end in $01^{i}$ but what comes before can end in either digit, has exactly $m-i$ $1's$ and still satisfies the consecutive condition. Hence $$f(n,m,k,i)=f(n-i-1,m-i,k)$$ Returning to the problem, we immediately get the recursion: $$f(n,m,k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-1,m-1,k,k-1)$$ Where the first term comes by appending a $0$, the second by appending a $1$ and the third by removing those strings which would violate the consecutive condition. Finally, then, we get,

$$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)$$

Note: this seems like a good candidate for a "fencepost" type error. That is, I would not be surprised if some indices were off by $1$. I'd check it carefully for reasonably small figures.

Answer 2

We can break down $f(n,m,k)$ into how many consecutive ones it ends with $$ f(n,m,k)=\left\{\begin{array}{} 0&\text{if }m<0\text{ or }n<m&\text{impossible}\\[9pt] [n<k]&\text{if }n=m&\text{only ones}\\ \displaystyle\sum_{j=0}^{k-1}f(n-j-1,m-j,k)&\text{if }n\gt m&\begin{array}{l}\text{ends with a zero}\\[-4pt]\text{and $j$ ones}\end{array} \end{array}\right. $$ where $[\cdots]$ are Iverson Brackets.

Here is a table for $k=3$: $$ \begin{array}{r|rr} &0&1&2&3&4&5&6&7&8&9&n\\\hline 0&1&1&1&1&1&1&1&1&1&1\\ 1&0&1&2&3&4&5&6&7&8&9\\ 2&0&0&1&3&6&10&15&21&28&36\\ 3&0&0&0&0&2&7&16&30&50&77\\ 4&0&0&0&0&0&1&6&19&45&90\\ 5&0&0&0&0&0&0&0&3&16&51\\ 6&0&0&0&0&0&0&0&0&1&10\\ 7&0&0&0&0&0&0&0&0&0&0\\ m \end{array} $$