Grid navigation problem

Question

The number of paths from one point to another through a grid can be solved in two methods: either by combinations or by implying the concept of Pascal's triangle. My question is: Should the grid necessarily be square or rectangular? If the grid is triangular, and one wants to go from one point to another, can the number of paths be counted? And I also want to ask, what will be the solution in case of a 3d grid? This is where I am getting stuck. If someone helps me with the problems, I'll be obliged.

Answer 1

For counting walks, the situation is fairly simple.

First, for any finite graph (directed or not, or even a multigraph) $G$ with adjacency matrix $A$, and a natural number $n$, the matrix $A^n$ counts walks of length exactly $n$ - namely, its entry at $(u,v)$ (where $u$ and $v$ are vertices of $G$, and we "number" rows and columns of the matrices with vertices) is equal to the number $W_{u,v}^G(n)$ of walks of length $n$ from $u$ to $v$, and if we now consider the "exponential generating function" (EGF) $$F_{u,v}^G(t)=\sum_{n=0}^{\infty}\frac{W_{u,v}^G(n)}{n!}t^n,$$ the matrix formed by all these functions is $e^{tA}$.

Next, rectangular grids are special cases of cartesian products of graphs (in particular, 3D grid is a product of three simple path graphs). Let $G_1, G_2$ be graphs. A walk of length $n_1$ from $u_1$ to $v_1$ in $G_1$, together with a walk of length $n_2$ from $u_2$ to $v_2$ in $G_2$, give rise to $\binom{n_1 + n_2}{n_1} = \frac{(n_1 + n_2)!}{n_1! n_2!}$ walks of length $n_1 + n_2$ from $(u_1, u_2)$ to $(v_1, v_2)$ in the cartesian product $G_1\ \Box\ G_2$ of $G_1$ and $G_2$. From this it is easy to conclude that $$F_{(u_1,u_2),(v_1,v_2)}^{G_1\ \Box\ G_2}(t) = F_{u_1,v_1}^{G_1}(t) F_{u_2,v_2}^{G_2}(t).$$ Thus, the EGF counting walks in cartesian product of two (or more!) graphs is simply the product of EGFs for each of the graphs. In terms of matrices, this corresponds to Kronecker products.

In particular, this allows you to get the EGF for 3D rectangular grids if you compute it for 1D paths. In the undirected case, the latter requires you to compute $e^{tA}$ for tridiagonal matrix $A$ of the form $$\begin{bmatrix} 0 & 1 & & & & & \\ 1 & 0 & 1 & & & & \\ & 1 & 0 & 1 & & & \\ & & 1 & 0 & 1 & & \\ & & & 1 & 0 & 1 & \\ & & & & 1 & 0 & 1 \\ & & & & & 1 & 0\end{bmatrix}.$$ (In the directed case this is trivial - at most a single walk is possible - and gives well-known results for, say, 2D grid with "up" and "right" movements possible, and similarly for greater dimensions.)

The rest depends on the form of computation results you need (a general formula for a given graph, or the first few values, or whatever else).