# Number of paths in a complex rectangle grid

Suppose we have a $M \times N$ grid with vertices placed as on the Cartesian plane. We want to walk from $(0,0)$ to the point $(m,n)$ within the grid.

The question is: How many paths are there if:

1. there is a line $y=x + k, (k < 0)$ and we cannot go beneath the line?
2. there is a line $y=x + k, (k > 0)$ and we cannot go above the line?
3. there are two such lines at the same time?

Suppose $(m,n)$ is always valid and we can only move 1 edge up or right. I know the solution exists for $k = 0$, which is a Catalan number, but this problem seems incredibly complicated.

EDIT:

Perhaps, the general problem stated above is too much complicated for case (3), but I can give a more specific problem (the one I am actually tackling), which will likely narrow down possible options vastly.

Let's elaborate the above conditions:

Suppose $M < N$

1. We wanna go from $(0,0)$ to $(N,M)$ (from origin to the opposite vertex of rectangle)
2. The first line is $y=x+(M-N)$ (it goes through the opposite vertex)
3. The second one lies above or on the $y=x$ line

Your first two questions can be solved by an application of the reflection principle used to find a formula for the Catalan numbers; they're no more complicated than that.

(I'll slightly change your notation and always assume $k>0$ and just consider lines $y=x-k$ and $y=x+k$ to make the notation more intuitive. I'll also assume that $m,n,k$ are such that it's possible to get from $(0,0)$ to $(m,n)$ without crossing the line: $n \ge m-k$ in the first case and $n \le m+k$ in the second.)

For the first question: with no restrictions on where we walk, there are obviously $\binom{m+n}{m}$ paths from $(0,0)$ to $(m,n)$. We biject paths that touch $y=x-k-1$ with paths from $(0,0)$ to $(n+k+1,m-k-1)$ by the following rule: find the first point of the form $(x,x-k-1)$ on the path, and reflect all steps following that, switching $(+1,0)$ steps and $(0,+1)$ steps. Note that:

• A path $(0,0)$ to $(m,n)$ that goes through $(x,x-k-1)$ was later going to increase by $(m-x, n-x+k+1)$, but is now going to increase by $(n-x+k+1, m-x)$, so it ends up at $(n+k+1,m-k-1)$, and vice versa.
• We can always find a point of the form $(x,x-k-1)$ on a line from $(0,0)$ to $(n+k+1,m-k-1)$, because we assume $n \ge m-k$, so $m-k-1 < (n+k+1)-k$.
• Because we always choose the first point of the form $(x,x-k-1)$ on the path, this reflection is an involution (it is its own inverse) which confirms that it's a bijection.

So the number of "bad paths" is equal to the number of paths from $(0,0)$ to $(n+k+1,m-k-1)$, and the final answer is $\binom{m+n}{m} - \binom{m+n}{m-k-1}$.

We deal with the second question similarly, except that we reflect starting at a point of the form $(x,x+k+1)$ instead, turning paths that go to $(m,n)$ into paths that go to $(n-k-1,m+k+1)$, and getting a final answer of $\binom{m+n}{m} - \binom{m+n}{m+k+1}$.

The third question is trickier to deal with. If we're lucky, we have lines $y=x-k_1$ and $y=x+k_2$ that are sufficiently far apart that we can't cross one line, return to cross the other, and then come back to touch $(m,n)$. If that's the case, we can just subtract off both kinds of "bad paths" and get $\binom{m+n}{m} - \binom{m+n}{m-k_1-1} - \binom{m+n}{m+k_2+1}$ as our answer.

We can handle cases where we can "zigzag" and cross both lines at most once as follows: if we reflect around the first point that's past either line, then this bijects "bad paths" going past $y=x-k_1$ with paths to $(n+k_1+1,m-k_1-1)$ that don't go past $y=x+k_2$, which we can solve using the earlier method, and "bad paths" going past $y=x+k_2$ with paths to $(n-k_2-1,m+k_2+1)$ that don't go past $y=x-k_1$, which we can also solve using the earlier method. You can see how this gets complicated quickly.

On the other hand, if the two lines $y=x-k_1$ and $y=x+k_2$ are very close together, and $(m,n)$ is between then and very far from $(0,0)$, it might make sense to write a linear recurrence, as follows:

• Let $r_{i,j}$ be the number of paths between the lines that have $x-y=i$ when they reach the line $x+y=j$ (that is, after $j$ steps).
• We think of this as a one-term linear recurrence on the vector $$(r_{-k_2,j}, r_{-k_2+1,j}, \dots, r_{k_1,j}) \in \mathbb Z^{k_1+k_2+1}$$ because we can solve for the $j+1$ vector in terms of the $j$ vector.
• The final answer is $r_{m-n,m+n}$.

The characteristic polynomial of this recurrence has degree $k_1+k_2+1$, so the bigger this value, the worse the final answer.