Производящая функция

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Март 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Эта статья может быть слишком длинной для чтения и удобной навигации . Размер читаемой прозы - 76 килобайт. Пожалуйста, рассмотрите возможность разделения контента на подстатьи, сжатия или добавления подзаголовков . Пожалуйста, обсудите этот вопрос на странице обсуждения статьи . ( Март 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , А функция генерирования представляет собой способ , кодирующие бесконечную последовательность чисел ( _п ) путем обработки их в качестве коэффициентов одного формальных степенных рядов . Этот ряд называется производящей функцией последовательности. В отличие от обычного ряда, формальный степенной ряд не требуется сходиться : на самом деле производящая функция фактически не рассматривается как функция , а «переменная» остается неопределенной . Производящие функции были впервые введены Абрахамом де Муавром.в 1730 г., чтобы решить общую линейную проблему повторения. ^[1] Можно обобщить на формальные степенные ряды более чем одного неопределенного числа, чтобы закодировать информацию о бесконечных многомерных массивах чисел.

Существуют различные типов генерации функций, включая обычные производящие функции , экспоненциальные производящие функции , серию Ламберта , серию Bell , и ряд Дирихля ; определения и примеры приведены ниже. Каждая последовательность в принципе имеет производящую функцию каждого типа (за исключением того, что ряды Ламберта и Дирихле требуют, чтобы индексы начинались с 1, а не с 0), но легкость, с которой они могут быть обработаны, может значительно различаться. Конкретная производящая функция, если таковая имеется, которая наиболее полезна в данном контексте, будет зависеть от характера последовательности и деталей решаемой проблемы.

Производящие функции часто выражаются в замкнутой форме (а не в виде ряда) некоторым выражением, включающим операции, определенные для формальных рядов. Эти выражения в терминах неопределенного  x могут включать арифметические операции, дифференцирование по  x и композицию с другими производящими функциями (т. Е. Подстановку в); поскольку эти операции также определены для функций, результат выглядит как функция от  x . Действительно, выражение в замкнутой форме часто можно интерпретировать как функцию, которая может быть вычислена при (достаточно малых) конкретных значениях x , и которая имеет формальный ряд в качестве разложения в ряд; этим объясняется обозначение «производящие функции». Однако такая интерпретация не требуется, чтобы быть возможной, потому что формальные ряды не требуются для получения сходящегося ряда, когда вместо x подставляется ненулевое числовое значение  . Кроме того, не все выражения, которые имеют смысл как функции от  x, имеют смысл как выражения, обозначающие формальные ряды; например, отрицательные и дробные степени  x являются примерами функций, которые не имеют соответствующего формального степенного ряда.

Производящие функции не являются функциями в формальном смысле отображения из области к области значений . Генерирующие функции иногда называют производящий ряд , ^[2] в том , что ряд терминов , можно сказать, что генератор своей последовательности срочных коэффициентов.

Определения [ править ]

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

- Джордж Полиа , Математика и правдоподобные рассуждения (1954).

Производящая функция - это бельевая веревка, на которую мы вешаем последовательность чисел для отображения.

- Герберт Уилф , Генерирующая функциональность (1994).

Обычная производящая функция (OGF) [ править ]

Обыкновенная производящая функция последовательности _п является

${\ Displaystyle G (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} x ^ {n}.}$

Когда термин производящая функция используется без уточнения, он обычно означает обычную производящую функцию.

Если _п является функцией вероятности массовой из дискретной случайной величины , то ее обычная производящая функция называется функцией вероятности генерации .

Обычная производящая функция может быть обобщена на массивы с несколькими индексами. Например, обычная производящая функция двумерного массива a _{m, n} (где n и m - натуральные числа) имеет вид

${\ displaystyle G (a_ {m, n}; x, y) = \ sum _ {m, n = 0} ^ {\ infty} a_ {m, n} x ^ {m} y ^ {n}.}$

Экспоненциальная производящая функция (EGF) [ править ]

Экспоненциальная производящая функция последовательности _п является

${\ displaystyle \ operatorname {EG} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {n!}}. }$

Экспоненциальные производящие функции обычно более удобны, чем обычные производящие функции для задач комбинаторного перечисления, которые включают помеченные объекты. ^[3]

Производящая функция Пуассона [ править ]

Производящая функция Пуассона последовательности _п является

${\ displaystyle \ operatorname {PG} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} e ^ {- x} {\ frac {x ^ {n}} {n!}} = e ^ {- x} \, \ operatorname {EG} (a_ {n}; x).}$

Серия Ламберта [ править ]

Серии Ламберта последовательности _п является

${\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}$

