The number of lattice paths below y=n/m x for gcd(m,n) = 1

Question

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams http://arxiv.org/abs/1305.7286 on rational Catalan combinatorics.

An important starting point of this paper is the fact that the number of lattice paths with steps $(1,0)$ and $(0,1)$ from the origin to $(m,n)$, where $gcd(m,n)=1$ weakly below the diagonal $y=\frac{n}{m} x$ equals $$ \frac{1}{m+n}\binom{m+n}{m}. $$

This can be proved (as done by Bizley, http://www.jstor.org/discover/10.2307/41139633?uid=3737528&uid=2&uid=4&sid=21102085756863) by considering all cyclic permutations of each path from the origin to $(m,n)$ and demonstrating that among these there is exactly one path below the diagonal.

I would like to know of any other proof of this fact, for example using generatingfunctionology.

One approach I looked at (from the paper by Gessel and Ree http://people.brandeis.edu/~gessel/homepage/papers/faber.pdf) extends the recurrence $B(m,n)=B(m,n-1)+B(m-1,n)$ to all of $\mathbb N^2$ and then uses suitable initial values $B(m,0)$ and $B(0,n)$ to obtain generating functions for paths below $y=\frac{1}{m} x$. But it seems that the initial values for the general case are unpleasant.

Answer 1

You can use the approach of my paper A factorization for formal Laurent series, Journal of Combinatorial Theory, Series A 28 (1980) 321-337. Although this problem is not considered in that paper, Theorem 4.1 and its proof give the following result: Let $m$ and $n$ be relative prime positive integers and let $p(k)$ be the number of paths from $(0,0)$ to $(km,kn)$ weakly below the diagonal $y=\frac{n}{m}x$. Expand $$\log\left(\frac{1}{1 -t^{n}x-t^{-m}y}\right)$$ as a power series in $x$ and $y$ and let $f$ be the constant term in $t$. Explicitly, we have $$f= \sum_{i=1}^\infty \frac{1}{(m+n)i} \binom{(m+n)i}{mi} x^{mi}y^{ni}.$$ Then $$\sum_{k=0}^\infty p(k) x^{mk}y^{nk} = e^f.$$ This is equivalent to Grossman's formula, which was proved by Bizley. In particular, $p(1) = \binom{m+n}{m}/(m+n)$. (Of course in the final result we could replace $x^my^n$ with a single variable.) The method of this paper can also be used to count paths that stay strictly below (or above) the line $y=\frac{n}{m}x$.