5
$\begingroup$

How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this?

Eg. The shortest path between $(0,0)$ and $(1,1)$ can be $(0,0)\to (0,1)\to (1,1)$ or $(0,0)\to(1,0)\to(1,1)$, so there are two shortest paths.

  • 1
    This question has been previously asked and resolved here http://math.stackexchange.com/questions/103480/number-of-ways-of-reaching-a-point-from-origin/103485#1034852012-01-29

1 Answers 1

15

Any shortest path from $(0,0)$ to $(m,n)$ includes $m$ steps in the x axis and $n$ steps in the y axis; what governs the shape of such a path is the order in which we choose to go to the right and up. Since we have $m+n$ total steps to take, we just need to choose which $m$ will be to the right. This is counted by the binomial coefficient $\binom{m+n}{m} = \binom{m+n}{n}$.

  • 0
    You need to assume that $m, n$ are non-negative here, but up to reflection this loses no generality.2012-01-29