cotpi 58 - Paths in an n-dimensional grid

[cotpi]

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, ..., x_n) that satisfy the inequality 0 <= x_i <= a_i
where i belongs to {1, 2, ..., 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, ..., 0) to the point at (a_1, a_2, ..., a_n)?

--
Originally posted at: http://cotpi.com/p/58/
Correct solutions will be archived at the URL mentioned above.

Solutions to 'Divisibility of largest n-bit integer':
http://cotpi.com/p/57/#solutions

Follow these puzzles on Twitter: http://twitter.com/cotpi

[Butch Malahide]

On Jul 18, 2:24 pm, cotpi <puzz...@cotpi.com> wrote:
> 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, ..., x_n) that satisfy the inequality 0 <= x_i <= a_i
> where i belongs to {1, 2, ..., 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, ..., 0) to the point at (a_1, a_2, ..., a_n)?

Multinomial coefficient (a_1 +...+ a_n)!/a_1!...a_n!