Коэффициенты ряда Ламберта в разложении степенного ряда для целых чисел связаны суммой делителей . Основная статья содержит еще несколько классических или, по крайней мере, хорошо известных примеров, связанных со специальными арифметическими функциями в теории чисел . В серии Ламберта индекс n начинается с 1, а не с 0, поскольку в противном случае первый член не был бы определен.${\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)}$${\displaystyle n\geq 1}$ ${\displaystyle b_{n}=\sum _{d|n}a_{d}}$

Серия Bell [ править ]

Серии Белл из последовательности _п является выражением с точки зрения как неопределенном х и простого р и задается ^[4]

${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}$

Производящие функции ряда Дирихле (ДГФ) [ править ]

Формальные ряды Дирихле часто классифицируются как производящие функции, хотя они не являются строго формальными степенными рядами. Производящий ряд функций Дирихле последовательности _п является ^[5]

${\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}$

Функция генерирования ряд Дирихля особенно полезна , когда _п является мультипликативной функцией , в этом случае он имеет Эйлера продукт выражение ^[6] в терминах рядов Bell функции в

${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.}$

Если a _n является характером Дирихле, то его производящая функция ряда Дирихле называется L-рядом Дирихле . У нас также есть связь между парой коэффициентов в разложениях в ряд Ламберта выше и их DGF. А именно, мы можем доказать это тогда и только тогда, когда где - дзета-функция Римана . ^[7]${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}$${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s)}$${\displaystyle \zeta (s)}$

Функции генерации полиномиальной последовательности [ править ]

Идея создания функций может быть распространена на последовательности других объектов. Так, например, полиномиальные последовательности биномиального типа порождаются

${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$

где p _n ( x ) - последовательность многочленов, а f ( t ) - функция определенного вида. Последовательности Шеффера генерируются аналогичным образом. См. Основную статью об обобщенных полиномах Аппеля для получения дополнительной информации.

Обычные производящие функции [ править ]

Примеры генерирующих функций для простых последовательностей [ править ]

Полиномы - это частный случай обычных производящих функций, соответствующих конечным последовательностям, или, что эквивалентно, последовательностям, которые исчезают после определенной точки. Они важны тем, что многие конечные последовательности можно с пользой интерпретировать как производящие функции, такие как полином Пуанкаре и другие.

Ключевой производящей функцией является функция постоянной последовательности 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., обычная производящая функция которой - геометрический ряд

${\displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}.}$

Левая часть - это разложение правой части в ряд Маклорена . В качестве альтернативы, равенство может быть подтверждено умножением степенного ряда слева на 1 -  x и проверкой того, что результатом является постоянный степенной ряд 1 (другими словами, что все коэффициенты, кроме одного из x ⁰ , равны 0) . Более того, других степенных рядов с этим свойством быть не может. Следовательно, левая часть обозначает мультипликативную обратную единицу -  x в кольце степенных рядов.

Выражения для обычной производящей функции других последовательностей легко выводятся из этого. Например, замена x  →  ax дает производящую функцию для геометрической последовательности 1, a , a ² , a ³ , ... для любой константы a :

${\displaystyle \sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}.}$

(Равенство также следует непосредственно из того факта, что левая часть является разложением правой части в ряд Маклорена.) В частности,

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.}$

Можно также ввести регулярные "пробелы" в последовательности, заменив x некоторой степенью x , так, например, для последовательности 1, 0, 1, 0, 1, 0, 1, 0, .... получается порождающий функция

${\displaystyle \sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.}$

Возводя в квадрат исходную производящую функцию или находя производную обеих частей по x и делая замену переменной n  →  n  + 1, можно увидеть, что коэффициенты образуют последовательность 1, 2, 3, 4, 5, ..., так что

${\displaystyle \sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}},}$

а третья степень имеет в качестве коэффициентов треугольные числа 1, 3, 6, 10, 15, 21, ..., член n является биномиальным коэффициентом , так что${\displaystyle {\tbinom {n+2}{2}}}$

${\displaystyle \sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.}$

В более общем смысле, для любого неотрицательного целого числа k и ненулевого действительного значения a верно, что

${\displaystyle \sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,.}$

С

${\displaystyle 2{\binom {n+2}{2}}-3{\binom {n+1}{1}}+{\binom {n}{0}}=2{\frac {(n+1)(n+2)}{2}}-3(n+1)+1=n^{2},}$

можно найти обычную производящую функцию для последовательности 0, 1, 4, 9, 16, ... квадратных чисел путем линейной комбинации производящих последовательностей биномиальных коэффициентов:

${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {2}{(1-x)^{3}}}-{\frac {3}{(1-x)^{2}}}+{\frac {1}{1-x}}={\frac {x(x+1)}{(1-x)^{3}}}.}$

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

${\displaystyle {\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}}$

