Calculating the number of possible paths from an arbitrary starting point 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?
 A: 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)!}
$$
A: 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.
