Number of possible paths On a $xy$ plane how many $2n$-move paths can be made that begin and end on $(0,0)$ but pass from $(k,n-k)$ with $0\leq k\leq n$?
I can't think of a way to solve it, because every move is allowed and the number of moves is specific.
 A: Notice that the shortest way to get to $(k, n-k)$ takes $n$ steps and the same is true of the return journey. Since we are allowed only $2n$, we must take a shortest path to $(k,n-k)$ and a shortest path on the way back.
The shortest path from $(0,0)$ to $(k,n-k)$ is a permutation of $k$ east moves and $n-k$ north moves. There are $\binom{n}{k}$ such paths. There are many ways to see this (edit: see @vonbrand's comment below for an alternative proof). There are $n!$ ways to order $n$ items, but since we don't care about how the north moves are ordered among themselves, we divide by $(n-k)!$ and since we don't care about how the east moves are order among themselves, we divide by $k!$. The total number of paths from $(0,0)$ to $(k,n-k)$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$.
The number of paths coming back can be computed to be the same quantity. Hence the total number of paths is $\binom nk ^2$.
A: We assume that a move is $1$ unit in any of the directions North, South, East, West.
If we return to $(0,0)$ in $2n$ moves but pass through the specific point $(k,n-k)$ we must in our first $n$ moves go $k$ moves East and $n-k$ moves North. There are $\binom{n}{k}$ ways to choose when among the first $n$ steps we take our $k$ steps North. 
For every trip to $(k,n-k)$ there are $\binom{n}{k}$ return trips, for a total of $\binom{n}{k}^2$.
Remark: Suppose now that $k$ is unspecified. Then the number of paths is $\sum_{k=0}^n \binom{n}{k}^2$. 
Call a move good if it is East on the outward trip or South in the inward trip. Then there are $n$ good moves, and the trip is completely determined by when a good move occurs. So the number of possible trips is $\binom{2n}{n}$.  This gives  another proof of the well-known combinatorial identity  $\sum_{k=0}^n \binom{n}{k}^2=\binom{2n}{n}$. 
