Что-то вроде обобщения одной из интерпретаций чисел Каталана

[Erken1]

Дан прямоугольник, с целочисленными сторонами равными $m,n\in\mathbb{N}$, разделённый на единичные квадраты.
Требуется найти явную формулу, $f_{m,n}$,находящию количество различных путей, из левого-нижнего угла до верхнего-правого, делая следующие ходы $\rightarrow,\uparrow,\nearrow$.
Найти значение производящей функции:
$1+\sum_{n=1}^{\infty}f_{n,n}x^{n}$

[VAL]

Erken1 писал(а):

Дан прямоугольник, с целочисленными сторонами равными $m,n\in\mathbb{N}$, разделённый на единичные квадраты.
Требуется найти явную формулу, $f_{m,n}$,находящию количество различных путей, из левого-нижнего угла до верхнего-правого, делая следующие ходы $\rightarrow,\uparrow,\nearrow$.

Пусть $n\ge m$. Тогда

$$f(m,n)=\sum_{i=0}^{m-1}C_{m+n-2-i}^iC_{m+n-2-2i}^{m-1-i}$$

.

[Erken1]

Спасибо.Можно ли увидеть обоснование данной формулы, и насколько я знаю, существует гораздо более приемлемая формула.

[VAL]

Erken1 писал(а):

Спасибо.Можно ли увидеть обоснование данной формулы,

Я рассуждал "в лоб". Суммируем число маршрутов: не содержащих ходов по диагонали, содержащих 1 диагональный ход, ... , m-1 диагональный ход.
Если, например, диагональных ходов k. то общее число ходов - n+m-2-k. Из них надо выбрать k диагональных, а из оставшихся - m-1-k вертикальных (считаем, что m - высота прямоугольника).

Цитата:

и насколько я знаю, существует гораздо более приемлемая формула.

Возможно. Я упрощать не пытался.

[Erken1]

Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

[maxal]

Erken1 писал(а):

Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Тогда уж

$$\sum_{k=0}^{\infty} (x+y+xy)^k = \frac{1}{1-x-y-xy}$$

[Erken1]

maxal писал(а):

Erken1 писал(а):

Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Тогда уж

$$\sum_{k=0}^{\infty} (x+y+xy)^k = \frac{1}{1-x-y-xy}$$

Это я к тому, что задача уже решена...

[VAL]

Erken1 писал(а):

Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Они какие-то бесконечные получаются...
Вот если брать коэффициенты при $x^my^n$ в сумме $\sum_{k=0}^{\infty}(x+y+xy)^{k}$, тогда они свопадут с моими, после очевидных поправок, связанных с тем, что я считал маршруты, пролегающие по клеткам, а не по узлам разбиения.

[Erken1]

извиняюсь...конечно же, сумма должна выглядеть как у вас.
Просто опечатка.