2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.