Uogólnienie liczb katalońskich

Question

Pozwolić $n$być nieujemną liczbą całkowitą. Powszechnie wiadomo, że liczba ścieżek kratowych z$(0, 0)$ do $(n, n)$ ze stopniami $(0, 1)$ i $(1, 0)$ które nigdy nie wznoszą się ponad linię $y=x$ podaje numer kataloński $C_n$. W literaturze jest wiele uogólnień liczb katalońskich; jednak mam inne podejście do tych liczb, o których nie mogłem znaleźć żadnych znanych wyników.

Pytanie: Niech$a$ i $b$być nieujemnymi liczbami całkowitymi. Jaka jest liczba ścieżek kratowych z$(0, 0)$ do $(a, b)$ ze stopniami $(0, 1)$ i $(1, 0)$ które nigdy nie wznoszą się ponad linię $bx-ay=0$?

Pozwolić $C(a, b)$być funkcją o wartościach całkowitych, która zlicza liczbę takich ścieżek sieci. Jest jasne, że$$ C(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n} $$ dla każdej nieujemnej liczby całkowitej $n$. My też to wiemy$C(a,b)=C(b,a)$, które można uzyskać, ustawiając bijekcję między dwoma zestawami takich ścieżek za pomocą odzwierciedlania ścieżek w poprzek linii $y=x$, więc możemy wziąć $a≤b$ bez straty ogólności.

W przypadku $a \mid b$, istnieje dobrze znane rozwiązanie problemu omawianego przez Hilton i Pedersen , Sands i być może wielu innych:

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

Poza tym istnieje potężne narzędzie do wyliczania zwane The Cycle Lemma (patrz Dvoretzky i Motzkin ), które może być użyte do udowodnienia wyżej wymienionych równań. Ponadto możliwe jest rozwiązanie problemu dzięki lematowi cyklu kiedy$a$ i $b$ to liczby całkowite względnie pierwsze:

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

Niestety, żadne z moich ustaleń nie okazało się przydatne w znalezieniu ogólnego rozwiązania problemu. Czy istnieją jakieś dokumenty lub znane wyniki, które rzucają trochę światła na to pytanie? Jeśli nie, w jaki sposób możemy osiągnąć wyraźną formułę$C(a,b)$?

Answer 1

W przypadku nieliniowym odpowiedź jest dużo bardziej skomplikowana. Zobacz „Rational Dyck Paths in the Non Relative Prime Case” autorstwa Gorsky'ego, Mazina i Vazirani. Wyjaśniają, że to wynik Bizleya$$ \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) $$ na względnie pierwsze $a, b$, co wydaje się najlepsze, jakie można zrobić.

Artykuł Bizleya to: https://doi.org/10.1017/S002026810005424X.