counting the number of paths from point $(0,0)$ to point $(n,m)$ on a recangular grid after N steps Is there anyway to determine the total number of paths which start at the origin $(0,0)$ and finish at a point $(n,m)$ of a 2D rectangular grid after taking a total of N steps. On each step transition to a neighboring lattice point in the positive or negative $x$ or $y$ direction is allowed(N S E W).
 A: There is actually a closed-form formula!  Here is a (kind of neat, in my opinion) way of finding it.
Take the whole grid, rotate it $45^\circ$, and shrink it by a factor of $\sqrt{2}$.
So the vectors we can move along are now pointing NE, SE, SW, NW and have length $\frac{1}{\sqrt{2}}$; that is, they are $(\pm \frac{1}{2}, \pm \frac{1}{2})$.
Now, add a vector pointing $NE$ with length $\frac{1}{\sqrt{2}}$ (that is, $(\frac{1}{2}, \frac{1}{2})$) to each possible move, yielding the four move vectors: $(0, 0)$, $(1, 0)$, $(0, 1)$, $(1,1)$.  That is, in our new movement scheme, we are allowed, at each of $N$ moves, to add $1$ to the $x$-coordinate, the $y$-coordinate, both, or neither.  Hence the number of ways to reach $(m, n)$ is $\displaystyle \binom{N}{m}\binom{N}{n}$.
This is not the final answer, however.  We need to transform back to the original problem.  So we subtract $N(\frac{1}{2}, \frac{1}{2})$ from $(m,n)$ corresponding to the extra move vectors we added at each step, and then scale by $\sqrt{2}$ and rotate by $45^\circ$ again (it doesn't actually matter which direction by symmetry).  So $(m, n)$ becomes $(m-\frac{N}{2}, n-\frac{N}{2})$ and then $(m-n, m+n-N)$.
Okay, so to recap:  the number of paths to $(m-n, m+n-N)$ is $\displaystyle \binom{N}{n}\binom{N}{m}$.  We're not quite done yet, though, because we really want the number of paths to $(a, b)$.   So, set $a = m-n$, $b = m+n-N$ and solve to get $m = \frac{a+b+N}{2}$ and $n = \frac{b-a+N}{2}$.
Thus, the number of paths to $(a, b)$ is $\displaystyle \binom{N}{\frac{a+b+N}{2}} \binom{N}{\frac{b-a+N}{2}}$ (where the binomial coefficient is zero if the bottom number is not an integer between $0$ and $N$ inclusive).
A: It is easy if $|m|+|n| \gt N$  
You have (number of north steps-number of south steps)=n and similar for m.  If there are steps left over from the minimum, you can add a north/south pair or an east/west pair.  For a given combination of N,S,E,W steps, you can put them in any order.  As an example, let $m=3,n=2,N=13$  You have a total of 13 steps, which could be 5N, 2S, 4E, 2W or various other combinations.  How many ways are to put those steps in order?  Now sum over the various legal combinations of steps.
A: First of all for this to be possible we need $N>|n|+|m|$ and we need N to have the same parity as $|n|+|m|$.
Let  $N=|n|+|m|+2k$ for $k$ an integer with $k\geq0$
let x be the number of movements in the x axis and y the number of movements in the y axis. Since $x\geq |n|,y\geq |m| $ and both x and y have same parity as $m,n$ we know that $x=|n|+2u$ and $y=|m|+2w$, but we know $u+w=k$ so $w=k-u$ 
So the number of paths is $\sum_{u=0}^k\binom{|n|+|m|+2k}{|n|+2u}$
