8
$\begingroup$

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

enter image description here

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.

  • 0
    @Didier, Yes, thank you Didier. I hadn't logged in recently, I will accept now.2011-04-11

1 Answers 1

7

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

  • 0
    @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.2011-03-14