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.

• can you explain what you consider to be a path? – Forever Mozart Dec 31 '15 at 19:28
• @ForeverMozart For example two paths from (0,0) to (1,1) are i)one that passes from (0,1) ii)one that passes from (1,0) – Mitsos Dec 31 '15 at 19:31
• so you have to go along the rectangular grid? Does the path have to pass through every $(k,n-k)$? And what is a move? – Forever Mozart Dec 31 '15 at 19:33

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$.

• Simpler: On each trip there are $n$ moves in total, $k$ of which are east (west) moves, there are $\binom{n}{k}$ ways to select the positions of the east (respectively west) moves; in all $\binom{n}{k}^2$. – vonbrand Dec 31 '15 at 20:52
• @vonbrand: Thank you. Yours is definitely easier to state and it's how I would prove it to someone in a hurry. Even after many years, I still think of the argument I wrote above as the "real reason", even though that is a matter of opinion. For completeness, I have referred to your comment in my answer. – Snow Dec 31 '15 at 20:58

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}$.

• Does this mean we are going to cross the point $(n,n)$ on the xy plane once...to satisfy the conditions given? – Freelancer Jan 2 '16 at 12:37
• @Freelancer: We are supposed to leave the origin, make a total of $2n$ moves, and be back at the origin, while having reached a point $(k,n-k)$. We certainly do not reach the point $(n,n)$ in our travels, for that would all by itself take $2n$ moves. – André Nicolas Jan 2 '16 at 14:22