Paths in a graph in 3 dimensions

Question

Consider paths in $\mathbb{Z}^3$ between two points, where the steps avaible are in the form of $(\pm 1, 0, 0)$,$(0,\pm 1,0)$,$(0,0, \pm 1)$. How many paths of $10$ steps there is between the points $(2,1,-1)$ and $(6,4,2)$ that don't pass through the point $(5,2,1)$?

Working with paths in $\mathbb{Z}^2$ there is a general formula where the solution is: $ \binom n {a_1,...,a_k} $, where $n=a_1+...+a_k.$

Is there any formula or simple way of calculating steps in $\mathbb{Z}^3$?

Answer 1

The general solution for the number of paths in $\mathbb Z^m$ is given by the multinomial coefficient

$$\binom {n}{a_1+a_2+a_3+\cdots+a_m}$$ where $n=a_1+a_2+a_3+\cdots+a_m$, and $a_i$ is the number of steps in the $i^{\text{th}}$ direction. This assumes no backtracking allowed. See additional notes below.

Let $A=(2,1,-1), B=(6,4,2), C=(5,2,1)$.

This gives $AB=(4,3,3) \; (10\text{ steps}),\; AC=(3,1,2) \;(6\text{ steps}),\; CB=(1,2,1)\; (4\text{ steps})$.

Number of ways to get from $A$ to $B$:

$$\binom {10}{4,3,3}=\frac{(10)!}{4!3!3!}=4200$$

Number of ways to get from $A$ to $B$ passing through $C$:

$$\binom 6{3,1,2}\cdot \binom 4{1,2,1}=\frac {6!}{3!1!2!}\cdot \frac {4!}{1!2!1!}=6!=720$$ Therefore, number of ways to get from $A$ to $B$ without passing through $C$ is $$4200-720=\color{red}{3480}$$

---

Additional Notes

When $m=2$ this reduces to a $2$D grid walk, and in particular if $a_1=a_2=N$, i.e. $n=2N$, then the number of paths reduces to the central binomial coefficient $$\frac {(2N)!}{N!N!}=\binom {2N}N$$

Similarly, for $m=2$, and $a_1=a_2=a_3=N$, this reduces to a walk on a cubic grid, and total number of paths given by $$\frac {(3N)!}{N!N!N!}=\binom {3N}{N,N,N}$$

Answer 2

Since you are looking for paths of 10 steps you will have to do 4 moves up in the first dimension, 3 up in the second dimension and 3 up in the third dimension. You can only change the order. This gives you ${10 \choose 4}{6 \choose 3}=4200$ choices.

Now you have to remove the paths that go to the point $(5, 2, 1)$. Let us count the paths of length 6 from $(2,1,−1)$ to $ (5,2,1)$: ${6 \choose 3}{3 \choose 1}=60$ and the paths of length 4 from $ (5,2,1)$ to $(6,4,2)$: ${4 \choose 1}{3 \choose 2}=12$. This gives 720 paths that are forbidden.

Finally you obtain 3480 paths.

A general formula for the number of paths in $\mathbb Z^n$ involving $a_k$ moves in the $k$th direction is indeed $${a_1 + \cdots + a_n \choose a_1, \cdots, a_n}$$