11
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ This issue is very well treated here $\endgroup$
    – Jean Marie
    May 19 at 13:09
  • $\begingroup$ I don't understand why you introduce the variable $k$ without using it. $\endgroup$
    – Vincent
    May 20 at 20:46

1 Answer 1

15
$\begingroup$

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.

$\endgroup$

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.