2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ can you explain what you consider to be a path? $\endgroup$ – Forever Mozart Dec 31 '15 at 19:28
  • $\begingroup$ @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) $\endgroup$ – Mitsos Dec 31 '15 at 19:31
  • $\begingroup$ 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? $\endgroup$ – Forever Mozart Dec 31 '15 at 19:33
6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – vonbrand Dec 31 '15 at 20:52
  • 1
    $\begingroup$ @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. $\endgroup$ – Snow Dec 31 '15 at 20:58
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does this mean we are going to cross the point $(n,n)$ on the xy plane once...to satisfy the conditions given? $\endgroup$ – Freelancer Jan 2 '16 at 12:37
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Jan 2 '16 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.