I want to count the number of shortest paths from one corner of a multidimensional lattice, to the opposite corner. Hence in the 2-dimensional case, given a lattice (or grid graph) of $n_1 \times n_2$ vertices, I want to count the number of shortest paths from the top left vertex to the bottom right vertex (which must only move right and down). In this case, the number of such paths is given by $$\binom{(n_1-1)+(n_2-1)}{n_1-1}$$

which for $n_1=3$ and $n_2=2$ equals 3 (see Staircase Walks). Now I want to find the following: Given integers $(n_1,n_2,\ldots,n_k)$, what is the number of shortest paths from one corner of the $(n_1 \times n_2 \times \cdots \times n_k)$-dimensional lattice to the opposite?


Look at the $2$d case. If you have a $n_1 \times n_2$ grid and without loss of generality you want to traverse from the top-left corner to the bottom-right, then you must take a total of $n_1 - 1$ steps down and $n_2 - 1$ steps right. The number of sequences of downs and rights is the number of paths and that is where $$\binom{n_1 - 1 + n_2 - 1}{n_1 - 1}$$ comes from. To generalize this, if you have a $k$-dimensional hypercube with dimensions $(n_1,\ n_2,\ \cdots,\ n_k)$ then you must take $n_i - 1$ steps in each respective dimension, and the number of these sequences of these steps will give you the total paths. The total number is then given by $$\binom{[n_1 - 1] + \cdots + [n_k - 1]}{n_1 - 1,\ n_2 - 1, \cdots, n_k - 1}$$ which is a multinomial coefficient.

  • $\begingroup$ Look at the case of a 3-dimensional cube of dimensions $2 \times 2 \times 2$. In this case, the number of paths is 6 as far as I can see, which is not given by your formula. $\endgroup$ – utdiscant Sep 28 '12 at 2:22
  • 2
    $\begingroup$ $$\binom{1+1+1}{1,1,1} = \binom{3}{1,1,1} = \frac{3!}{1!1!1!}=6$$ That's precisely what I get. $\endgroup$ – EuYu Sep 28 '12 at 2:24
  • $\begingroup$ You are of course correct, I added $1!+1!+1!$ instead of multiplying. $\endgroup$ – utdiscant Sep 28 '12 at 2:26

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.