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.

$\endgroup$
4
  • $\begingroup$ This approach will lead to $k$ terms. Are we allowed to use sums? This will reduce it to one term. $\endgroup$ Mar 11, 2011 at 6:28
  • $\begingroup$ @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. $\endgroup$ Mar 11, 2011 at 6:31
  • $\begingroup$ Did you get something out of the answer below? $\endgroup$
    – Did
    Apr 7, 2011 at 8:04
  • $\begingroup$ @Didier, Yes, thank you Didier. I hadn't logged in recently, I will accept now. $\endgroup$ Apr 11, 2011 at 20:15

1 Answer 1

8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Mar 13, 2011 at 1:26
  • $\begingroup$ @Hobbie I fail to see why you think this is not the way the book suggests, especially in view of (b) and (c). $\endgroup$
    – Did
    Mar 13, 2011 at 8:25
  • $\begingroup$ 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). $\endgroup$ Mar 13, 2011 at 22:17
  • $\begingroup$ @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. $\endgroup$
    – Did
    Mar 14, 2011 at 6:23

Not the answer you're looking for? Browse other questions tagged .