P-рекурсивное уравнение

Дополнительная информация: голономная функция.

В математике P-рекурсивное уравнение — это линейное уравнение последовательностей , в котором последовательности коэффициентов могут быть представлены в виде полиномов . P-рекурсивные уравнения — это линейные рекуррентные уравнения (или линейные рекуррентные соотношения или линейные разностные уравнения) с полиномиальными коэффициентами. Эти уравнения играют важную роль в различных областях математики, в частности в комбинаторике . Последовательности, являющиеся решениями этих уравнений, называются голономными , P-рекурсивными или D-конечными.

В конце 1980-х годов были разработаны первые алгоритмы для поиска решений этих уравнений. Сергей А. Абрамов, Марко Петковшек и Марк ван Хой описали алгоритмы поиска полиномиальных, рациональных, гипергеометрических и даламберовых решений.

Определение

Позволять ${\textstyle \mathbb {K} }$ быть полем нулевой характеристики (например, ${\textstyle \mathbb {K} =\mathbb {Q} }$), ${\textstyle p_{k}(n)\in \mathbb {K} [n]}$ полиномы для ${\textstyle k=0,\dots ,r}$, ${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$ последовательность и ${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$ неизвестная последовательность. Уравнение $$\sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)$$называется линейным рекуррентным уравнением с полиномиальными коэффициентами (все рекуррентные уравнения в этой статье имеют именно такой вид). Если ${\textstyle p_{0}}$ и ${\textstyle p_{r}}$ оба ненулевые, то ${\textstyle r}$ называется порядком уравнения. Если ${\textstyle f}$ равно нулю, уравнение называется однородным, в противном случае оно называется неоднородным.

Это также можно записать как ${\textstyle Ly=f}$ где ${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$ — линейный рекуррентный оператор с полиномиальными коэффициентами и ${\textstyle N}$ является оператором сдвига, т.е. ${\textstyle N\,y(n)=y(n+1)}$.

Решения закрытой формы

Позволять ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ или эквивалентно ${\textstyle Ly=f}$ — рекуррентное уравнение с полиномиальными коэффициентами. Существует несколько алгоритмов, вычисляющих решения этого уравнения. Эти алгоритмы могут вычислять полиномиальные, рациональные, гипергеометрические и даламберовские решения. Решение однородного уравнения задается ядром линейного рекуррентного оператора: ${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$. Как подпространство пространства последовательностей это ядро ​​имеет базис . Позволять ${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$ быть основой ${\textstyle \ker L}$, то формальная сумма ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$ для произвольных констант ${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$ называется общим решением однородной задачи ${\textstyle Ly=0}$. Если ${\textstyle {\tilde {y}}}$ является частным решением ${\textstyle Ly=f}$, то есть ${\textstyle L{\tilde {y}}=f}$, затем ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$ также является решением неоднородной задачи и называется общим решением неоднородной задачи.

Полиномиальные решения

Основная статья: Полиномиальные решения P-рекурсивных уравнений

В конце 1980-х годов Сергей Абрамов описал алгоритм, который находит общее полиномиальное решение рекуррентного уравнения, т.е. ${\textstyle y(n)\in \mathbb {K} [n]}$, с полиномиальной правой частью ${\textstyle f(n)\in \mathbb {K} [n]}$. Он (а несколько лет спустя Марко Петковшек ) дал оценку степени полиномиальных решений. Таким образом, задачу можно просто решить, рассматривая систему линейных уравнений . В 1995 году Абрамов, Бронштейн и Петковшек показали, что полиномиальный случай может быть решен более эффективно, если рассматривать решение рекуррентного уравнения степенным рядом в определенном степенном базисе (т.е. не в обычном базисе). ${\textstyle (x^{n})_{n\in \mathbb {N} }}$).

Другие алгоритмы поиска более общих решений (например, рациональных или гипергеометрических решений) также основаны на алгоритмах вычисления полиномиальных решений.

Рациональные решения

Main article: Abramov's algorithm

В 1989 году Сергей Абрамов показал, что общее рациональное решение, т.е. ${\textstyle y(n)\in \mathbb {K} (n)}$, с полиномиальной правой частью ${\textstyle f(n)\in \mathbb {K} [n]}$, можно найти, используя понятие универсального знаменателя. Универсальный знаменатель – это многочлен ${\textstyle u}$ такой, что знаменатель каждого рационального решения делит ${\textstyle u}$. Абрамов показал, как этот универсальный знаменатель можно вычислить, используя только первый и последний полином-коэффициент. ${\textstyle p_{0}}$ и ${\textstyle p_{r}}$. Подставив этим универсальным знаменателем неизвестный знаменатель $y$ все рациональные решения можно найти путем вычисления всех полиномиальных решений преобразованного уравнения.

Гипергеометрическое решение

Основная статья: алгоритм Петковшека

Последовательность ${\textstyle y(n)}$ называется гипергеометрическим, если отношение двух последовательных членов является рациональной функцией в $n$, то есть ${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$. Это так тогда и только тогда, когда последовательность является решением рекуррентного уравнения первого порядка с полиномиальными коэффициентами. Множество гипергеометрических последовательностей не является подпространством пространства последовательностей, поскольку оно не замкнуто относительно сложения.

В 1992 году Марко Петковшек предложил алгоритм получения общего гипергеометрического решения рекуррентного уравнения, в котором правая часть $f$ есть сумма гипергеометрических последовательностей. Алгоритм использует нормальную форму рациональной функции Госпера-Петковшека. При таком конкретном представлении снова достаточно рассмотреть полиномиальные решения преобразованного уравнения.

Другой, более эффективный подход принадлежит Марку ван Хойю. Учитывая корни первого и последнего коэффициентного многочлена ${\textstyle p_{0}}$ и ${\textstyle p_{r}}$ – называемые сингулярностями – можно построить решение шаг за шагом, используя тот факт, что каждая гипергеометрическая последовательность ${\textstyle y(n)}$ имеет представление вида $$y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}$$для некоторых ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$ с ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ для ${\textstyle i\neq j}$ и ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$. Здесь ${\textstyle \Gamma (n)}$ обозначает гамма-функцию и ${\textstyle {\overline {\mathbb {K} }}}$ алгебраическое замыкание поля ${\textstyle \mathbb {K} }$. Тогда ${\textstyle \xi _{1},\dots ,\xi _{s}}$ должны быть сингулярностями уравнения (т.е. корнями ${\textstyle p_{0}}$ или ${\textstyle p_{r}}$). Кроме того, можно вычислить границы показателей степени ${\textstyle e_{i}}$. Для фиксированных значений ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ можно сделать анзац, который дает кандидатов на ${\textstyle z}$. Для конкретного ${\textstyle z}$ можно снова сделать анзац, чтобы получить рациональную функцию ${\textstyle r(n)}$ по алгоритму Абрамова. Учитывая все возможности, получаем общее решение рекуррентного уравнения.

Даламберовские решения

Последовательность $y$ называется даламберовским, если ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ для некоторых гипергеометрических последовательностей ${\textstyle h_{1},\dots ,h_{k}}$ и ${\textstyle y=\sum x}$ означает, что ${\textstyle \Delta y=x}$ где ${\textstyle \Delta }$ обозначает разностный оператор, т.е. ${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$. Это так тогда и только тогда, когда существуют линейные рекуррентные операторы первого порядка. ${\textstyle L_{1},\dots ,L_{k}}$ с рациональными коэффициентами такими, что ${\textstyle L_{k}\cdots L_{1}y=0}$.

1994 Абрамов и Петковшек описали алгоритм, который вычисляет общее даламберовское решение рекуррентного уравнения. Этот алгоритм вычисляет гипергеометрические решения и рекурсивно снижает порядок рекуррентного уравнения.

Примеры

Знаковые матрицы перестановок

Количество матриц перестановок со знаком размера $n\times n$ можно описать последовательностью ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$. Матрица перестановок со знаком — это квадратная матрица, которая имеет ровно один ненулевой элемент в каждой строке и в каждом столбце. Ненулевые записи могут быть ${\textstyle \pm 1}$. Последовательность определяется линейным рекуррентным уравнением с полиномиальными коэффициентами $$y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)$$и начальные значения ${\textstyle y(0)=1,y(1)=2}$. Применяя алгоритм поиска гипергеометрических решений, можно найти общее гипергеометрическое решение. $$y(n)=c\,2^{n}n!$$для некоторой константы ${\textstyle c}$. Также учитывая начальные значения, последовательность ${\textstyle y(n)=2^{n}n!}$ описывает количество матриц перестановок со знаком.

Инволюции

Число инволюций ${\textstyle y(n)}$ из набора с ${\textstyle n}$ элементов задается рекуррентным уравнением $$y(n)=(n-1)\,y(n-2)+y(n-1).$$Применяя, например, алгоритм Петковшека, можно увидеть, что для этого рекуррентного уравнения не существует полиномиального, рационального или гипергеометрического решения.

Приложения

Функция ${\textstyle F(n,k)}$ называется гипергеометрическим, если ${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$ где ${\textstyle \mathbb {K} (n,k)}$ обозначает рациональные функции в ${\textstyle n}$ и ${\textstyle k}$. Гипергеометрическая сумма — это конечная сумма вида ${\textstyle f(n)=\sum _{k}F(n,k)}$ где ${\textstyle F(n,k)}$ является гипергеометрическим. Творческий алгоритм телескопирования Зейлбергера может преобразовать такую ​​гипергеометрическую сумму в рекуррентное уравнение с полиномиальными коэффициентами. Затем это уравнение можно решить, чтобы получить, например, линейную комбинацию гипергеометрических решений, которая называется решением в замкнутой форме ${\textstyle f}$.