Число ломаных длины n в коридоре [0,m]

[alhimikoff]

Здравствуйте.

Что известно про такую задачу -
Сколько ломаных с шагами $(1,1)$ и $(1,-1)$ идёт из точки $(0,0)$ в точку $(0,2n)$ в коридоре $[0,m]$ ?

По идее должно быть что-то похожее на числа Каталана, т.к. число Каталана $C_n$ - это число ломаных с шагами $(1,1)$ и $(1,-1)$, идущих из точки $(0,0)$ в точку $(0,2n)$, не опускающихся ниже оси Ox.

Обозначим искомое число $C_{n,m}$.

Пока только нашёл рекуррентное соотношение от 2 переменных:

$$C_{n+1,m}=C_{n,m}C_{0,m-1}+C_{n-1,m}C_{1,m-1}+...+C_{0,m}C_{n,m-1}$$

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[arseniiv]

Т. е. последовательность чисел $i\mapsto C_{i, m}$ — это (кроме первого элемента $1$) сдвинутая на 1 свёртка себя с $i\mapsto C_{i, m-1}$. Тогда если $A_m$ — производящая функция $i\mapsto C_{i, m}$, то $A_m(z) = z A_m(z) A_{m-1}(z) + 1$, и $A_m = (1 - zA_{m-1})^{-1}$, плюс $A_0 = 1$. Может, это вам что-то даст…

[alhimikoff]

То есть такая цепная дробь получается для $A_m$ ?

$$A_m(z)=\frac{1}{1-\frac{z}{1-\frac{z}{1-\frac{z}{...}}}}$$

(m ступеней)

[arseniiv]

Ага.

[alhimikoff]

arseniiv в сообщении #1077229 писал(а):

$A_m = (1 - zA_{m-1})^{-1}$, плюс $A_0 = 1$

Вольфрам решает это РС, получается какая-то жуть с $\sqrt{1-4z}$:
http://www.wolframalpha.com/input/?i=f% ... 280%29%3D1
Коэффициент при $z^n$ оттуда определить не представляется возможным...
Здесь уже обсуждали эту задачу, для частных случаев решения правильные:
http://ru-math.livejournal.com/216034.html

[arseniiv]

(Кстати, если вам нужны $C_{m,n}$ в каком-то практическом контексте, то можно использовать динамическое программирование (хотя, наверно, кто-нибудь это уже сказал), рекуррентность-то вы давно нашли.)

[alhimikoff]

Да, написать программу большой проблемы нет.
Нашлась таки эта задача:
https://oeis.org/A080934
Частный случай $m=5$ https://oeis.org/A080937