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!

  • $\begingroup$ Wow sorry and thank you for the fix; I meant $a>b$ and have corrected it $\endgroup$ – HoopaU Dec 10 '15 at 18:13
  • $\begingroup$ No problem; I just fixed it in the title as well. $\endgroup$ – Brian M. Scott Dec 10 '15 at 18:13
  • $\begingroup$ Are you allowing only steps up and steps to the right? $\endgroup$ – Brian M. Scott Dec 10 '15 at 18:14
  • $\begingroup$ Yes only steps right and upwards (monotonic?) $\endgroup$ – HoopaU Dec 10 '15 at 20:26
  • $\begingroup$ See this: nptel.ac.in/courses/111104026/lecture12.pdf $\endgroup$ – 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}\\ &=\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.