1
$\begingroup$

I'm looking to find the number of paths through the 3-D lattice from the origin $(0,0,0)$ to the point $(7,3,5)$. Each step made can only move forwards 1 unit in the x,y or z direction.

I think the answer is (number of paths from $(0,0,0)$ to $(7,3,4)$) + (number of paths from $(0,0,0)$ to $(7,2,5)$) + (number of paths from $(0,0,0)$ to $(6,3,5)$) but I don't know how to calculate the three individual components of the sum. Am I supposed to use the multinomial formula $\binom{k+m+n}{k,m,n}=\frac{(k+m+n)!}{k!m!n!}\;$ for each one?

$\endgroup$
3
$\begingroup$

The paths are in bijection with words of length $15$ over the alphabet $\{x, y ,z\}$ with exactly $7$ letters as $x$, $3$ letters as $y$ and $5$ letters as $z$. Here $x$ represents a $(1,0,0)$ step, $y$ represents a $(0,1,0)$ step and $z$ represents a $(0,0,1)$ step. Hence the number of ways is $$ \binom{15}{7, 3, 5} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the help! I got the same answer with your method and my longer one. $\endgroup$ – Sonjov Oct 13 '17 at 0:32
1
$\begingroup$

Your answer should be correct: This follows from the logic of counting paths in $2$ dimensions:

There is $1$ to get to $(0, 0)$. There are therefore $n$ ways to get to $(0, n)$ or $(n, 0)$. Any place with positive coordinates $(a, b)$ has the sum of the ways to get to $(a-1, b)$ and $(a, b-1)$.

You may recognize this pattern of construction as the same as Pascal's triangle. Thus, the number of ways to $(a, b)$ is ${a+b}\choose a$.

Thus, a similar construction method in $3$ dimensions will yield Pascal's Pyramid. Hence, your calculation is correct as any point in Pascal's pyramid is $\frac{(a+b+c)!}{a!\cdot b!\cdot c!}.$

| cite | improve this answer | |
$\endgroup$

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.