2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Паттерн в рекурсии с многочленами
Сообщение23.09.2024, 17:56 
Аватара пользователя


22/11/13
02/04/25
549
Пусть $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)$, так и для многочленов)?

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение23.09.2024, 18:03 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение23.09.2024, 18:18 
Аватара пользователя


22/11/13
02/04/25
549
dgwuqtj, спасибо, хорошая идея. Так действительно выглядит убого. В ближайшее время я этим займусь.

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение23.09.2024, 20:12 
Аватара пользователя


22/11/13
02/04/25
549
Готово! Скопировано с программы на 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)!}).
$$
Возможно что-то еще можно упростить, не так ли?

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение23.09.2024, 22:32 
Заслуженный участник


07/08/23
1055
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*}

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 10:08 
Аватара пользователя


22/11/13
02/04/25
549
dgwuqtj, все проверил, работает. Великолепное упрощение! Спасибо вам огромное!

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

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 12:42 
Заслуженный участник


07/08/23
1055
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)$.

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 14:01 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 14:38 
Заслуженный участник


07/08/23
1055
Конечно, сократится.

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 16:45 
Аватара пользователя


22/11/13
02/04/25
549
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)$? И если можно, то что для этого требуется?

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 17:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 17:46 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Паттерн в рекурсии с многочленами
Сообщение24.09.2024, 17:55 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group