How many walks are there from $(0,0)$ to $(N, r)$ on $\mathbb Z^2$ along diagonals?

Question

Suppose we are looking at all paths from $(0,0)$ to $(N,r)$ using only the steps $(1,\pm 1)$ while always staying between the horizontals $y=r-1$ (except for the last step) and $y=-l$.

Visualization:

Roughly speaking, I am looking at all paths consisting only of unit diagonals up/down between the two blue points while always staying between the two horizontal lines. The green line indicates the last step, which is the only possible last step since we have to stay below the red line in all prior steps.

My question. How many such paths are there for any given $N,l$ and $r$?

---

Remarks.

• This question popped up while I was looking at a Bernoulli path based on this MSE question.
• If $F(N, l,r)$ denotes the number of such paths, then $F$ satisfies $$F(N,l,r)=\begin{cases}1, &\text{ if } \min(N,l)\geq0 \land N=r \\ 0, &\text{ if } \min(N,l,r)<0\lor (N\geq 1 \land r\le 0)\lor r >N\\ F(N-1, l-1,r-1)+F(N-1,l+1,r+1), &\text{ otherwise} \end{cases}. $$ Is there any good way to get a simplified expression out of this?
• If $l\geq \frac{N-d}2$, then the triangular sequence $$\begin{matrix} F(1,l,1) \\ F(2,l,1) & F(2,l,2) \\ F(3,l,1) & F(3,l,2) & F(3,l,3) \\ \dots & \dots & \dots & \ddots \end{matrix}$$ is simply the Catalan triangle with $0$s.

Answer 1

We consider OP's problem in a slightly more convenient (symmetrical) setting:

Let $0\leq n\leq m$. We are looking for the number $L_{m,n;r,s}$ of lattice paths starting in $(0,0)$ and ending in $(m,n)$ which do not reach the lines $y=r$ and $y=-s$ where $r,s>0$. Admissible steps are $(1,1)$ and $(1,-1)$.

We show the following is valid:

\begin{align*} \color{blue}{L_{m,n;r,s}}&\color{blue}{=\binom{m}{\frac{m+n}{2}}-\sum_{j\geq0}\left[\binom{m}{\frac{m+n}{2}-(j+1)r-js} +\binom{m}{\frac{m+n}{2}+jr+(j+1)s}\right]}\\ &\qquad\qquad\qquad\color{blue}{+\sum_{j\geq1}\left[\binom{m}{\frac{m+n}{2}+j(r+s)} +\binom{m}{\frac{m+n}{2}-j(r+s)}\right]}\tag{1}\\ \end{align*}

Note, the sums in (1) are finite since $\binom{p}{q}=0$ if $q<0$ or $q>p$. OPs problem is looking for the number of paths from $(0,0)$ to $(N-1,r-1)$ which do not reach the lines $y=r$ and $y=-(l+1)$, so that (1) can be applied with \begin{align*} m&=N-1\\ n&=r-1\\ s&=l+1\\ \end{align*}

We prove (1) in three steps. At first we are looking for the number of paths from $(0,0)$ to $(m,n)$ without boundary restrictions using steps $(1,1)$ and $(1,-1)$.

Step 1: The number $L_{m,n}$ of paths from $(0,0)$ to $(m,n)$ where $0\leq n\leq m$ is \begin{align*} \color{blue}{L_{m,n}=\binom{m}{\frac{m+n}{2}}}\tag{2} \end{align*}

We show (2) algebraically. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We encode the steps $(1,1)$ with $xy$ and $(1,-1)$ with $\frac{x}{y}$. We obtain \begin{align*} L_{m,n}&=[x^my^n]\left(xy+\frac{x}{y}\right)^m\tag{3}\\ &=[x^my^n]x^my^{-m}\left(1+y^2\right)^m\\ &=[y^{m+n}]\sum_{j=0}^m\binom{m}{j}y^{2j}\tag{4}\\ &=\binom{m}{\frac{m+n}{2}}\tag{5} \end{align*} and the claim follows.

Comment:

• In (3) we note that each step is either $(1,1)$ or $(1,-1)$ which can be encoded as $xy+\frac{x}{y}$.

• In (4) we expand the binomial and apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

• In (5) we select the coefficient of $y^{m+n}$. We also note according to the specific steps $(1,1)$ and $(1,-1)$ the parity of $m$ and $n$ is the same so that $\frac{m+n}{2}$ is always an integer.

Step 2: The number $L_{m,n;r,-}$ of paths from $(0,0)$ to $(m,n)$ where $0\leq n\leq m$ which do not reach the boundary $y=r$ with $r>0$ is \begin{align*} \color{blue}{L_{m,n;r,-}=\binom{m}{\frac{m+n}{2}}-\binom{m}{\frac{m+n}{2}-r}}\tag{6} \end{align*}

We prove (6) using Andre's reflection principle. The number of all paths from $(0,0)$ to $(m,n)$ is $L_{m,n}$. We subtract all invalid paths which are those reaching the line $y=r$. An invalid path touches (or crosses) the line a first time. We reflect each invalid path part from the origin to the first contact with $y=r$ at $y=r$ and obtain all paths from $(0,2r)$ to $(m,n)$.

