MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams 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, 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 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.

share|cite|improve this question
It's a long time since I read it but if I remember correctly, I think you might find the following paper useful (unless you've already read it): Hilton, P., Pedersen, J., "Catalan numbers, their generalization, and their uses" Math. Intelligencer 13(2) (1991). (Incidentally Google seems to be able to find a version outside a paywall.) – Oliver Nash Jun 9 '13 at 22:17
up vote 7 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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