Intuitive Explanation for Number of Dyck Paths Never Going Above Diagonal of a Rectangle

Question

Suppose we have a an $a\times{}b$ rectangle whose bottom-left corner is at $(0,0)$ and whose upper-right corner is at $(b,a)$. Let $a$ and $b$ both be positive integers, and let $b\geq{}a$. If $a$ and $b$ are mutually prime then the number of Dyck paths inside the rectangle going from $(0,0)$ to $(b,a)$ which never go above the diagonal line between those two points is $\frac{1}{a+b}\binom{a+b}{a}$. Otherwise, if $b=ak$ for some positive integer $k$ the number of Dyck paths is $\frac{1}{b+1}\binom{a+b}{a}$. These formulas are very simple and it would seem there would be some straightforward combinatorial derivation of them, but if that is the case I haven't found one yet. I have tried applying the reflection strategy used to solve Bertrand's ballot theorem to this problem, with no success. Indeed, Bertrand's ballot theorem (with ties allowed) seems to be special case of this problem if $a=b=n$ (the probability of one candidate always being tied or ahead in the vote count is $\frac{1}{n+1}$ in that case, and the fraction of Dyck paths which never go above the diagonal from $(0,0)$ to $(n,n)$ is also $\frac{1}{n+1}\binom{2n}{n}\big/\binom{2n}{n}=\frac{1}{n+1}$). Does anybody know of any intuitive combinatorial, geometric, or other kinds of proofs for those two formulas?

Answer 1

I can explain the $\frac1{a+b}\binom{a+b}{b}$ formula for when $\gcd(a,b)=1$ combinatorially. The total number of paths from $(0,0)$ to $(b,a)$ is $\binom{a+b}{a}$, so it suffices to partition all of these paths into groups of size $a+b$ such that exactly one path in each group stays at or below the diagonal. The idea is to group each path with all of its cyclic rotations. Because $a$ and $b$ are coprime, all of these rotations will be distinct from one each other. Furthermore, there is exactly one rotation for which the path stays below $y=\tfrac{a}bx$. Namely, if you take any path, and you mark the lattice point on the path which attains the largest perpendicular distance above the diagonal $y=\tfrac ab x$, then you need to rotate so the path starts at the marked point for the rotated path to stay below the diagonal.

Here is an example when $a=2$ and $b=3$. There are $a+b=5$ ways to cyclically rotate any path. For the example path below and its four other rotations, I have marked the which attains the highest perpendicular distance with an asterisk.

         .
         |
   *--.--.   RURRU
   |
.--.

      .--.
      |
*--.--.      URRUR
|
.
         *
         |
      .--.   RRURU   (stays below diagonal)
      |
*--.--.

      *--.
      |
   .--.      RURUR
   |
.--.

   *--.--.
   |
.--.         URURR
|
.

For the $\frac1{1+b}\binom{a+b}{a} $ result in the case $b=ak$, several proofs are given in Four Proofs of the Ballot Theorem by Marc Renault, available online here. See the "Weak Ballot Problem, Catalan Numbers" section at the end.