По индукции аналогично можно показать для натуральных чисел, что ^{[8] [9]}${\displaystyle m\geq 1}$

${\displaystyle n^{m}=\sum _{j=0}^{m}\left\{{\begin{matrix}m\\j\end{matrix}}\right\}{\frac {n!}{(n-j)!}},}$

где обозначают числа Стирлинга второго рода и где производящая функция , так что мы можем сформировать аналогичные производящие функции по целым -м степеням, обобщая результат в квадратном случае выше. В частности, поскольку мы можем писать , мы можем применить хорошо известное тождество конечной суммы, включающее числа Стирлинга, чтобы получить это ^[10]${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$${\displaystyle \sum _{n\geq 0}n!/(n-j)!\,z^{n}=j!\cdot z^{j}/(1-z)^{j+1}}$${\displaystyle m}$${\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}}}$

${\displaystyle \sum _{n\geq 0}n^{m}z^{n}=\sum _{j=0}^{m}\left\{{\begin{matrix}m+1\\j+1\end{matrix}}\right\}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}.}$

Рациональные функции [ править ]

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

Отметим также, что класс рациональных производящих функций в точности соответствует производящим функциям, перечисляющим квазиполиномиальные последовательности вида ^[11]

${\displaystyle f_{n}=p_{1}(n)\rho _{1}^{n}+\cdots +p_{\ell }(n)\rho _{\ell }^{n},}$

где взаимные корни, являются фиксированными скалярами, а где - многочлен от для всех .${\displaystyle \rho _{i}\in \mathbb {C} }$${\displaystyle p_{i}(n)}$${\displaystyle n}$${\displaystyle 1\leq i\leq \ell }$

В общем, произведения Адамара рациональных функций порождают рациональные производящие функции. Аналогичным образом , если это двумерный рационально производящей функция, то ее соответствующая диагональ производящая функция , является алгебраической . Например, если мы положим ^[12]${\displaystyle F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}}$${\displaystyle \operatorname {diag} (F):=\sum _{n\geq 0}f(n,n)z^{n}}$

${\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},}$

тогда производящая функция диагонального коэффициента этой производящей функции задается известной формулой OGF

