Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  utdiscant Sep 28 '12 at 2:22
1  
$$\binom{1+1+1}{1,1,1} = \binom{3}{1,1,1} = \frac{3!}{1!1!1!}=6$$ That's precisely what I get. –  EuYu Sep 28 '12 at 2:24
    
You are of course correct, I added $1!+1!+1!$ instead of multiplying. –  utdiscant Sep 28 '12 at 2:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.