Denoting with $L[(0,2r),(m,n)]$ the number of all invalid paths we have \begin{align*} L[(0,2r),(m,n)]&=L_{m,n-2r}=\binom{m}{\frac{m+n}{2}-r} \end{align*} and the claim (6) follows.

Step 3: The number $L_{m,n;r,s}$ with boundaries at $y=r$ and $y=-s$ is given by (1).

This number can be calculated using Andre's reflection principle in conjunction with the inclusion-exclusion principle (PIE).

• We denote with $L(A_1)$ the paths which reach $y=r$, with $L(A_2)$ the paths which reach $y=r$, then $y=-s$ in that order, with $L(A_3)$ the paths which reach $y=r$, then $y=-s$, then $y=r$ in that order, etc.

• Analogously w denote with $L(B_1)$ the paths which reach $y=-s$, with $L(B_2)$ the paths which reach $y=-s$, then $y=r$ in that order, with $L(B_3)$ the paths which reach $y=-s$, then $y=r$, then $y=-s$ in that order, etc.

• Application of PIE as compensation for double counting gives

\begin{align*} \color{blue}{L_{m,n;r,s}=\binom{m}{\frac{m+n}{2}} + \sum_{j\geq 1}(-1)^j\left(L(A_j)+L(B_j)\right)}\tag{7} \end{align*}

We find by application of the reflection principle \begin{align*} L(A_1)&=L\left[(0,2r),(m,n)\right]=L_{m,n-2r}=\binom{m}{\frac{m+n}{2}-r}\\ \color{blue}{L(A_{2j+1})}&=L\left[(0,2(j+1)r+2js),(m,n)\right]=L_{m,n-2(j+1)r-2js}\\ &\,\,\color{blue}{=\binom{m}{\frac{m+n}{2}-(j+1)r-js}}\qquad\qquad \color{blue}{j\geq 0}\tag{8}\\ L(A_2)&=L\left[(0,-2r-2s),(m,n)\right]=L_{m,n+2r+2s}=\binom{m}{\frac{m+n}{2}+r+s}\\ \color{blue}{L(A_{2j})}&=L\left[(0,-2jr-2js),(m,n)\right]=L_{(m,n+2jr+2js}\\ &\,\,\color{blue}{=\binom{m}{\frac{m+n}{2}+jr+js}}\qquad\qquad\qquad\ \ \color{blue}{j\geq 1}\tag{9}\\ \end{align*} Analogously we obtain \begin{align*} L(B_1)&=L\left[(0,-2s),(m,n)\right]=L_{m,n+2s}=\binom{m}{\frac{m+n}{2}+s}\\ \color{blue}{L(B_{2j+1})}&=L\left[(0,-2jr-2(j+1)s),(m,n)\right]=L_{m,n+2jr+2(j+1)s}\\ &\,\,\color{blue}{=\binom{m}{\frac{m+n}{2}+jr+(j+1)s}}\qquad\qquad \color{blue}{j\geq 0}\tag{10}\\ L(B_2)&=L\left[(0,+2r+2s),(m,n)\right]=L_{m,n-2r-2s}=\binom{m}{\frac{m+n}{2}-r-s}\\ \color{blue}{L(B_{2j})}&=L\left[(0,2jr+2js)\right]=L_{m,n-2jr-2js}\\ &\,\,\color{blue}{=\binom{m}{\frac{m+n}{2}-jr-js}}\qquad\qquad\qquad\ \ \color{blue}{j\geq 1}\tag{11}\\ \end{align*}

Finally putting (7) - (11) together we get the claim (1).

Example:

Now it's time to harvest. So, let's make an example which can also be easily manually checked. We look for the number of paths from $(0,0)$ to $(14,2)$ which do not reach the boundary lines $y=4$ and $y=-3$.

This number is $\color{blue}{L_{14,2;4,3}=1\,652}$ which is marked red in the graphic below.

Applying (1) we obtain \begin{align*} \color{blue}{L_{14,2;4,3}}&=\binom{14}{8}-\sum_{j\geq0}\left[\binom{14}{8-4(j+1)-3j} +\binom{14}{8+4j+3(j+1)}\right]\\ &\qquad\qquad\qquad+\sum_{j\geq1}\left[\binom{14}{8+7j} +\binom{14}{8-7j}\right]\\ &=\binom{14}{8}-\left[\binom{14}{4}+\binom{14}{11}\right]+\left[\binom{14}{1}\right]\tag{12}\\ &=3\,003-\left(1\,001+364\right)+\left(14\right)\\ &\,\,\color{blue}{=1\,652} \end{align*}

in accordance with the manual calculation in the graphic.

• In (12) we have two summands in brackets. They give the number of reflected paths indicated in the graphic via $A_1$ and $B_1$.

• The right-most summand in (12) gives the number of reflected paths indicated in the graphic via $B_2$.

• No more reflections need to be considered in this example.