Calculating the number of possible paths from an arbitrary starting point

Question

I have a grid of size $n\times n$, where the origin is set at $(0,0)$ and the coordinates of the points on this grid, can only be positive.

Let's say that we start at the point $(i,j)$. We can only go 1 step up or 1 step to the right and we want to reach the corner $(n,n)$. What is the total number of paths?

I want to solve this problem recursively (no other solutions allowed).

Let me define $N(i,j)$ the total number of paths to go from $(i,j)$ to $(n,n)$. Then, we need to solve this recursive equation

$$ N(i,j) = N(i+1,j) + N(i,j+1) $$

with boundary conditions

$$ N(n,j) = N(i,n)=1\,,\forall i\neq n, j\neq n\\ N(n,n)=0 $$

How can I solve this equation?

What I have done is to write down the generetical function

$$ f(x,y) = \sum_{i=0}^\infty\sum_{j=0}^\infty N(i,j)x^i y^j = \frac{y f(0,y)+x f(x,0)}{x+y-x y} $$

Is it useful somehow?

Answer 1

Guess a solution, then prove it by induction. By generalizing from small examples, you should be able to guess that: $$ N(i, j) = \frac{(2n - i - j)!}{(n - i)!(n - j)!} $$

It would probably have been easier if you had redefined the function to count paths from $(0, 0)$ to $(i, j)$.

For the inductive step, it would be helpful to recall Pascal's Identity: $$ \frac{p!}{q!(p - q)!} = \frac{(p - 1)!}{(q - 1)!(p - q)!} + \frac{(p - 1)!}{q!(p - q - 1)!} $$

Answer 2

For a non-inductive method, you can look at it as a combinatorial exercise. Also, to make things a little neater I'm going to look at the number of paths from $(0, 0)$ to $(i, j)$, but you can transform this to your problem quite easily.

Notice that every path from $(0, 0)$ to $(i, j)$ will consist of exactly $i$ steps to the right, and $j$ steps up, and the only difference is their order. So if we write a step right as $r$ and a step up as $u$, then we are looking for the number of ways we can arrange the letters

$$\underbrace{u u \ldots u}_{i \text{ times}}\underbrace{r r \ldots r}_{j \text{ times}}$$

There are a couple of ways to approach this, but one way is to just note that out of $(i + j)$ possible positions to put the letters into, you have ${ {i + j} \choose i } = \frac{(i + j)!}{i! (i + j - i)!} = \frac{(i + j)!}{i! j!}$ ways to choose where to put the $u$s, and once you've done that the positions of the $r$s are fixed, so this is the total number of arrangements.