6
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Do you want the number of paths (or rather walks) of a certain given length? Otherwise it is infinite. $\endgroup$ – Aryabhata Aug 21 '17 at 6:16
  • $\begingroup$ @Aryabhata Yes walk , For a given Length L it's not infinite $\endgroup$ – Regression Aug 21 '17 at 6:18
  • $\begingroup$ 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, $\endgroup$ – Aryabhata Aug 21 '17 at 6:19
  • $\begingroup$ 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. $\endgroup$ – Santana Afton Aug 21 '17 at 6:35
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

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\}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.