# Catalan Numbers: Number of Lattice Paths from $(0,0)$ to $(a,b)$, $a>b$

The question is to find number of lattice paths from $(0,0)$ to $(a,b)$, $a>b$, such that for any point $(x,y)$ along the path, we have that $x\geqslant y$

Ive been trying to find some way to split the problem into 2 parts. The closest Ive gotten is:

$$\text{Number of valid paths to } (a,b) = \left\{ \text{Number of valid paths from (0,0) to the line} (b,k), 0 \leqslant k \leqslant b \right\} + \left\{ \text{All paths from the line (b,k) to the point} (a,b) \right\}$$

The problem I am experiencing is that I can find no way to formulate this in a way such that over-counting of # of paths is avoided!

• Wow sorry and thank you for the fix; I meant $a>b$ and have corrected it – HoopaU Dec 10 '15 at 18:13
• No problem; I just fixed it in the title as well. – Brian M. Scott Dec 10 '15 at 18:13
• Are you allowing only steps up and steps to the right? – Brian M. Scott Dec 10 '15 at 18:14
• Yes only steps right and upwards (monotonic?) – HoopaU Dec 10 '15 at 20:26
• – ckoe Dec 11 '15 at 7:48

This is the same as the number of Dyck paths from $\langle 0,0\rangle$ to $\langle a+b,a-b\rangle$, i.e., lattice paths using $a$ up-steps $\langle 1,1\rangle$ and $b$ down-steps $\langle 1,-1\rangle$ that never drop below the $x$-axis. (A Dyck up-step corresponds to a step to the right in your setting, and a Dyck down-step to a step up.) In what follows path means any lattice path using only these up-steps and down-steps.
There are $\binom{a+b}a$ paths from $\langle 0,0\rangle$ to $\langle a+b,a-b\rangle$. If a path drops below the $x$-axis, it hits $\langle k,-1\rangle$ at some least $k>0$; reflect the part of the path to the right of this point in the line $y=-1$. Say that at $\langle k,-1\rangle$ there have been $r$ up-steps and $r+1$ down-steps; then the original path had $a-r$ up-steps and $b-r-1$ down-steps to the right of this point, so the reflected path has $a-r$ down-steps and $b-r-1$ up-steps to the right of this point. Thus, the reflected path has altogether $b-1$ up-steps and $a+1$ down-steps, so it terminates at $\langle a+b,b-a-2\rangle$. Conversely, any path of length $2n$ from $\langle 0,0\rangle$ to $\langle a+b,b-a-2\rangle$ must cross the line $y=-1$, and reflecting the part of it to the right of the first such crossing in the line $y=-1$ yields a path from $\langle 0,0\rangle$ to $\langle a+b,a-b\rangle$ that drops below the $x$-axis. There are $\binom{a+b}{a+1}$ paths of length $2n$ from $\langle 0,0\rangle$ to $\langle a+b,b-a-2\rangle$, so there are
\begin{align*} \binom{a+b}a-\binom{a+b}{a+1}&=\binom{a+b}a-\frac{b}{a+1}\binom{a+b}{a+1}\\ &=\frac{a+1-b}{a+1}\binom{a+b}a \end{align*}
paths from $\langle 0,0\rangle$ to $\langle a+b,a-b\rangle$ that do not drop below the $x$-axis.
As a quick and dirty partial check, note that if $a=b$, this reduce to $\frac1{a+1}\binom{2a}a$, the $a$-th Catalan number, as of course it should, and if $b=0$, it’s $1$, again as it should be.