Number of paths between two lines , Catalan Numbers

Question

Find the number of paths with length of 14 between (0,0) and (7,7) which do not go above the line $y=x+1$ and do not go beneath the line $y=x-3$ ? every step in the path is either right or up.

In order to find the number of the paths from (0,0) to (7,7) which don't go above the line $y=x+1$ I used the reflection Lemma, I did the same for the paths which don't go beneath the line $y=x-3$: I thought about using inclusion-exclusion. let F be the amount of the paths from (0,0) to (7,7) which means: $7+7 \choose 7 $ =3432

Let $F_1$ be the number of paths from (0,0) to (7,7) which GO above the line $y=x+1$ which means: $5+9 \choose 5$

and finally, Let $F_2$ be the number of paths from (0,0) to (7,7) which GO beneath the line $y=x-3$ which means: $11+3 \choose 3$

Now, I need to calculate: $F-(F_1+F_2-F_1\cap F_2$). I can't figure out how to find the intersection between the two.
Thanks in advance.

Answer 1

You can find the number of paths crossing both lines by repeated use of the reflection lemma. The paths which cross the upper line reflect to paths to (5,9). Any which later crossed the lower line as well become paths that cross y = x + 7. So reflect again in the line y = x + 8 and these paths become ones ending at (13,1), of which there are 14. Similarly, paths which cross the lower line first and then the upper become, after two reflections, paths to (1,13) and there are again 14.

So $F-(F_1+F_2-F_1\cap F_2) = {14\choose7} - {14\choose5} - {14\choose3} + 28 = 1094$.

Answer 2

@Jack D'Aurizio.

Here is an approach using linear algebra:

Let us call "admissible" a path situated between the given lines.

Let us define $A_k=(k,k+1), \ \ B_k=(k+1,k), \ \ C_k=(k+2,k-1)$ for $k=1\cdots5.$

(blue dots on figure below)

Let $a_k,b_k,c_k$ the number of admissible paths starting in $O(0,0)$ ending in $A_k,B_k,C_k$ resp.

The only thing is to convince oneself that these numbers are governed by the following iteration:

$$\tag{1}\begin{cases}a_{n+1}&=&a_n&+&b_n&&\\b_{n+1}&=&a_n&+&2b_n&+&c_n\\c_{n+1}&=&&&b_n&+&c_n\end{cases}$$

(coefficient 2 for $b_n$ on the second line is justified by the fact that there are 2 ways to proceed from point $B_n$ to point $B_{n+1}$).

This process works for the major reason that any of the admissible paths from $(0,0)$ to $(7,7)$ crosses line $x+y=2k+1$ either in $A_k$, "exclusive or" in $B_k$ "exclusive or" in $C_k$ (this could be phrased in terms of imbricated partitions of the set of admissible paths).

(1) can be expressed under the form of a matrix-vector iteration:

$$\tag{2}\underbrace{\begin{pmatrix}a_{n+1}\\b_{n+1}\\c_{n+1}\end{pmatrix}}_{V_{n+1}}=\underbrace{\begin{pmatrix}1&1&0\\1&2&1\\0&1&1\end{pmatrix}}_M\underbrace{\begin{pmatrix}a_{n}\\b_{n}\\c_{n}\end{pmatrix}}_{V_{n}} \ \ \ \ \ \ \text{with} \ \ \ \ V_1=\begin{pmatrix}a_1\\b_1\\c_1\end{pmatrix}=\begin{pmatrix}2\\3\\1\end{pmatrix}$$

It suffices then to compute $V_5=M^4 V_1$ in order to get $a_5,b_5,c_5$.

The final result will be:

$$\tag{3}2a_5+3b_5+c_5=1094.$$

Remark 1: coefficients 2,3,1 in (3), which are the same as the coefficients of $V_1$ in (2), are found by looking at the different ways to connect $O(0,0)$ to $A_1,B_1$ or $C_1$ and the same for connecting $A_5,B_5$ or $C_5$ to terminal point $(7,7)$.

Remark 2: I just realized that, instead of considering 3 series of points $A_k,B_k,C_k$, it was enough to consider the 2 series $D_k,E_k$ of intermediate points with coordinates $D_k=(k,k)$ and $E_k=(k+1,k-1)$ ($k=1 \cdots 6$) giving rise to the simpler computation:

$$\begin{pmatrix}2&1\end{pmatrix}\begin{pmatrix}2&1\\1&2\end{pmatrix}^5\begin{pmatrix}2\\1\end{pmatrix}=1094.$$