4
$\begingroup$

Let $n$ be a nonnegative integer. It is well-known that the number of lattice paths from $(0, 0)$ to $(n, n)$ with steps $(0, 1)$ and $(1, 0)$ that are never rising above the line $y=x$ is given by the Catalan number $C_n$. There are lots of generalisations of Catalan numbers in the literature; however, I have a different approach to these numbers which I could not manage to find any known results about.

Question: Let $a$ and $b$ be nonnegative integers. What is the number of lattice paths from $(0, 0)$ to $(a, b)$ with steps $(0, 1)$ and $(1, 0)$ that are never rising above the line $bx-ay=0$?

Let $C(a, b)$ be the integer valued function that counts the number of such lattice paths. It is clear that $$ C(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n} $$ for every nonnegative integer $n$. We also know that $C(a,b)=C(b,a)$, which can be obtained by setting up a bijection between the two sets of such paths by means of reflecting the paths across the line $y=x$, so we can take $a≤b$ without loss of generality.

In the case of $a \mid b$, there is a well-known solution to the problem that is discussed by Hilton and Pedersen, Sands and possibly many others:

$$ C(a,ma) = \frac{1}{ma+1} \binom{a(m+1)}{a}. $$

Besides, there is a powerful enumeration tool called The Cycle Lemma (see Dvoretzky and Motzkin) which can be used to prove the equations mentioned above. Furthermore, it is possible to solve the problem thanks to the Cycle Lemma when $a$ and $b$ are coprime integers:

$$ gcd⁡(a,b)=1 \Rightarrow C(a,b) = \frac{1}{a+b} \binom{a+b}{a}. $$

Unfortunately, none of my findings could prove itself useful in finding a general solution to the problem. Are there any existing papers or known results that shed some light on this question? If not, how can we achieve an explicit formula of $C(a,b)$?

$\endgroup$
3
  • 1
    $\begingroup$ You might want to check the natural refinements of the Catalan numbers oeis.org/A125181 and the signed version oeis.org/A134264. $\endgroup$ Commented Sep 22, 2020 at 17:13
  • 1
    $\begingroup$ The $C(a,ma)=C(a,ma+1)$ thing seems kinda special to me, and not representative of the general one runs into in the non-coprime case (btw, these are often called 'Fuss-Catalan numbers') . $\endgroup$ Commented Sep 22, 2020 at 17:19
  • 1
    $\begingroup$ The sequences of Fuss-Catalan #s are mentioned in A134264 with a link to the first sequence, oeis.org/A001764. A relation to Dyck paths falls out of the connections among the NC-partitions, Dyck paths, and compositional inversion. $\endgroup$ Commented Sep 22, 2020 at 23:59

1 Answer 1

4
$\begingroup$

In the non-coprime case the answer is much more complicated. See "Rational Dyck Paths in the Non Relatively Prime Case" by Gorsky, Mazin, and Vazirani. They explain that it is a result of Bizley that $$ \sum_{d\geq 0} C(da,db)z^d = \mathrm{exp}\left(\sum_{d\geq 1} \frac{1}{d(a+b)}\binom{d(a+b)}{da}z^d \right) $$ for coprime $a, b$, which is the best it seems one can do.

The paper of Bizley is: https://doi.org/10.1017/S002026810005424X.

$\endgroup$
4
  • $\begingroup$ Interestingly, the Gordita et. al. paper is from 2017 and the paper of Bizley is from 1954. $\endgroup$ Commented Sep 22, 2020 at 22:54
  • $\begingroup$ Gordita!?! More seriously, "rational Catalan combinatorics" is a hot topic of late... $\endgroup$ Commented Sep 22, 2020 at 22:59
  • 1
    $\begingroup$ Gorsky...@#$#^ autocorrect. It was the 1954 that I thought was interesting. $\endgroup$ Commented Sep 23, 2020 at 7:05
  • $\begingroup$ The argument from that 1954 is not too difficult; but note that $\frac{1}{d(a+b)}\binom{d(a+b)}{da}$ are not always integers (e.g. $\frac{1}{2(2+5)}\binom{2(2+5)}{2*2}$) so it's a little more complicated than a straightforward exponential generating function argument, which is what I initially thought it was. $\endgroup$ Commented Sep 23, 2020 at 17:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .