Finding the number of lattice paths

Question

Find the number of lattice path of length $2n$ that starts on $(0, 0)$ such that for all the points $(x, y)$ in the path, $x < y$. So pretty much all the points besides the origin are strictly above the line $y = x$.

What I have done so far is that, given a point: $$p =(k, 2n-k)$$ We know that $$k < 2n - k$$ The total number of path paths will be $${2n \choose k}$$

so my approach is that in order for the paths to not meet the requirement, it must have some other point on the diagonal.

I defined a set $A(j)$, which consists of paths from $(0, 0)$ to $(j, j)$ where no points other than the origin and endpoint.

I found that $|A(j)| = \frac{2}{j} {2n-2 \choose n-1}$ because for every such path, if you take away the first and last step, it becomes dyck path from $(0, 0)$ to $(j-1, j-1)$.

Then you multiply that by the number of paths from$(j, j)$ to $(k, 2n-k)$. Which is $${2n-2j \choose k-j}$$

Thus, $$B(j) = |A(j)|{2n-2j \choose k-j} $$ will be the amount of paths from $(0, 0)$ to point $p$ such that $(j, j)$ is the first point in the diagonal.

Then I do $$F(p)=\sum_{j=1}^{k} B(j)$$ To get amount of all the paths that intersects with the diagonal at least once after the origin. Subtracting that from the total amount of paths possible I get the number of paths that meets the requirement for that point.

Then I do it for all the points to get a total number of paths that never intersects with diagonal. But I'm kinda stuck on the summation part. Is there another approach to this?

Answer 1

We consider lattice paths starting from $(0,0)$ containing horizontal $(1,0)$-steps and vertical $(0,1)$-steps only, with $x<y$ at all other points besides the origin.

The following is valid. The number of paths of length $2n$ starting at $(0,0)$ and never touching the diagonal $x=y$ again is \begin{align*} \binom{2n-1}{n-1}\qquad\qquad\qquad n\geq 1 \end{align*}

Note, the number of paths of shortest length from $(x_0,y_0)$ to $(x_1,y_1)$ with $x_0\leq x_1$ and $y_0\leq y_1$ is \begin{align*} \binom{(x_1-x_0)+(y_1-y_0)}{x_1-x_0}\tag{1} \end{align*}

Paths of length $2n$ starting at $(0,0)$ and never touching the diagonal again end in points \begin{align*} (k,2n-k)\qquad\qquad\qquad 0\leq k \leq n-1 \end{align*}

Since the first step is always from $(0,0)$ to $(0,1)$ in order to walk above the diagonal, we consider at first the number of all paths from $(0,1)$ to $(k,2n-k)$. This number is according to (1)

\begin{align*} \binom{2n-1}{k}\qquad\qquad\qquad 0\leq k \leq n-1 \end{align*}

From this number we have to subtract the number of all paths from $(0,1)$ to $(k,2n-k)$ which touch (or cross) the diagonal $x=y$.

This can be determined using Andre's Reflection Principle: A path starting from $(0,1)$ going to $(k,2n-k)$ which touches the diagonal, will touch it the first time let's say at $(t,t)$. So, each such path consists of two parts. The first part from $(0,1)$ to $(t,t)$ and the second from $(t,t)$ to $(k,2n-k)$. We bijectively map paths of this shape by reflecting the first part at the diagonal and leaving the second part unchanged. This way we get a reflected path starting at $(1,0)$ crossing at $(t,t)$ the diagonal the first time and ending in $(k,2n-k)$.

We conclude: The number of paths from $(0,1)$ to $(k,2n-k)$ which touch the diagonal $x=y$ is equal to the number of all pathes from $(1,0)$ to $(k,2n-k)$ and is according to (1) \begin{align*} \binom{2n-1}{k-1} \end{align*}

Let's denote with $P_k(n)$ the number of all paths from $(0,0)$ to $(k,2n-k)$ which do not touch the diagonal again. The following is valid for $n\geq 1$ \begin{align*} P_k(n)= \begin{cases} 1\qquad\qquad &k=0\\ \binom{2n-1}{k}-\binom{2n-1}{k-1}\qquad\qquad &k\geq 1 \end{cases}\tag{2} \end{align*}

Note that for $k=0$ there is exactly one path from $(0,0)$ to $(0,2n)$. Since in this case there are no paths touching the diagonal which are to subtract, we interpret the binomial coeffient $\binom{r}{s}$ with negative $s$ as usual with zero and we obtain $P_0(n)=\binom{2n-1}{0}-\binom{2n-1}{-1}=1$.

Now it's time to harvest: The number of all paths of length $2n$ starting at $(0,0)$ and never touching the diagonal again is \begin{align*} \sum_{k=0}^{n-1}P_k(n)&=\sum_{k=0}^{n-1}\left(\binom{2n-1}{k}-\binom{2n-1}{k-1}\right)\\ &=\sum_{k=0}^{n-1}\binom{2n-1}{k}-\sum_{k=1}^{n-1}\binom{2n-1}{k-1}\tag{3}\\ &=\sum_{k=0}^{n-1}\binom{2n-1}{k}-\sum_{k=0}^{n-2}\binom{2n-1}{k}\\ &=\binom{2n-1}{n-1} \end{align*} and the claim is proved.

Comment: In (3) we split the sum and skip the index $k=0$ in the right hand sum since it's contribution is zero. In the following line we shift the index by $1$ in the right hand sum.