${\displaystyle \operatorname {diag} (F)=\sum _{n\geq 0}{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.}$

Этот результат вычисляется многими способами, включая интегральную формулу Коши или контурное интегрирование , взятие комплексных вычетов или прямое изменение формальных степенных рядов от двух переменных.

Операции над производящими функциями [ править ]

Умножение дает свертку [ править ]

Умножение обычных производящих функций дает дискретную свертку (произведение Коши ) последовательностей. Например, последовательность кумулятивных сумм (сравните с несколько более общей формулой Эйлера – Маклорена )

${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$

последовательности с обычной производящей функцией G ( a _n ;  x ) имеет производящую функцию

${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$

поскольку 1 / (1 -  x ) - обычная производящая функция для последовательности (1, 1, ...). См. Также раздел о свертках в разделе приложений этой статьи ниже для получения дополнительных примеров решения проблем с помощью сверток производящих функций и интерпретаций.

Сдвиг индексов последовательностей [ править ]

Для целых чисел мы имеем следующие два аналогичных тождества для модифицированных производящих функций, перечисляющих сдвинутые варианты последовательностей и , соответственно:${\displaystyle m\geq 1}$${\displaystyle \langle g_{n-m}\rangle }$${\displaystyle \langle g_{n+m}\rangle }$

${\displaystyle {\begin{aligned}z^{m}G(z)&=\sum _{n\geq m}g_{n-m}z^{n}\\{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}&=\sum _{n\geq 0}g_{n+m}z^{n}.\end{aligned}}}$

Дифференциация и интеграция производящих функций [ править ]

У нас есть следующие разложения в степенной ряд для первой производной производящей функции и ее интеграла:

${\displaystyle {\begin{aligned}G^{\prime }(z)&=\sum _{n\geq 0}(n+1)g_{n+1}z^{n}\\z\cdot G^{\prime }(z)&=\sum _{n\geq 0}ng_{n}z^{n}\\\int _{0}^{z}G(t)\,dt&=\sum _{n\geq 1}{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}}$

Операция дифференцирования-умножения второго тождества может повторяться несколько раз, чтобы умножить последовательность на , но это требует чередования между дифференцированием и умножением. Если вместо этого выполнять дифференцирование последовательно, эффект будет умножаться на ^th падающий факториал :${\displaystyle k}$${\displaystyle n^{k}}$${\displaystyle k}$${\displaystyle k}$

${\displaystyle z^{k}G^{(k)}(z)=\sum _{n\geq 0}n^{\underline {k}}g_{n}z^{n}=\sum _{n\geq 0}n(n-1)\dotsb (n-k+1)g_{n}z^{n}{\text{ for all }}k\in \mathbb {N} .}$

Используя числа Стирлинга второго рода , которые можно превратить в другую формулу для умножения на следующим образом (см. Основную статью о преобразованиях производящих функций ):${\displaystyle n^{k}}$

${\displaystyle \sum _{j=0}^{k}\left\{{\begin{matrix}k\\j\end{matrix}}\right\}z^{j}F^{(j)}(z)=\sum _{n\geq 0}n^{k}f_{n}z^{n}{\text{ for all }}k\in \mathbb {N} .}$

Обращение отрицательного порядка этой формулы степеней последовательности, соответствующей операции повторного интегрирования, определяется преобразованием дзета-ряда и его обобщениями, определяемыми как основанное на производной преобразовании производящих функций , или, альтернативно, почленно путем выполнения интегрального преобразования в последовательности производящая функция. Связанные операции выполнения дробной интеграции на порождающей функции последовательности обсуждаются здесь .

Перечисление арифметических последовательностей [ править ]

В этом параграфе мы дадим формулу для производящих функций перечисления последовательности заданной обычной производящей функции , где , и (см основной статьи о преобразованиях ). Ведь это просто знакомое разложение функции на четные и нечетные части (т.е. четные и нечетные степени):${\displaystyle \{f_{an+b}\}}$${\displaystyle F(z)}$${\displaystyle a,b\in \mathbb {N} }$${\displaystyle a\geq 2}$${\displaystyle 0\leq b<a}$${\displaystyle a=2}$

${\displaystyle \sum _{n\geq 0}f_{2n}z^{2n}={\frac {1}{2}}\left(F(z)+F(-z)\right)}$

${\displaystyle \sum _{n\geq 0}f_{2n+1}z^{2n+1}={\frac {1}{2}}\left(F(z)-F(-z)\right).}$

В более общем плане , предположим , что и означает ^й примитивный корень из единицы . Тогда как приложение дискретного преобразования Фурье имеем формулу ^[13]${\displaystyle a\geq 3}$${\displaystyle \omega _{a}=\exp \left(2\pi \imath /a\right)}$${\displaystyle a}$

${\displaystyle \sum _{n\geq 0}f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).}$

Для целых чисел другая полезная формула, обеспечивающая несколько перевернутые арифметические прогрессии - эффективное повторение каждого коэффициента раз - генерируется тождеством ^[14]${\displaystyle m\geq 1}$${\displaystyle m}$

${\displaystyle \sum _{n\geq 0}f_{\lfloor {\frac {n}{m}}\rfloor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1}\right)F(z^{m}).}$

P-рекурсивные последовательности и голономные производящие функции [ править ]

Определения [ править ]

Формальный степенной ряд (или функция) называется голономным, если он удовлетворяет линейному дифференциальному уравнению вида ^[15]${\displaystyle F(z)}$

${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}$

где коэффициенты находятся в поле рациональных функций, . Эквивалентно, голономно, если векторное пространство, натянутое на множество всех его производных, конечномерно.${\displaystyle c_{i}(z)}$${\displaystyle \mathbb {C} (z)}$${\displaystyle F(z)}$${\displaystyle \mathbb {C} (z)}$

Поскольку мы можем очистить знаменатели, если это необходимо в предыдущем уравнении, мы можем предположить, что функции являются полиномами от . Таким образом, мы видим эквивалентное условие голономности производящей функции, если ее коэффициенты удовлетворяют P-рекуррентности вида${\displaystyle c_{i}(z)}$${\displaystyle z}$

${\displaystyle {\widehat {c}}_{s}(n)f_{n+s}+{\widehat {c}}_{s-1}(n)f_{n+s-1}+\cdots +{\widehat {c}}_{0}(n)f_{n}=0,}$

для всех достаточно больших и где фиксированы многочлены конечной степени от . Другими словами, свойства того, что последовательность P-рекурсивна и имеет голономную производящую функцию, эквивалентны. Голономные функции закрываются операцией произведения Адамара над производящими функциями.${\displaystyle n\geq n_{0}}$${\displaystyle {\widehat {c}}_{i}(n)}$${\displaystyle n}$${\displaystyle \odot }$

Примеры [ править ]

Функции , , , , , то дилогарифма функция , то обобщенные гипергеометрические функции и функция , определенная серии мощности и не-сходящееся все голономные. Примеры P-рекурсивных последовательностей с голономными производящими функциями включают и , где такие последовательности, как и , не являются P-рекурсивными из-за природы сингулярностей в их соответствующих производящих функциях. Аналогично, функции с бесконечно многих особенностей , таких как , и это не голономные функции.${\displaystyle e^{z}}$${\displaystyle \log(z)}$${\displaystyle \cos(z)}$${\displaystyle \arcsin(z)}$${\displaystyle {\sqrt {1+z}}}$${\displaystyle \operatorname {Li} _{2}(z)}$ ${\displaystyle _{p}F_{q}(...;...;z)}$${\displaystyle \sum _{n\geq 0}z^{n}/(n!)^{2}}$${\displaystyle \sum _{n\geq 0}n!\cdot z^{n}}$${\displaystyle f_{n}:={\frac {1}{n+1}}{\binom {2n}{n}}}$${\displaystyle f_{n}:=2^{n}/(n^{2}+1)}$${\displaystyle {\sqrt {n}}}$${\displaystyle \log(n)}$${\displaystyle \tan(z)}$${\displaystyle \sec(z)}$${\displaystyle \Gamma (z)}$

Программа для работы с P-рекурсивными последовательностями и голономными производящими функциями [ править ]

Инструменты для обработки и работы с P-рекурсивными последовательностями в системе Mathematica включают пакеты программного обеспечения, предоставленные для некоммерческого использования на сайте программного обеспечения алгоритмической комбинаторики RISC Combinatorics Group . Несмотря на то, что это в основном закрытый исходный код, особенно мощные инструменты в этом программном пакете предоставляются пакетом Guess для угадывания P-повторений для произвольных входных последовательностей (полезно для экспериментальной математики и исследований) и пакетом Sigma , который может находить P-повторения для много сумм и решение для замкнутых решений P-рекуррент, включающих обобщенные гармонические числа . ^[16]Другие пакеты, перечисленные на этом конкретном сайте RISC, специально предназначены для работы с функциями генерации голономии . ( В зависимости от того, насколько подробно эта статья посвящена теме, существует множество других примеров полезных программных инструментов, которые можно перечислить здесь или на этой странице в другом разделе. )

Связь с преобразованием Фурье с дискретным временем [ править ]

Когда ряд абсолютно сходится ,

${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$

- дискретное преобразование Фурье последовательности a ₀ ,  a ₁ , ....

Асимптотический рост последовательности [ править ]

В расчетах часто скорость роста коэффициентов степенного ряда может использоваться для определения радиуса сходимости степенного ряда. Обратное тоже может иметь место; часто радиус сходимости производящей функции может использоваться для вывода асимптотического роста базовой последовательности.

Например, если обычная производящая функция G ( a _n ;  x ), имеющая конечный радиус сходимости r, может быть записана как

${\displaystyle G(a_{n};x)={\frac {A(x)+B(x)\left(1-{\frac {x}{r}}\right)^{-\beta }}{x^{\alpha }}}}$

где каждая из A ( x ) и B ( x ) является функцией, аналитической с радиусом сходимости больше r (или целой ), и где B ( r ) ≠ 0, то

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}(1/r)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}(1/r)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\!\right)(1/r)^{n}\,,}$

