Taxi distance count to all lattice points at specified distance from the lattice origin and of a specified dimensionality?

Question

Setup of the problem

Description of the lattice

1. The problem is stated on a non-negative integer ($ℤ_{\ge 0}$) lattice.

2. The specification of distance is also a non-negative integer ($ℤ_{\ge 0}$).

3. The specification of dimensionality is positive integer ($ℤ_{\gt 0}$).

4. Lattice may considered to be labeled by vectors of non-negative integers ($ℤ_{\ge 0}$) of dimensionality length.

Description of paths involved in the question

1. A trips will start from the origin, a constant array of $0$s, which is a lattice point in the lattice.

2. The set of destinations (a set of lattice points) is the set of lattice point whose sum of vector coordinates is distance.

3. The permissible transitions between lattice points are those which add an integer $1$ to exactly one of the vector components of the current lattice point's label vector.

4. A path is an ordered set of legal transitions from one lattice point to another.

---

The problem statement

Starting from the origin and transitioning under the above rules to a destination set, how many distinct paths are there?

The answer should be a formula or method that gives single non-negative integer answer for a given distance and dimensionality.

---

Remark:

Therefore, there are dimensionality legal transitions from a given lattice point. There is not stated upper limit of the magnitude of the vector components; but, effectively, a matrix of size $(\text{distance}+1)^{\text{dimensionality}}$ ought to be a sufficiently large work area for a computer implementation.

Answer 1

1. Using Wolfram Mathematica:

taxi = Function[{distance, dimensionality}, 
    Total[(Multinomial @@ #1 & ) /@ 
      Union[Flatten[(Permutations[#1, 
           {dimensionality}] & ) /@ 
         (PadRight[#1, dimensionality] & ) /@ 
          IntegerPartitions[distance, 
           dimensionality], 1]]]]; 

$$ \left( \begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 9 & 16 & 25 \\ 1 & 8 & 27 & 64 & 125 \\ 1 & 16 & 81 & 256 & 625 \\ 1 & 32 & 243 & 1024 & 3125 \\ \end{array} \right) $$

An English translation of the Wolfram Mathematica code (since this is not mathematica.stackexchange.com.

a) define a function of two arguments distance and dimensionality,

b) compute the total of

c) the set of multinomials (Union removes duplicates and Flatten reduces nesting level) of

d) the lists of right-padded with $0$s to length dimensionality lists of

e) the integer partitions of distance to a maximium length of dimensionality.

2. By inspection of the table above:

$$ \text{dimensionality}^\text{distance} $$

3. By attributes of Binomial and Multinominal:

Resolve[ForAll[{m, n}, Binomial[n, m] == Multinomial[m, n - m]]]

$$ \sum _{m=0}^n \binom{n}{m} = 2^n $$

N.B., this is also the number of binary integers of dimensionality bits, starting from zero.

The multinomial coefficient, $\text{Multinominal}\left[N;n_1,n_2,\ldots \right]$, denoted $\left(N;n_1,n_2,\ldots ,n_m\right)$, gives the number of ways of partitioning $N$ distinct object sets, each of size $n_i$ (with $N=\sum _{i=1}^m n_i$). See Multinomial in Wolfram documentation.

N.B., in general, the sum of the multinomial coefficients over the integer partitions of distance is also the number of base distance integers of dimensionality digits, starting from zero.

And, that leads back to the first answer.