Обобщение каталонских чисел
Позволять $n$быть неотрицательным целым числом. Как известно, количество решеточных путей из$(0, 0)$ к $(n, n)$ с шагами $(0, 1)$ и $(1, 0)$ которые никогда не поднимаются выше черты $y=x$ дается каталонским числом $C_n$. В литературе есть множество обобщений каталонских чисел; однако у меня другой подход к этим числам, по которым мне не удалось найти никаких известных результатов.
Вопрос: Пусть$a$ и $b$быть неотрицательными целыми числами. Сколько путей решетки от$(0, 0)$ к $(a, b)$ с шагами $(0, 1)$ и $(1, 0)$ которые никогда не поднимаются выше черты $bx-ay=0$?
Позволять $C(a, b)$- целочисленная функция, которая подсчитывает количество таких решетчатых путей. Ясно, что$$ C(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n} $$ для каждого неотрицательного целого числа $n$. Мы также знаем, что$C(a,b)=C(b,a)$, который может быть получен путем установки взаимно однозначного соответствия между двумя наборами таких путей посредством отражения путей через линию $y=x$, так что мы можем взять $a≤b$ не теряя общий смысл.
На случай, если $a \mid b$, есть хорошо известное решение проблемы, которое обсуждают Хилтон и Педерсен , Сэндс и, возможно, многие другие:
$$ C(a,ma) = \frac{1}{ma+1} \binom{a(m+1)}{a}. $$
Кроме того, существует мощный инструмент для перечисления под названием The Cycle Lemma (см. Дворецкий и Моцкин ), который можно использовать для доказательства упомянутых выше уравнений. Кроме того, можно решить проблему благодаря лемме о цикле, когда$a$ и $b$ взаимно простые целые числа:
$$ gcd(a,b)=1 \Rightarrow C(a,b) = \frac{1}{a+b} \binom{a+b}{a}. $$
К сожалению, ни один из моих выводов не оказался полезным для поиска общего решения проблемы. Существуют ли какие-либо существующие статьи или известные результаты, которые проливают свет на этот вопрос? Если нет, то как мы можем получить явную формулу$C(a,b)$?
Ответы
В случае непростого случая ответ намного сложнее. См. «Рациональные пути Дейка в случае не относительного простого числа» Горского, Мазина и Вазирани. Они объясняют, что именно благодаря Бизли$$ \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) $$ для совместной $a, b$, что кажется лучшим, что можно сделать.
Бумага Бизли: https://doi.org/10.1017/S002026810005424X.