с использованием гамма-функции , биномиального коэффициента или коэффициента мультимножества .

Часто такой подход может повторяться для создания нескольких терминов в асимптотический ряд для в _п . Особенно,

${\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}(1/r)^{n};x\right)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}}\right)^{-\beta }\,.}$

Затем можно искать асимптотический рост коэффициентов этой производящей функции, находя A , B , α, β и r для описания производящей функции, как указано выше.

Аналогичный асимптотический анализ возможен для экспоненциальных производящих функций. С экспоненциальной производящей функцией, то _п / п ! который растет согласно этим асимптотическим формулам.

Асимптотический рост последовательности квадратов [ править ]

Как показано выше, обычная производящая функция для последовательности квадратов имеет вид

${\displaystyle {\frac {x(x+1)}{(1-x)^{3}}}.}$

При r  = 1, α = −1, β = 3, A ( x ) = 0 и B ( x ) =  x +1 мы можем проверить, что квадраты растут, как и ожидалось, как и квадраты:

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}(1/1)^{n}=n^{2}.}$

Асимптотический рост каталонских чисел [ править ]

Обычная производящая функция для каталонских чисел:

${\displaystyle {\frac {1-{\sqrt {1-4x}}}{2x}}.}$

При r  = 1/4, α = 1, β = −1/2, A ( x ) = 1/2 и B ( x ) = −1/2 мы можем заключить, что для каталонских чисел

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{({\frac {1}{4}})^{1}\Gamma (-{\frac {1}{2}})}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\frac {1}{4}}}\right)^{n}={\frac {1}{\sqrt {\pi }}}n^{-{\frac {3}{2}}}\,4^{n}.}$

Двумерные и многомерные производящие функции [ править ]

Для массивов с несколькими индексами можно определить производящие функции от нескольких переменных. Их называют многомерными производящими функциями или, иногда, суперпроизводящими функциями . Для двух переменных их часто называют двумерными производящими функциями .

