Counting paths in multidimensional grids

Question

Let's consider a grid in a multidimensional space. Each grid has 'n' number of lines, spaced one unit apart. A path (or walk) of 'm' steps is between two grid intersections. A step is a single unit movement in any dimension (direction).

I'll cut through the fluff by providing an example :

Let's say we have 2 dimensions and 3 grid lines. The grid intersections (x,y), where x,y ∈ {0,1,2}.

There will be six valid walks starting at (0,0) of length m=2:

(0,0)→(0,1)→(0,0)

(0,0)→(0,1)→(0,2)

(0,0)→(0,1)→(1,1)

(0,0)→(1,0)→(0,0)

(0,0)→(1,0)→(2,0)

(0,0)→(1,0)→(1,1)

Then generalize this for d dimensions, n gridlines, m steps and any starting point.

I'm not interested in knowing what the paths look like, just how many of them there are based on the starting location and the other parameters.

I wrote a python script (iterative and recursive) that kinda generates this (at each intersection, it generates all the possible following steps), but it chokes when the dimensions and steps start to get larger. Since we're supposed to know what's the highest count of paths possible considering all starting locations, this "brute-force" approach is definitely not the way to go I believe.

I was wondering if there was a way to solve this in a simpler manner, involving math to generate the number of final intersections to be visited based on the different parameters, without having to actually generate the paths maybe ?

Answer 1

The number of shortest paths from $(0,0,0)$ to $(a,b,c)$ is $$\frac{(a+b+c)!}{a!\;b!\;c!}$$ with an obvious extension to higher dimensions. This is a Multinomial Coefficient.

Answer 2

---Please note---
I'm not well versed in the topic being discussed.
Someone mentioned the same problem to me. This is my approach, which was based mostly on brute force and some chance encounter of adjacency matrices.

For anyone who is well versed in this, is this an approach worth using? Basically, did I get the answer?

I considered the following situation:
If I can create an matrix of for each of the possible coordinates (grid lines) and then list out possible single step (of length 1 unit), taking powers of the matrix following by sum of rows (or columns) of the result will yield possible total number of paths of length(l) taken 1 step at a time.

I have attempted this in R as follows:

library(Matrix)  

q <- list()#will house coordinates for a xyzk plane where each point will be enumerated
counter = 1  
for (i in 0:10){  
  for (j in 0:10){  
    for (k in 0:10){  
      for (l in 0:10){  
        q[[counter]]<- c(i,j,k,l)  
        counter = counter +1  
      }  
    }}}  
rm(counter,i,j,k,l)  #view length(q), should be 10^4  
length(q)  
a <- matrix(ncol=length(q),nrow=length(q),byrow = T)#making space  for adjacency matrix  
for(i in 1:length(q)){  
  for(j in 1:length(q)){  
    if(i==j){  
      a[i,j] <- 0#all diagonals are 0  
    }else{  
      if(sum(abs(q[[j]]-q[[i]]))==1){ #this calculates absolute path length  
        #since we are moving 1 step at a time we are only interested in   
        #step sizes of 1, so length = 1  
        a[i,j] <- 1  
      }else{a[i,j] <- 0}  
    }  
  }  
}  
rm(i,j,q)  
\#save space and speedier calculation by making it a sparse matrix  
a_sparse <- as(a,"dgCMatrix")  
\#remove large a  
rm(a)  

\#go 10 steps, each step is a power of the adjacency matrix  
mat_power <- function(m, pow){  
  v = as(diag(dim(m)[1]),"dgCMatrix")  
  for(i in 1:pow){  
    v <- v%*%m  
  }  
  return(v)  
}  
\#the calculation will take a bit of time  
\#note that using dgCMatrix saves space and also expedites calculation  
\#do not attempt to calculate powers for such large matrix from large matrix A  

steps <- mat_power(a_sparse,10)    
sums <- apply(steps, 1, sum)  

\# a neat thing to be noted is that this will yield steps of size 10 (taken 1 step at a time) for all possible starting points in that grid line.  

So starting form (0,0,0,0) I got a total of 44569728 steps that can be taken of size 10 (taken 1 at a time)