6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Oliver Nash Jun 9 '13 at 22:17
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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