Например, поскольку это обычная производящая функция для биномиальных коэффициентов для фиксированного n , можно запросить двумерную производящую функцию, которая генерирует биномиальные коэффициенты для всех k и n . Для этого рассмотрим ряд по n и найдите производящую функцию по y , у которой они есть коэффициенты. Поскольку производящая функция для равна${\displaystyle (1+x)^{n}}$${\displaystyle {\binom {n}{k}}}$${\displaystyle (1+x)^{n}}$${\displaystyle a^{n}}$

${\displaystyle {\frac {1}{1-ay}},}$

производящая функция для биномиальных коэффициентов:

${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$

Представление цепными дробями (J-дроби типа Якоби) [ править ]

Определения [ править ]

Разложения (формальных) цепных дробей типа Якоби и Стилтьеса ( J-дроби и S-дроби соответственно), рациональные сходящиеся дроби которых представляют собой степенные ряды с точностью до порядка, являются еще одним способом выразить типично расходящиеся обычные производящие функции для многих специальных и двухвариантные последовательности. Конкретная форма непрерывных дробей типа Якоби (J-дроби) раскрывается, как в следующем уравнении, и имеет следующие соответствующие расширения степенного ряда по отношению к некоторым конкретным, зависящим от приложения последовательностям компонентов, и , где${\displaystyle h^{th}}$ 2 h {\displaystyle 2h} ${\displaystyle z}$${\displaystyle \{{\text{ab}}_{i}\}}$${\displaystyle \{c_{i}\}}$${\displaystyle z\neq 0}$обозначает формальную переменную во втором разложении степенного ряда, приведенном ниже: ^[17]

${\displaystyle {\begin{aligned}J^{[\infty ]}(z)&={\cfrac {1}{1-c_{1}z-{\cfrac {{\text{ab}}_{2}z^{2}}{1-c_{2}z-{\cfrac {{\text{ab}}_{3}z^{2}}{\ddots }}}}}}\\&=1+c_{1}z+\left({\text{ab}}_{2}+c_{1}^{2}\right)z^{2}+\left(2{\text{ab}}_{2}c_{1}+c_{1}^{3}+{\text{ab}}_{2}c_{2}\right)z^{3}+\cdots .\end{aligned}}}$

Коэффициенты при , сокращенно обозначенные в предыдущих уравнениях, соответствуют матричным решениям уравнений${\displaystyle z^{n}}$${\displaystyle j_{n}:=[z^{n}]J^{[\infty ]}(z)}$

${\displaystyle {\begin{bmatrix}k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\k_{0,3}&k_{1,3}&k_{2,3}&k_{3,3}&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}={\begin{bmatrix}k_{0,0}&0&0&0&\cdots \\k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}\cdot {\begin{bmatrix}c_{1}&1&0&0&\cdots \\{\text{ab}}_{2}&c_{2}&1&0&\cdots \\0&{\text{ab}}_{3}&c_{3}&1&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}},}$

где , для , если и где для всех целых чисел , у нас есть соотношение формулы сложения, заданное следующим образом:${\displaystyle j_{0}\equiv k_{0,0}=1}$${\displaystyle j_{n}=k_{0,n}}$${\displaystyle n\geq 1}$${\displaystyle k_{r,s}=0}$${\displaystyle r>s}$${\displaystyle p,q\geq 0}$

${\displaystyle j_{p+q}=k_{0,p}\cdot k_{0,q}+\sum _{i=1}^{\min(p,q)}{\text{ab}}_{2}\cdots {\text{ab}}_{i+1}\times k_{i,p}\cdot k_{i,q}.}$

Свойства h- ^й сходящейся функции [ править ]

Для (хотя на практике, когда ) мы можем определить рациональные подходящие дроби к бесконечной J-дроби , разложенной на${\displaystyle h\geq 0}$${\displaystyle h\geq 2}$${\displaystyle h^{\text{th}}}$${\displaystyle J^{[\infty ]}(z)}$

${\displaystyle \operatorname {Conv} _{h}(z):={\frac {P_{h}(z)}{Q_{h}(z)}}=j_{0}+j_{1}z+\cdots +j_{2h-1}z^{2h-1}+\sum _{n\geq 2h}{\widetilde {j}}_{h,n}z^{n},}$

покомпонентно через последовательности и , рекурсивно определяемый${\displaystyle P_{h}(z)}$${\displaystyle Q_{h}(z)}$

