Number of paths in a grid moving E, NE, SE only and ending in the top right

Question

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.

Answer 1

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.