Q:

Number of lattice paths between two vertical lines

There are two vertical lines, $l_1$ from $(0,0)$ to $(0,n)$ and $l_2$ from $(m,0)$ to $(m, n)$.
Prove that the number of north-east lattice paths that start on the line $l_1$ and end on the line $l_2$ are: $$\binom{n+m+2}{n}$$
My initial thought is that smallest possible lattice path would just be a set of horizontal steps and would be of length $m$ and the biggest path would be have $n+m$ steps in total. I am not quite sure how to frame a summation that would give the above combination equation.

A:

Let $P$ be the set of lattice paths from $\ell_1$ to $\ell_2$ using only steps to the north and steps to the east, and let $Q$ be the set of such paths from $\langle -1,0\rangle$ to $\langle m+1,n\rangle$. A path in $Q$ must comprise $m+2$ steps to the east and $n$ steps to the north; these $n+m+2$ steps can occur in any order, and any sequence of such steps is a path in $Q$, so $|Q|=\binom{n+m+2}n$. I claim that there is a bijection between $Q$ and $P$, so that $|P|=\binom{n+m+2}n$ as well.
Suppose that $q\in Q$; $q$ begins with $k$ steps to the north for some $k$ such that $0\le k\le n$, but eventually it must take a step to the east. At that point it intersects $\ell_1$ at $\langle 0,k\rangle$. It continues until it hits $\ell_2$ at some point $\langle m,\ell\rangle$ such that $k\le\ell\le n$. It may proceed north for a bit on $\ell_2$, but at some point $\langle m,j\rangle$ it must go east to $\langle m+1,j\rangle$ and continue north to $\langle m+1,n\rangle$. Let $p_q$ be the part of $q$ from $\langle 0,k\rangle$ to $\langle m,j\rangle$; clearly $p_q\in P$. Conversely, if $p\in P$ starts at $\langle 0,k\rangle$ and ends at $\langle m,j\rangle$, we can extend it to a $q\in Q$ by adding $k$ steps to the north followed by one to the east before $p$ and one to the east followed by $n-m$ to the north after $p$; then clearly $p=p_q$. Thus, the correspondence $q\leftrightarrow p_q$ is a bijection between $Q$ and $P$, and $|P|=\binom{n+m+2}n$.

