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 ] 

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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