[Solved]: Find all the paths from node A to node B

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 $ile j$, $$ P(i, j)=sum_{k=0}^ibinom{i+j-k}{k, i-k, j-k}=sum_{k=0}^ifrac{(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}$.