Паттерн в рекурсии с многочленами

[kthxbye]

Пусть $a(n,m)$ - семейство целочисленных последовательностей, таких, что

$$ a(n,m) = \sum\limits_{k=1}^{n} \binom{n(m+1)-mk-1}{n-k}\frac{k}{nm-(m-1)k}, \\ a(0,m) = 1. $$

Первые случаи подробно представлены в A376447.

Заметив в последовательности A130458 рекурсию с многочленами, я заинтересовался общим случаем. По всей видимости, для любого натурального $m$ существуют многочлены $P_m(n)$ и $Q_m(n)$, такие, что

$$ P_m(n)a(n, m+2) = Q_m(n)a(n-1, m+2) + P_m(n)a(n-m-1, m+2) $$

$$ - (P_m(n) + Q_m(n))a(n-m-2, m+2) + Q_m(n)a(n-m-3, m+2). $$

Благодаря счастливому случаю мне удалось обнаружить замкнутые формы для вышеупомянутых многочленов. Вот они:

$$ P_m(n) = \prod\limits_{i=0}^{m+1}(n(m+2) - i - m - 1)((m+2)\prod\limits_{j=1}^{(m+1)^2} (n(m+2)-j-2(m+1)) $$

$$ +\sum\limits_{k=2}^{m+2} (m-k+3)(m+3)^{k-1}\prod\limits_{s=1}^{(m+1)(m-k+2)}(n(m+2)-s-2(m+1))\frac{\prod\limits_{t=(m+2)(m-k+4)+2}^{(m+2)^2+m+3}(n(m+3)-t)}{\prod\limits_{r=m-k+5}^{m+3} ((m+3)(n-r+1))}). $$

$$ Q_m(n) = (m+3)(n(m+3) - m^2 - 5m - 7)\prod\limits_{i=0}^{m}(n(m+3) - i - m^2 - 4m - 5)((m+2)\prod\limits_{j=1}^{(m+1)^2} (n(m+2)-j-m) $$

$$ + \sum\limits_{k=2}^{m+2} (m-k+3)(m+3)^{k-1}\prod\limits_{s=1}^{(m+1)(m-k+2)}(n(m+2)-s-m)\frac{\prod\limits_{t=(m+2)(m-k+3)+1}^{(m+2)^2}(n(m+3)-t)}{\prod\limits_{r=m-k+5}^{m+3} ((m+3)(n-r+2))}). $$

Вы можете проверить их для малых $m$ с помощью ссылок на частные случаи в A376447.

Меня интересует следующий вопрос: можно ли доказать справедливость рекурсии, имея замкнутые формы (как для $a(n,m)$, так и для многочленов)?

[dgwuqtj]

А можно это по-человечески переписать, без произведений, в терминах факториалов или биномиальных коэффициентов?

[kthxbye]

dgwuqtj, спасибо, хорошая идея. Так действительно выглядит убого. В ближайшее время я этим займусь.

[kthxbye]

Готово! Скопировано с программы на PARI/GP, где значения прошли предварительную проверку. Но когда мы работает с факториалами, появляется ограничение $n>(m+2)$.

$$ P_m(n) = (n(m+2)-m-1)!(\frac{m+2}{((m+2)(n-m-2))!} $$

$$ + \sum\limits_{k=2}^{m+2} \frac{(m-k+3)(n(m+3) - (m+2)(m-k+4) - 2)!(n - m - 3)!}{(n(m+2) - 2m - 3 - (m+1)(m-k+2))!(n(m+3) - (m+2)(m+3) - 2)!(n-m+k-4)!}). $$

$$ Q_m(n) = \frac{(m+3)(n(m+3)-m^2-5m-7)(n(m+3)-m^2-4m-5)!}{((m+3)(n-m-2))!}(\frac{(m+2)(n(m+2)-m-1)!}{(n(m+2)-m^2-3m-2)!} $$

$$ + \sum\limits_{k=2}^{m+2} \frac{(m-k+3)(n(m+2)-m-1)!(n(m+3)-(m+2)(m-k+3)-1)!(n-m-2)!}{(n(m+2)-(m+1)(m-k+3))!(n(m+3)-(m+2)^2-1)!(n-m+k-3)!}). $$

Возможно что-то еще можно упростить, не так ли?

[dgwuqtj]

kthxbye в сообщении #1655782 писал(а):

Но когда мы работает с факториалами, появляется ограничение $n>(m+2)$.

