# How many strings of length $n$ with $m$ $1$s have no more than $k$ consecutive $1$s? - from generatingfunctionology

Here is a problem from generatingfunctionology that I'm stuck on:

I'm trying to get started on part (a). I broke the string up like this. If the last digit is $0$, the number of possible strings is then $f(n-1,m,k)$. If the last digit is $1$, there are two subcases. If the $n-1^{th}$ digit is $0$, then we can cut them both off and the number of strings is $f(n-2,m-1,k)$. However, if the $n-1^{th}$ digit is $1$, then I don't know what to say, since even if I cut both last $1$s off, I can't have the last $k-2$ numbers of my $n-2$ long string be $1$s, but it's entirely possible that I could have $k-2$ $1$s earlier in the string. So I have something like: $$f(n,m,k)=f(n-1,m,k)+f(n-2,m-1,k)+???$$ and I don't know what third term to put there. What is the third term? Thanks.

If it's not trouble, I may ask questions on parts (b) and (c) when I get there.

-
This approach will lead to $k$ terms. Are we allowed to use sums? This will reduce it to one term. – Yuval Filmus Mar 11 '11 at 6:28
@Yuval, I'm not sure, this is a screenshot taken directly from the book, but it seems like Wilf (the author) wants to put it in three terms. Any insight is appreciated though. – Dani Hobbes Mar 11 '11 at 6:31
Did you get something out of the answer below? – Did Apr 7 '11 at 8:04
@Didier, Yes, thank you Didier. I hadn't logged in recently, I will accept now. – Dani Hobbes Apr 11 '11 at 20:15

## 1 Answer

Assume $m$ and $n$ are large, say larger than $k$. If you continue your what-is-the-end-of-the-string argument, you will get $f(n,m,k)$ as the sum of $f(n-i,m-i+1,k)$ from $i=1$ to $i=k$, each of these terms counting the strings ending by $01^{i-1}$. Now, this sum has $k$ terms and you want only three.

Compare the $k$ terms sums for $f(n,m,k)$ and for $f(n-1,m-1,k)$.

The same terms appear in both sums with two exceptions: the first term of $f(n,m,k)$ is $f(n-1,m,k)$, which is not in $f(n-1,m-1,k)$, and the last term of $f(n-1,m-1,k)$ is $f(n-1-k,m-k,k)$, which is not in $f(n,m,k)$. Of course this reflects a combinatorial fact, which I let you explicit.

Hence, at least for large enough $n$ and $m$, $$f(n,m,k)=f(n-1,m-1,k)+f(n-1,m,k)-f(n-1-k,m-k,k).$$

-
Thank you Didier. However, I'm still hoping to solve it the way the book presents it, in order to address parts (b) and (c) later. – Dani Hobbes Mar 13 '11 at 1:26
@Hobbie I fail to see why you think this is not the way the book suggests, especially in view of (b) and (c). – Did Mar 13 '11 at 8:25
I suppose I think it's not the way the book suggests, since part (a) says the recurrence should have $f(n,m,k)$ on the left, not $f(n,m)$, and then uses $f(n,m,k)$ in the summation of part (b), and then asks for an explicit formula for $f(n,m,k)$ in part (c). – Dani Hobbes Mar 13 '11 at 22:17
@Hobbit Your answer makes no sense. Did you notice that $k$ is fixed once and for all in all the exercise (which is why I said in the first sentence of my post that I will omit it)? I put $k$ back in my post. – Did Mar 14 '11 at 6:23