## Paths in an n-dimensional grid

There is an $$n$$-dimensional grid in an $$n$$-dimensional Euclidean space made of all points with integer coordinates of the form $$(x_1, x_2, \dots, x_n)$$ that satisfy the inequality $$0 \leq x_i \leq a_i$$ where $$i \in \{1, 2, \dots, n\}$$. Every pair of points in the grid that are a unit distance apart are connected by an edge. Through these edges, how many possible shortest paths are there from the point at $$(0, 0, \dots, 0)$$ to the point at $$(a_1, a_2, \dots, a_n$$)?

[SOLVED]

#### Wonderwice Margera solved this puzzle:

Let $$A = \sum_{i=1}^n a_i$$. Any path can be represented as a sequence of colors $$b_1, b_2, \dots, b_A$$ where the colors are chosen from a set of $$n$$ colors, $$\{c_1, c_2, \dots, c_n\}$$, such that $$b_i = c_j$$ if the $$i$$th step in the path was along the $$j$$th dimension. The correspondence between the set of paths and the set of such sequences is clearly a bijection.

Therefore, the given problem is identical to the problem of finding the number of ways of finding such a sequence, which is well known to be

$\frac{A!}{\prod_{i=1}^n (a_i!)}.$

#### Tim Ophelders solved this puzzle:

Let us call the points in the grid nodes. Let the vector $$\newcommand{\v}{\mathbf{v}}$$ $$\v = (v_0, v_1, \dots, v_n$$) represent a node at coordinates $$(v_0, v_1, \dots, v_n)$$. The shortest distance from the origin to $$\v$$, in terms of edges is $$\newcommand{\x}{\mathbf{x}} \newcommand{\0}{\mathbf{0}}$$

$d(\v) = \sum_{i=1}^n v_i.$

The set of nodes adjacent to the node at $$\v$$ in the shortest paths to $$\v$$ is

$p(\v) = \left\{ \x \mid d(\x) = \bigl(d(\v) - 1\bigr) \land \bigl(d(\v - \x) = 1\bigr) \right\}.$

The component of $$\v$$ that differs from a node $$\x \in p(\v)$$ is

$\Delta(\v, \x) = \v \cdot (\v - \x).$

We prove by structural induction on paths that the number of shortest paths to $$\v$$, is $$f(\v) = \frac{(d(\v))!}{\prod_{i=1}^n (v_i!)}$$.

\begin{array}{cl|r} f(\0) & = \frac{(d(\0))!}{\prod_{i=1}^n (a_i!)} = \frac{0!}{(0!)^n} = 1 & \text{ i.e. only the empty path} \\ f(\v) & = \sum_{\x \in p(\v)} f(\x) & \\ & = \sum_{\x \in p(\v)} \frac{(d(\x))!}{\prod_{i=1}^n (x_i!)} & \\ & = \sum_{\x \in p(\v)} \frac{(d(\v) - 1)!}{\prod_{i=1}^n (x_i!)} & d(x) = d(v) - 1 \\ & = \sum_{\x \in p(\v)} \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \cdot \Delta(\v, \x) & \prod_{i=1}^n (v_i!) = \Delta(\v, \x) \prod_{i=1}^n (x_i!) \\ & = \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \sum_{\x \in p(\v)} \Delta(\v, \x) & \\ & = \frac{(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} \sum_{i=1}^n v_i & \sum_{\x \in p(\v)} \Delta(\v, \x) = \sum_{i=1}^n v_i \\ & = \frac{(d(\v))(d(\v) - 1)!}{\prod_{i=1}^n (v_i!)} & \\ & = \frac{(d(\v))!}{\prod_{i=1}^n (v_i!)} & \\ \end{array}

Therefore, the number of shortest paths from the origin to $$(a_1, a_2, \dots, a_n)$$ is

$\frac{\left(\sum_{i=1}^n a_i\right)!} {\prod_{i=1}^n (a_i!)}.$

#### Rino Raj solved this puzzle:

Let $$m = \sum_{i=1}^n a_i$$. Then all shortest paths have length $$m$$, and each step can be denoted by just $$i$$, the direction or dimension in which the step is taken. Thus each shortest path can be encoded by a string of $$m$$ digits, where each digit $$i \in \{1, 2, \dots, n\}$$ occurs exactly $$a_i$$ times. Every such string represents a valid shortest path, so the number of such strings is the same as the number of shortest paths.

The number of such strings is counted by the multinomial coefficient

$\frac{m!}{\prod_{i=1}^n (a_i!)}.$

#### Eric Sosman solved this puzzle:

Assuming there are no bridges other than the unit steps mentioned in the puzzle, each step in any path changes one coordinate by one unit. A shortest path thus needs $$\sum_{i=1}^n a_i$$ steps in all, $$a_k$$ along the $$k$$th axis. Therefore, the number of shortest paths is the number of permutations of $$a_1$$ steps along the first axis, $$a_2$$ steps along the second axis, and so on, which is given by the expression

$\frac{\left(\sum_{i=1}^n a_i\right)!}{\prod_{i=1}^n (a_i!)}.$

### Credit

This is an original cotpi puzzle inspired by: