North-East lattice path exceeding threshold

Question

Given a maximum of $N$ turns of movement ($m+k \leq N$), I want to find how many paths there are from $(0,0)$ to $(m,k)$ where $m-k\geq t$ at some point on the path for an integer $t$.

I've tried this from a combinatorial perspective and a recursion/generating function perspective, but don't know enough about either to take this further. Here's my work/intuition thus far:

Combinatorial Perspective:

The number of paths to $(m,k)$ using only north and east steps is $$m+k \choose m$$

Therefore, I thought I just had to find all points (m,k) that satisfy my conditions, but this isn't the case due to overlap. For example, if $t=2$, a path to (5,3) has several paths that end at $(4,2)$, and so there are cases where a path goes through both or many more of these candidates points.

Another approach I had was to try a recursion/generating function model and got the following:

Every step is either one step closer or one step further from the condition $m-k\geq t$. Therefore, I can make a function $F$ such that $$F(d,n)$$ represents the number of steps that is a distance d away from satisfying the condition and has a maximum of n terms remaining. Then, my problem statement allows for

$$F(d,k) = F(d+1,n-1) + F(d-1,n-1)$$

Since after one move, we are either one step closer, or one step further from the case working. Note that $F(0,n_0) = 1$ and $F(d_0,0) = 0$ for $d_0 \neq 0$ since we only want to count each success once, and end the recursion.

I suspect there is a generating function solution to my formulation, but I ran into computational errors, most likely due to my lack of knowledge about the subject. Any advice would be greatly appreciated

Answer 1

Set up the function $F_t(i,j)$ in the folowing way:

$$ F_t(i,j)=\begin{cases} 0,& i=-1\text{ or } j=-1, \text{ or } i-j>t,\\ 1,& i=0 \text{ and } j=0,\\ F_t(i-1,j)+F_t(i,j-1),& \text{otherwise}. \end{cases} $$

Then the function $\binom{m+k}k-F_t(m,k)$ will give the result in question.

Answer 2

Let $N(m,k)$ denote the number of any north-east path in a lattice from $(0,0)$ to $(m,k)$ on which some point $(x',y')$ satisfies $x'-y' \ge t$.

When $m$ and $k$ are fixed with $m\ge t$, the solution for $ \boldsymbol{k \ge m-t}$ is

$$ N(m,k)= \binom{ m+k}{m-t}.$$

To prove this, it is enough to determine the number of paths from $(0,0)$ to $(m,k)$ that cross the line $y=x-t$. Such a path can be one-to-one related to a unique path starting from $(t,-t)$ and ending to $(m,k)$. To see this, reflect the whole part of the original path before touching the line $y=x-t$ for the first time with respect to the line $y=x-t$. Hence, the number of desired paths is equal to the number of north-east paths from $(t,-t)$ to $(m,k)$, which is

$$ \binom{ m-t+k-(-t)}{m-t}.$$

If $k<m-t$, only those north-east paths from $(t,-t)$ to $(m,k)$ are acceptable that cross the $x$-axis at one of the points $(t,0), \dots, (t+k,0)$ (those violating this condition are not related to a feasible path in the original lattice). Therefor, the solution for $ \boldsymbol {k < m-t}$ is given by

$$ N(m,k)= \sum_{i=0}^{k}\binom{ i+t}{t}\binom{ m+k-t-i}{k}.$$

In sum, for $m\ge t, k\ge 0$, the general solution can be written as follows:

$$ N(m,k)= \sum_{i=0}^{\min\{k, \, m-t\}}\binom{ i+t}{t}\binom{ m+k-t-i}{k}.$$

I am not sure that this can be simplified further unless for $ k \ge m-t$, discussed earlier.

For a given $N \ge t$, when $m$ and $k$ are variable with $m+k\le N, m \ge t, k \ge 0$, the solution is

$$ \sum_{m=t}^{N}\sum_{k=0}^{N-m} N(m,k).$$