Une généralisation des nombres catalans

Question

Laisser $n$être un entier non négatif. Il est bien connu que le nombre de chemins de réseau de$(0, 0)$ à $(n, n)$ avec marches $(0, 1)$ et $(1, 0)$ qui ne dépassent jamais la ligne $y=x$ est donné par le nombre catalan $C_n$. Il y a beaucoup de généralisations des nombres catalans dans la littérature; cependant, j'ai une approche différente de ces chiffres sur laquelle je n'ai pas réussi à trouver des résultats connus.

Question: Laissez$a$ et $b$être des entiers non négatifs. Quel est le nombre de chemins de treillis à partir de$(0, 0)$ à $(a, b)$ avec marches $(0, 1)$ et $(1, 0)$ qui ne dépassent jamais la ligne $bx-ay=0$?

Laisser $C(a, b)$être la fonction à valeur entière qui compte le nombre de ces chemins de réseau. Il est clair que$$ C(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n} $$ pour tout entier non négatif $n$. Nous savons aussi que$C(a,b)=C(b,a)$, qui peut être obtenue en établissant une bijection entre les deux ensembles de tels chemins en réfléchissant les chemins à travers la ligne $y=x$, afin que nous puissions prendre $a≤b$ sans perte de généralité.

Dans le cas de $a \mid b$, il existe une solution bien connue au problème discuté par Hilton et Pedersen , Sands et peut-être bien d'autres:

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

En outre, il existe un puissant outil d'énumération appelé The Cycle Lemma (voir Dvoretzky et Motzkin ) qui peut être utilisé pour prouver les équations mentionnées ci-dessus. De plus, il est possible de résoudre le problème grâce au lemme de cycle lorsque$a$ et $b$ sont des entiers premiers:

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

Malheureusement, aucune de mes découvertes n'a pu s'avérer utile pour trouver une solution générale au problème. Existe-t-il des articles ou des résultats connus qui éclairent cette question? Sinon, comment pouvons-nous parvenir à une formule explicite de$C(a,b)$?

Answer 1

Dans le cas des non-coprimes, la réponse est beaucoup plus compliquée. Voir "Rational Dyck Paths in the Non Relately Prime Case" de Gorsky, Mazin et Vazirani. Ils expliquent que c'est à cause de Bizley que$$ \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) $$ pour coprime $a, b$, ce qui semble être le mieux que l'on puisse faire.

Le papier de Bizley est: https://doi.org/10.1017/S002026810005424X.