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