# How can I find the number of the shortest paths between two points on a 3D lattice grid?

A similar question has been asked here , but what if we want to find the shortest path between two points in a 3d-space?

Of course we are jut allowed to move along the lattice.

-
You should make it explicit that you want steps along the lattice. Otherwise, there is one shortest path, the straight segment. –  Ross Millikan Feb 9 '13 at 22:19
of course... thank you. –  powermetal114 Feb 9 '13 at 22:21
I am not sure, but I think multinomials solve your question. –  CBenni Feb 9 '13 at 22:25

Assuming that you’re talking about lattice paths, say from $\langle 0,0,0\rangle$ to $\langle k,m,n\rangle$ for some non-negative integers $k,m,n$, you want the multinomial coefficient

$$\binom{k+m+n}{k,m,n}=\frac{(k+m+n)!}{k!m!n!}\;.$$

You must take a total of $k+m+n$ steps, $k$ of them in the positive $x$-direction, $m$ of them in the positive $y$-direction, and $n$ of them in the positive $z$-direction. There are $\binom{k+m+n}k$ ways to choose when to take the steps in the $x$-direction, and there are then $\binom{m+n}m$ ways to choose which of the remaining $m+n$ steps are to be in the $y$-direction. Finally,

$$\binom{k+m+n}k\binom{m+n}m=\frac{(k+m+n)!}{k!m!n!}\;.$$

-
Generally, the answer in n dimension is $$\sum_{i=1}^nk_i\choose k_1,...,k_n$$ then? –  CBenni Feb 9 '13 at 22:28
Perfect answer. Thank you! –  powermetal114 Feb 9 '13 at 22:29
@powermetal114: You’re welcome! –  Brian M. Scott Feb 9 '13 at 22:34
@CBenni: Yes, that’s right. –  Brian M. Scott Feb 9 '13 at 22:35
@powermetal114, accept the answer then. –  vonbrand Jan 25 '14 at 15:27