Find the formula of this binary recurrence equation? f(m,n) = f(m-1,n) + f(m,n-1)

Question

SORRY GUYS! MY MISTAKE! Thanks for your reminder, I found out f(0,k) == f(k,0) == 1. This question is about how to count the number of shortest paths from grid (0,0) to (m,n).

I have to solve the following equation now, find out exactly what f(m,n) equal to.

1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

for example:

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3  

I remember there is a standard way to solve such kinds of binary recurrence equation as I learned in my algorithm class several years ago, but I just cannot remember for now.

Could anyone give any hint? Or a keyword how to find the answer?

Answer 1

Ugh, I was just having fun going through my old textbooks on generating functions, and you went and changed the question again!

This question is about how to count the number of shortest path from grid (0,0) to (m,n).

This is a basic combinatorics question - it doesn't require knowing anything about generating functions, or even recurrence relations.

To solve, imagine the paths being written out as a sequence of U's (for "up") and R's (for "right"). If we are moving from (0,0) to, say, (5, 8), there must be 5 R's and 8 U's. Just one example:

RRUURURUUURUU

There will always be, in this example, 8 U's and 5 R's; different paths will just have them in different orders. So we can just choose 8 positions for our U's, and the rest must be R's. Thus, the answer is

(8+5) choose (8)

Or, in general,

(m+n) choose (m)

Answer 2

This is simply the binomial coefficient

f(m,n) = (m+n choose m) = (m+n choose n)

You can prove this by noting that they satisfy the same recurrence relation.

To derive the formula (if you couldn't just guess and then check), use generating functions as Chris Nash correctly suggests.

Answer 3

Try looking up "generating functions" in the literature. One approach would be to imagine a function P(x,y) where the coefficient of x^m y^n is f(m,n). The recurrence line (line 3) tells you that P(x,y) - x.P(x,y) - y.P(x,y) = (1-x-y) P(x,y) should be pretty simple except for those pesky edge values. Then solve for P(x,y).

Are you sure f(k,0) = f(0,k) = k, and not 1, maybe? If it were, I'd say the best bet would be to write some values out, guess what they are, then prove it.