3
$\begingroup$

I've been trying to find a solution to this problem for a few days now and I'm hoping someone here may be able to help.

I'm trying to find the total number of paths in a MxN grid with the following rules/restrictions.

  • Path must start from (0,0) and end at (M,N).

  • Each step can only be E (1,0), NE (1,1) or SE (1, -1)

  • Once the path reaches height N it may only travel East

Pretty much the end location of a Delannoy path and the direction restrictions of a Motzkin path.

Heres a table of values if it helps. I noticed a few patterns, a couple are obvious so I won't list them. But theres also the N=1 column can be calculated with f(x) = $2^M-1$ And starting from N=1, M=3 is this pattern A027379 along the diagonal.

Table of (M,N) values ( To clarify the table values are the number of unique paths in a grid of size (M,N) following the restrictions listed above )

EDIT 1:

I've created an image to better explain everything, it shows all unique paths for a few different M,N cases. Unique paths illustration

Also I've made a little progress. I think this can be broken into two sub problems.

  • A) Unique paths excluding SE moves
  • B) Unique paths with at least one SE move

And then the total paths is of course A+B

Because we have to move North East exactly N times and there are M possible places we know that A = $\binom{M}{N}$

I'm not sure how to find B though. I know that if we look at the unique paths we get without any SE moves we find that the SE moves are duplicates of paths where two consecutive E moves happen and where 0 < Y < N. The E, E moves just become SE, NE

EDIT 2 In case it helps here is a table of the number of paths with SE moves for each case in the previous table. SE paths per grid size

EDIT 3 I’ve been unable to solve this after almost six days. If anyone knows there is no closed solution to this problem and can prove or explain why, that’d be much appreciated so I can give up on it.

$\endgroup$
11
  • $\begingroup$ You could compute this via the following relation, where $f(x,y)$ is the number of paths from $(0,0)$ to $(x,y)$: $$f(x,y) = \begin{cases} 0 & y > x \\ f(x-1,y-1) + f(x-1,y) + f(x-1,y+1) & 0 < y < M \\ f(x-1,y) + f(x-1, y+1) & y=0 \\ f(x-1,y-1) + f(x-1,y) & y=M \end{cases}$$ If you're looking for a closed form however, I think I'm a little out of my depth. $\endgroup$
    – J. Young
    Oct 26, 2017 at 23:46
  • $\begingroup$ Was looking for a closed form but I'm not sure if one even exists. Maybe it's only computable recursively $\endgroup$
    – Kyle Goodale
    Oct 26, 2017 at 23:55
  • 1
    $\begingroup$ I don't understand your table. E.g., for $N=1$ the largest $M$ that can be reached is $M=1$. But in your table $M>1$ can also be reached (in one path). Can you explain? $\endgroup$
    – Jens
    Oct 27, 2017 at 1:19
  • $\begingroup$ @Jens Oh sorry, N and M are the size of the grid. M is the X and N is the Y. But now that I’m looking at it you’re correct the N=1 column shouldn’t be all 1’s. I’ll edit the table. $\endgroup$
    – Kyle Goodale
    Oct 27, 2017 at 1:40
  • $\begingroup$ Your notation is still very confusing. In your question you talk about an "NxM grid" and about the "height M", but then you present a table of MxN values and say M is the X value. In any case, I'm not getting the same values as your table. My interpretation of the setup is the same as @Wolfups gave above. $\endgroup$
    – Jens
    Oct 27, 2017 at 1:59

1 Answer 1

Reset to default
0
$\begingroup$

The fact that all valid moves take you east makes the problem tractable.

Consider the case $N=3$. Turn the grid $90^\circ$ so that you start on the left-hand side of the top row, and move downwards. Let's count the paths. In the top row, we always start on the left, so the first row looks like this: $$\begin{matrix}1&0&0&0\end{matrix}$$ To count the paths ending in the next row, we add up like this: $$\begin{matrix}1\quad&0&\quad0&\quad0\\\downarrow\swarrow&\searrow\downarrow\swarrow&\searrow\downarrow&\searrow\downarrow\\1\quad&1&\quad0&\quad0\end{matrix}$$ Continuing, we get: $$\begin{matrix}1&0&0&0\\1&1&0&0\\2&2&1&0\\4&5&3&1\\9&12&8&4\\\vdots&\vdots&\vdots&\vdots\end{matrix}$$ The last column gives the sequence we want; it's just a running total of the values in the second-last column.

Call the columns $A,B,C,S$. What we have is a system of linear recurrences. Let $A(x),B(x),$ $C(x),S(x)$ be the generating functions. Then:

$$A-1=x(A+B),\quad B=x(A+B+C),\quad C=x(B+C),\quad S=x(S+C)$$

We can solve this by expressing $A(x)$ and $C(x)$ in terms of $B(x)$, then substituting into the second equation; it turns out that $B(x)=\frac{x}{1-2x-x^2}$, so $C(x)=\frac{x^2}{(1-2x-x^2)(1-x)}$ and thus

$$S(x)=\frac{x^3}{(1-2x-x^2)(1-x)^2}$$

If you go to WolframAlpha and enter 

series at x=0 of x^3/((1-2x-x^2)(1-x)^2)
you will notice that the coefficients are the entries in the last column: $1,4,12,32,81,200,\dots$ If you scroll down you will even see a formula.

$\endgroup$
2
  • $\begingroup$ I'm a little confused on how to use that to create a closed function where given the grid dimensions it will return the amount of unique paths. I.e f( 7, 4 ) = 56. I do see the coefficients for the example you gave match the N=3 column but I'm not sure how to use that for any N column $\endgroup$
    – Kyle Goodale
    Oct 28, 2017 at 19:52
  • $\begingroup$ @Andrew woods The fifteen rows is the sequence (9,12,9,4)! Could you please the ordinary generating function of this lattice in general case? $\endgroup$
    – d.y
    Oct 28, 2017 at 21:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .