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.
On
I know I’m very late, but this is more for others than the original asker.
The number of shortest paths between (X1,Y1) and (X2,Y2) can is:
$\frac{(|X1-X2|+|Y1-Y2|)!}{(|X1-X2|!)(|Y1-Y2|!)}$
Probably.
It works for every scenario that I’ve tested so far, but it might be wrong because I haven’t put in the effort to check every single potential path of farther separated points.
Really sorry if this doesn’t work, I’m kind of an amateur mathematician.
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}$.