Find all the paths from node A to node B

Question

You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom right hand corner (southeast). From each node you can only move east, south, or diagonally southeast to the next adjacent node (assuming there is an adjacent node that permits moving in that direction). How many different paths are there from A to B?

I only found a brute-force method using a depth first search with a stack. Is there a more efficient algorithm to solve this puzzle? Specifically, I am looking for an algorithm (preferably efficient) that can determine the total number of paths you can take from node A to node B in a grid of evenly spaced nodes of size M x N.

Answer 1

Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that $$\begin{align} P(i, 0) &= 1\\ P(0, j) &= 1\\ P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0 \end{align}$$ Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot of redundant calls. You could improve this by memoizing the intermediate values: at step $k$, compute and save the values $P(0, k), P(1, k), \dotsc P(k,k)$ and the values $P(k, 0), P(k, 1), \dotsc P(k,k)$. Note that this last series actually doesn't need to be saved at all, since $P(a,b)=P(b,a)$.

---

For another way (which turns out to be conceptually the same as Yuval's answer), you could observe that a path consists of a collection of steps:

1. An eastward move, $E$, from node $(i,j)$ to node $(i+1, j)$.
2. A southward move, $S$, from node $(i,j)$ to node $(i, j+1)$.
3. A diagonal move, $D$, from node $(i,j)$ to node $(i+1, j+1)$.

So to get from $(0,0)$ to $(i,j)$ we will need to make $i$ moves east and $j$ moves south. Note that each diagonal move will contribute 1 to the eastward moves and 1 to the southward moves. Thus, every path from the origin to node $(i,j)$ can be uniquely described as a sequence of $E, S, D$ where the number of $E$s plus the number of $D$s equals $i$ and the number of $S$s plus the number of $D$s equals $j$. For example, $P(2,2)$ is the number of paths

1. Using no $D$s: $EESS, ESES, ESSE, SEES, SESE, SSEE$.
2. Using one $D$: $DES, DSE, EDS, SED, ESD, SED$.
3. Using two $D$s: $DD$

So we see that $P(2,2)=6+6+1=13$.

Now the number of sequences of three symbols $D,E,S$, in order, with $a$ of the $D$s, $b$ of the $E$s, $c$ of the $S$s, is given by the multinomial coefficient $$ \binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\;b!\;c!} $$ and from this and the observations we just made, we'll have, for $i\le j$, $$ P(i, j)=\sum_{k=0}^i\binom{i+j-k}{k,\ i-k,\ j-k}=\sum_{k=0}^i\frac{(i+j-k)!}{k!\;(i-k)!\;\ (j-k)!} $$ where $k$ is the number of $D$ moves, $i$ is the number of $E$ moves and $j$ is the number of $S$ moves. This sum of factorials is also somewhat computationally expensive, but by recognizing that there are some relations among the terms, you can slightly simplify the number of multiplications and divisions involved. Unfortunately, there doesn't appear to be any nice closed form for this sum, unlike the situation where we don't allow diagonal moves, in which case $P(i,j)=\binom{i+j}{i}$.

Answer 2

The answer is the coefficient of $x^N y^M$ in the generating function $$ \frac{1}{1-x-y-xy}. $$ This is because $$ \frac{1}{1-x-y-xy} = \sum_{\ell=0}^\infty (x+y+xy)^\ell, $$ and every term in the expansion of $(x+y+xy)^\ell$ corresponds to a walk of length $\ell$.

We can also obtain an explicit formula for it: $$ \sum_{t=0}^{\min(N,M)} \frac{(N+M-t)!}{t!(N-t)!(M-t)!}. $$ Here $t$ is the number of diagonal steps.