Так и без факториалов есть ограничение из-за знаменателей. Давайте в формуле для $P_m(n)$ заменим индекс суммирования $n - m + k + 4 = s$, тогда отдельное слагаемое соответствует $s = n - m - 3$ и получается
\begin{align*} P_m(n) = \frac{ (n m + 2 n - m - 1)!\, (n - m - 3)! }{ (n m + 3 n - m^2 - 5 m - 8)! } \sum_{s = n - m - 3}^{n - 2} \frac{(n - s - 1)\, (n + (m + 2) s - 2)! }{ (n + (m + 1) s - 1)!\, s! }. \end{align*}
Аналогично, взяв $n - m + k - 3 = t$, получается
\begin{align*} Q_m(n) = \frac{ (n m + 2 n - m - 1)!\, (n - m - 3)! }{ (n m + 3 n - m^2 - 5 m - 8)! } \sum_{t = n - m - 2}^{n - 1} \frac{ (n - t)\, (n + (m + 2) t - 1)! }{ (n + (m + 1) t)!\, t! }. \end{align*}

Ну и, конечно же, при $n > 0$ у вас
\begin{align*} a(n, m) = \sum_{k = 0}^{n - 1} \frac{ (n + m k - 1)!\, (n - k) }{ k!\, (n + (m - 1) k)! }. \end{align*}

[kthxbye]

dgwuqtj, все проверил, работает. Великолепное упрощение! Спасибо вам огромное!

Теперь по поводу моего основного вопроса. Насколько на ваш взгляд очевидна данная рекурсия?

[dgwuqtj]

kthxbye в сообщении #1655864 писал(а):

Насколько на ваш взгляд очевидна данная рекурсия?

Мне не очевидна, но наверняка можно посчитать и проверить. Введём обозначение

$$ R_m(n) = \sum_{t = n - m}^{n - 1} \frac{ (n - t)\, (n + m t - 1)! }{ (n + (m - 1) t)!\, t! }, $$

тогда $P_m(n) = U(m, n) R_{m + 2}(n - 1)$ и $Q_m(n) = U(m, n) R_{m + 2}(n)$ для общего сомножителя $U(m, n)$. Рекуррентное соотношение можно сократить на $U(m, n)$ и уменьшить $m$ на 2, получится

$$ R_m(n - 1)\, b(n, m) = R_m(n)\, b(n - 1, m) $$

где $b(n, m) = a(n, m) + a(n - m, m) - a(n - m + 1, m)$. Если теперь упростить $b(n, m)$, когда для его слагаемых работает общая формула (крайние случай пока не рассматриваем), получится как раз $b(n, m) = R_m(n)$.

[kthxbye]

dgwuqtj, а можно $b(n,m)$, выраженное через $a(n,m)$, подставить вместо $R_m(n)$ в основную рекурсивную формулу? Там все сократится или же мы откроем новую рекурсию?

[dgwuqtj]

Конечно, сократится.

[kthxbye]

dgwuqtj, а как вы получили $b(n,m)$, выраженное через $a(n,m)$? Какие-то манипуляции с суммой для $R_m(n)$? И что это за крайние случаи, которые мы пока не рассматриваем? Зачем вообще нужна вот эта штука:

dgwuqtj в сообщении #1655888 писал(а):

$$ R_m(n - 1)\, b(n, m) = R_m(n)\, b(n - 1, m) $$

?

Разве нельзя сразу сказать, что $b(n,m)=R_m(n)$? И если можно, то что для этого требуется?

[dgwuqtj]

kthxbye
Так вы сами возьмите тождество, которое надо доказать, и выразите в нём $P_m(n)$ и $Q_m(n)$ через $R_m(n)$. Крайние случае — это формула $a(0, m) = 1$, которая не является частным случаем общей формулы для $a(n, m)$ (работающей при $n > 0$).

[kthxbye]

dgwuqtj, понятно, спасибо. Т.е. теперь вся загвоздка состоит в том, чтобы показать, что $b(n,m) = R_m(n)$, верно?

[dgwuqtj]

Это простые манипуляции с суммами. Левая часть раскрывается по определению в три суммы, слагаемые из сумм для $a(n - m, m)$ и $a(n - m + 1, m)$ можно попарно вычесть и упростить. Получится начальный кусок суммы для $a(n, m)$ со знаком минус, без которого как раз остаётся $R_m(n)$.