# Find the total Number of Path of length L

find the number of the path between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this?.

Any shortest path from $(0,0)$ to $(m,n)$ includes $m$ steps in the x axis and $n$ steps in the y axis. This is counted by the binomial coefficient $\binom{m+n}{m} = \binom{m+n}{n}$.

But what number about the total path exist of Length L in a grid and We can revisit the cell ?

• Do you want the number of paths (or rather walks) of a certain given length? Otherwise it is infinite. – Aryabhata Aug 21 '17 at 6:16
• @Aryabhata Yes walk , For a given Length L it's not infinite – Regression Aug 21 '17 at 6:18
• Did you mention $L$ before (or edit in after my comment)? I seem to have overlooked/missed that. And yes, it seems we are in agreement, – Aryabhata Aug 21 '17 at 6:19
• As far as I know, finding a closed form solution for the number of paths between two points on a grid using NSEW moves is an open problem. @Andres Mejia, do you have information about this problem? I believe we've spoken about it before. – Santana Afton Aug 21 '17 at 6:35

The classic method for counting number of walks of length $L$ on a graph $G$ are to take the corresponding adjacency matrix $A$ and compute $A^L$.

No idea if this approach can be used to give a closed form etc solution though.

Total number of walks from of length L from Point A to A is given by

number of possible walks is $$\sum_{k=0}^{L/2}\frac{L!}{k!^2(L/2-k!)!^2}={L\choose L/2}\sum_{k=0}^{L/2}{L/2\choose k}^2={L\choose L/2}^2$$

Since you are calculating from point A to B , so shortest path will be of distance $:X =|A.x-B.X| , Y=|A.y-B.y| , S=X+Y$ , now just iterate towards the remaining length

$$\sum_{k=0}^{L-S}\frac{L!}{k/2!(L-S-k)/2!*(X+K/2)!*(Y+(L-S-k)/2)!}$$

Note: $K$ is incremented twice i.e $K=K+2$ and some base condition also $(L-S)$ should be even else there will be no path

• Wow !! Beautiful – Regression Aug 21 '17 at 18:41
• Can you please explain the formula it will be more clear :) – Regression Aug 21 '17 at 18:43
• No !! not in mood – Marvel Aug 21 '17 at 19:01

Let $[x^p]$ denote the coefficient of $x^p$ in a series $A(x)$.

We consider lattice paths in $\mathbb{Z}\times\mathbb{Z}$ of length $L$ from $(0,0)$ to $(m,n)$ with steps in direction $(1,0),(0,1),(-1,0)$ and $(0,-1)$. The number of paths is given as: \begin{align*} \color{blue}{[x^my^nt^L]}&\color{blue}{\frac{1}{1-t\left(x+y+\frac{1}{x}+\frac{1}{y}\right)}}\\ &=[x^my^n]\left(x+y+\frac{1}{x}+\frac{1}{y}\right)^L\tag{1}\\ &=[x^my^n]\sum_{j=0}^L\binom{L}{j}\left(x+\frac{1}{x}\right)^j\left(y+\frac{1}{y}\right)^{L-j}\tag{2}\\ &=\sum_{j=0}^L\binom{L}{j}[x^{m}]x^{-j}(1+x^2)^j[y^{n}]y^{-L+j}(1+y^2)^{L-j}\tag{3}\\ &=\sum_{j=0}^L\binom{L}{j}[x^{m+j}](1+x^2)^j[y^{n+L-j}](1+y^2)^{L-j}\tag{4}\\ &\color{blue}{=\sum_{{j=0}\atop{{\,\,m\,\equiv\,j(2)}\atop{n+L\,\equiv\,j(2)}}}^L\binom{L}{j}\binom{j}{\frac{m+j}{2}}\binom{L-j}{\frac{n+L-j}{2}}}\tag{5} \end{align*}

Comment:

• In (1) we expand the geometric series and select the coefficient of $t^L$.

• In (2) we apply the binomial theorem.

• In (3) we use the linearity of the coefficient of operator and do some rearrangements as preparation for the next step.

• In (4) we apply the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

• In (5) we select the coefficients of $x^{m+j}$ and $y^{n+L-j}$.

Special case $L=m+n$

We put $L=m+n$ and obtain from (5)

\begin{align*} \sum_{{j=0}\atop{\,\,m\,\equiv\,j(2)}}^{m+n}&\binom{m+n}{j}\binom{j}{\frac{m+j}{2}}\binom{m+n-j}{n+\frac{m-j}{2}}\tag{6}\\ &=\sum_{j\color{blue}{=m}}^{\color{blue}{m}}\binom{m+n}{j}\binom{j}{\frac{m+j}{2}}\binom{m+n-j}{n+\frac{m-j}{2}}\tag{7}\\ &\color{blue}{=\binom{m+n}{m}} \end{align*} as expected.

Comment:

• In (6) we can skip one constraint since $n+L\equiv n+(n+m)\equiv m(2)$.

• In (7) we observe the middle binomial coefficient $\binom{j}{\frac{m+j}{2}}=0$ if $j<m$. We also note the right-hand binomial coefficient $\binom{m+n-j}{n+\frac{m-j}{2}}=0$ if $j>m$. We can therefore restrict the range of the index $j$ to $\{m\}$.

• very straightforward and nice answer! (as usually yours are) – G Cab Aug 21 '17 at 18:14
• @GCab: Details added. Regards, – Markus Scheuer Aug 24 '17 at 6:25