${\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{\text{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{\text{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}}$

Более того, рациональность сходящейся функции для всех влечет за собой дополнительные конечно-разностные уравнения и свойства сравнения, которым удовлетворяет последовательность , а для, если тогда мы имеем сравнение${\displaystyle {\text{Conv}}_{h}(z)}$${\displaystyle h\geq 2}$${\displaystyle j_{n}}$${\displaystyle M_{h}:={\text{ab}}_{2}\cdots {\text{ab}}_{h+1}}$${\displaystyle h|\mid M_{h}}$

${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}$

для не-символического, детерминированного выбора последовательностей параметров, и , когда , то есть, когда эти последовательности не неявно зависят от вспомогательного параметра , таких как , или , как в примерах , содержащихся в таблице ниже.${\displaystyle \{{\text{ab}}_{i}\}}$${\displaystyle \{c_{i}\}}$${\displaystyle h\geq 2}$${\displaystyle q}$${\displaystyle x}$${\displaystyle R}$

Примеры [ править ]

В следующей таблице приведены примеры формул замкнутых формул для последовательностей компонентов, найденных вычислительным путем (и впоследствии доказавших свою правильность в цитируемых ссылках ^[18] ) в нескольких частных случаях предписанных последовательностей , порожденных общими разложениями J-дробей, определенных в первом подразделе. Здесь мы определяем и параметры , и быть неизвестными в отношении этих разложений, где предписанные последовательности , перечисленных путем разложения этих J-фракции определены в терминах Q-Похгаммере символа , символ Похгаммера , и биномиальных коэффициенты .${\displaystyle j_{n}}$${\displaystyle 0<|a|,|b|,|q|<1}$${\displaystyle R}$${\displaystyle \alpha \in \mathbb {Z} ^{+}}$${\displaystyle x}$

${\displaystyle j_{n}}$	${\displaystyle c_{1}}$	${\displaystyle c_{i}(i\geq 2)}$	${\displaystyle {\text{ab}}_{i}(i\geq 2)}$
${\displaystyle q^{n^{2}}}$	${\displaystyle q}$	${\displaystyle q^{2h-3}\left(q^{2h}+q^{2h-2}-1\right)}$	${\displaystyle q^{6h-10}\left(q^{2h-2}-1\right)}$
${\displaystyle (a;q)_{n}}$	${\displaystyle 1-a}$	${\displaystyle q^{h-1}-aq^{h-2}\left(q^{h}+q^{h-1}-1\right)}$	${\displaystyle aq^{2h-4}(aq^{h-2}-1)(q^{h-1}-1)}$
${\displaystyle \left(zq^{-n};q\right)_{n}}$	${\displaystyle {\frac {q-z}{q}}}$	${\displaystyle {\frac {q^{h}-z-qz+q^{h}z}{q^{2h-1}}}}$	${\displaystyle {\frac {(q^{h-1}-1)(q^{h-1}-z)\cdot z}{q^{4h-5}}}}$
${\displaystyle {\frac {(a;q)_{n}}{(b;q)_{n}}}}$	${\displaystyle {\frac {1-a}{1-b}}}$	${\displaystyle {\frac {q^{i-2}\left(q+abq^{2i-3}+a(1-q^{i-1}-q^{i})+b(q^{i}-q-1)\right)}{(1-bq^{2i-4})(1-bq^{2i-2})}}}$	${\displaystyle {\frac {q^{2i-4}(1-bq^{i-3})(1-aq^{i-2})(a-bq^{i-2})(1-q^{i-1})}{(1-bq^{2i-5})(1-bq^{2i-4})^{2}(1-bq^{2i-3})}}}$
${\displaystyle \alpha ^{n}\cdot \left({\frac {R}{\alpha }}\right)_{n}}$	${\displaystyle R}$	${\displaystyle R+2\alpha (i-1)}$	${\displaystyle (i-1)\alpha (R+(i-2)\alpha )}$
${\displaystyle (-1)^{n}{\binom {x}{n}}}$	${\displaystyle -x}$	${\displaystyle -{\frac {(x+2(i-1)^{2})}{(2i-1)(2i-3)}}}$	${\displaystyle {\begin{cases}-{\frac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&i\geq 3;\\-{\frac {1}{2}}x(x+1)&i=2.\end{cases}}}$
${\displaystyle (-1)^{n}{\binom {x+n}{n}}}$	${\displaystyle -(x+1)}$	${\displaystyle {\frac {(x-2i(i-2)-1)}{(2i-1)(2i-3)}}}$	${\displaystyle {\begin{cases}-{\frac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&i\geq 3;\\-{\frac {1}{2}}x(x+1)&i=2.\end{cases}}}$

Радиусы сходимости этих рядов, соответствующих приведенному выше определению J-дробей типа Якоби, в общем случае отличаются от радиусов сходимости соответствующих разложений в степенные ряды, определяющих обычные производящие функции этих последовательностей.

Примеры [ править ]

Производящими функциями для последовательности квадратных чисел a _n = n ² являются:

Обычная производящая функция [ править ]

${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}}$

Экспоненциальная производящая функция [ править ]

${\displaystyle \operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}}$

Серия Ламберта [ править ]

В качестве примера тождества ряда Ламберта, не приведенного в основной статье , мы можем показать, что, поскольку у нас есть это ^[19]${\displaystyle |x|,|xq|<1}$

${\displaystyle \sum _{n\geq 1}{\frac {q^{n}x^{n}}{1-x^{n}}}=\sum _{n\geq 1}{\frac {q^{n}x^{n^{2}}}{1-qx^{n}}}+\sum _{n\geq 1}{\frac {q^{n}x^{n(n+1)}}{1-x^{n}}},}$

где у нас есть специальный идентификатор случая для производящей функции функции делителей , , задаваемый${\displaystyle d(n)\equiv \sigma _{0}(n)}$

${\displaystyle \sum _{n\geq 1}{\frac {x^{n}}{1-x^{n}}}=\sum _{n\geq 1}{\frac {x^{n^{2}}(1+x^{n})}{1-x^{n}}}.}$

Серия Bell [ править ]

${\displaystyle \operatorname {BG} _{p}(n^{2};x)=\sum _{n=0}^{\infty }(p^{n})^{2}x^{n}={\frac {1}{1-p^{2}x}}}$

Производящая функция ряда Дирихле [ править ]

${\displaystyle \operatorname {DG} (n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2),}$

используя дзета-функцию Римана .

Последовательность a _k, порожденная производящей функцией ряда Дирихле (DGF), соответствующей:

${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$

где - дзета-функция Римана , имеет обычную производящую функцию:${\displaystyle \zeta (s)}$

${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{m \choose 1}\sum _{2\leq a\leq n}x^{a}+{m \choose 2}{\underset {ab\leq n}{\sum _{a\geq 2}\sum _{b\geq 2}}}x^{ab}+{m \choose 3}{\underset {abc\leq n}{\sum _{a\geq 2}\sum _{c\geq 2}\sum _{b\geq 2}}}x^{abc}+{m \choose 4}{\underset {abcd\leq n}{\sum _{a\geq 2}\sum _{b\geq 2}\sum _{c\geq 2}\sum _{d\geq 2}}}x^{abcd}+\cdots }$

Многомерные производящие функции [ править ]

Многовариантные производящие функции возникают на практике при вычислении количества таблиц непредвиденных обстоятельств неотрицательных целых чисел с заданными суммами по строкам и столбцам. Предположим, что в таблице есть r строк и c столбцов; суммы строк равны, а суммы столбцов равны . Тогда, согласно IJ Good , ^[20] количество таких таблиц является коэффициентом${\displaystyle t_{1},\ldots t_{r}}$${\displaystyle s_{1},\ldots s_{c}}$

${\displaystyle x_{1}^{t_{1}}\ldots x_{r}^{t_{r}}y_{1}^{s_{1}}\ldots y_{c}^{s_{c}}}$

в

${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$

В двумерном случае примеры неполиномиальной двойной суммы так называемых « двойных » или « супер » производящих функций формы включают следующие производящие функции с двумя переменными для биномиальных коэффициентов , чисел Стирлинга и чисел Эйлера : ^{[ 21]}${\displaystyle G(w,z):=\sum _{m,n\geq 0}g_{m,n}w^{m}z^{n}}$

${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}\left\{{\begin{matrix}n\\m\end{matrix}}\right\}w^{m}{\frac {z^{n}}{n!}}\\{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}\left[{\begin{matrix}n\\m\end{matrix}}\right]w^{m}{\frac {z^{n}}{n!}}\\{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}}\right\rangle w^{m}{\frac {z^{n}}{n!}}\\{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}}\right\rangle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}}$

Приложения [ править ]

Различные методы: оценка сумм и решение других проблем с помощью генерирующих функций [ править ]

Пример 1. Формула суммы гармонических чисел [ править ]

Производящие функции дают нам несколько методов для управления суммами и установления тождеств между суммами.

Самый простой случай возникает, когда . Затем мы знаем, что для соответствующих обычных производящих функций.${\displaystyle s_{n}=\sum _{k=0}^{n}{a_{k}}}$${\displaystyle S(z)={\frac {A(z)}{1-z}}}$

Например, мы можем манипулировать , где находятся номера гармоник . Позвольте быть обычной производящей функцией гармонических чисел. потом${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}}$${\displaystyle H_{k}=1+{\frac {1}{2}}+\cdots +{\frac {1}{k}}}$${\displaystyle H(z)=\sum _{n\geq 1}{H_{n}z^{n}}}$