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

Формальный степенной ряд; коэффициенты кодируют информацию о последовательности, индексированной натуральными числами.

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

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

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

История

Производящие функции были впервые введены Абрахамом де Муавром в 1730 году для решения общей линейной рекуррентной задачи. ^[2]

Джордж Полиа пишет в своей книге «Математика и правдоподобные рассуждения» :

Название «производящая функция» дано Лапласу . Однако, не давая ему названия, Эйлер использовал прием производящих функций задолго до Лапласа [..]. Он применил этот математический инструмент к нескольким задачам комбинаторного анализа и теории чисел .

Определение

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

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

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

—  Герберт Вильф , Генерирующая функционалология (1994)

Конвергенция

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

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

Ограничения

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

Типы

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

Когда термин «производящая функция» используется без уточнения, он обычно подразумевает обычную производящую функцию. Обычная производящая функция последовательности a _n имеет вид: Если a _n — это функция массы вероятности дискретной случайной величины , то ее обычная производящая функция называется функцией, производящей вероятность . $${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$$

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

Экспоненциальная производящая функция последовательности a _n равна $${\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}$$

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

Другим преимуществом экспоненциальных производящих функций является то, что они полезны при переносе линейных рекуррентных соотношений в область дифференциальных уравнений . Например, возьмем последовательность Фибоначчи { f _n } , которая удовлетворяет линейному рекуррентному соотношению f _{n +2} = f _{n +1} + f _n . Соответствующая экспоненциальная производящая функция имеет вид $${\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}$$

и его производные можно легко показать, что они удовлетворяют дифференциальному уравнению EF″( x ) = EF ′ ( x ) + EF( x ) как прямому аналогу рекуррентного соотношения выше. С этой точки зрения факториальный член n ! является просто контрчленом для нормализации оператора производной, действующего на x ⁿ .

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

Производящая функция Пуассона последовательности a _n равна $${\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).}$$

серия Ламберта

Ряд Ламберта последовательности a _n имеет вид Обратите внимание, что в ряде Ламберта индекс n начинается с 1, а не с 0, так как в противном случае первый член был бы неопределен. $${\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}$$

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

_{где мы имеем} особый случай тождества для производящей функции функции делителя , d ( n ) ≡ σ0 ( n ) , заданный как $${\displaystyle \sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n}\right)}{1-x^{n}}}.}$$

Серия колоколов

Ряд Белла последовательности a _n представляет собой выражение в терминах как неопределенного x , так и простого числа p и задается формулой: ^[5] $${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}$$

Функции производства рядов Дирихле (DGF)

Формальные ряды Дирихле часто классифицируются как производящие функции, хотя они не являются строго формальными степенными рядами. Производящая функция ряда Дирихле последовательности a _n имеет вид: ^[6] $${\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}$$

Функция производства ряда Дирихле особенно полезна, когда _n является мультипликативной функцией , в этом случае она имеет выражение произведения Эйлера ^[7] в терминах ряда Белла функции: $${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.}$$

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

Последовательность a _k , сгенерированная производящей функцией ряда Дирихле (DGF), соответствующая: имеет обычную производящую функцию: $${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$$ $${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots }$$

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

Идея генерации функций может быть распространена на последовательности других объектов. Так, например, полиномиальные последовательности биномиального типа генерируются следующим образом: где p _n ( x ) — последовательность полиномов, а f ( t ) — функция определенного вида. Последовательности Шеффера генерируются аналогичным образом. Для получения дополнительной информации см. основную статью обобщенные полиномы Аппеля . $${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$$

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

• Полиномы Аппеля
• полиномы Чебышева
• Разностные полиномы
• Обобщенные полиномы Аппеля
• q -разностные полиномы

Другие производящие функции

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

• Двойные экспоненциальные производящие функции. Например: Массив Эйткена: Треугольник чисел
• Произведения Адамара производящих функций и диагональных производящих функций и соответствующие им интегральные преобразования

Сверточные полиномы

Статья Кнута под названием « Сверточные полиномы » ^[9] определяет обобщенный класс последовательностей сверточных полиномов с помощью их специальных производящих функций вида для некоторой аналитической функции F с разложением в степенной ряд, таким что F (0) = 1 . $${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$

Мы говорим, что семейство многочленов f ₀ , f ₁ , f ₂ , ... образует семейство сверток, если deg f _n ≤ n и если следующее условие свертки выполняется для всех x , y и для всех n ≥ 0 : $${\displaystyle f_{n}(x+y)=f_{n}(x)f_{0}(y)+f_{n-1}(x)f_{1}(y)+\cdots +f_{1}(x)f_{n-1}(y)+f_{0}(x)f_{n}(y).}$$

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

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

• Последовательность n ! · f _n ( x ) имеет биномиальный тип
• Специальные значения последовательности включают f _n (1) = [ z ⁿ ] F ( z ) и f _n (0) = δ _{n ,0} , а также
• Для произвольных (фиксированных) эти полиномы удовлетворяют формулам свертки вида ${\displaystyle x,y,t\in \mathbb {C} }$

$${\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(y)\\{\frac {(x+y)f_{n}(x+y+tn)}{x+y+tn}}&=\sum _{k=0}^{n}{\frac {xf_{k}(x+tk)}{x+tk}}{\frac {yf_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}}$$

Для фиксированного ненулевого параметра мы модифицировали производящие функции для этих последовательностей полиномов свертки, заданных как где 𝓕 _t ( z ) неявно определяется функциональным уравнением вида 𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^t ) . Более того, мы можем использовать матричные методы (как в ссылке), чтобы доказать, что если даны две последовательности полиномов свертки, ⟨ f _n ( x ) ⟩ и ⟨ g _n ( x ) ⟩ , с соответствующими производящими функциями, F ( z ) ^x и G ( z ) ^x , то для произвольного t мы имеем тождество ${\displaystyle t\in \mathbb {C} }$ $${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$ $${\displaystyle \left[z^{n}\right]\left(G(z)F\left(zG(z)^{t}\right)\right)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{n-k}(x+tk).}$$

Примерами последовательностей сверточных полиномов являются биномиальный степенной ряд , 𝓑 _t ( z ) = 1 + z 𝓑 _t ( z ) ^t , так называемые древовидные полиномы , числа Белла , B ( n ) , полиномы Лагерра и сверточные полиномы Стирлинга .

Обычные производящие функции

Примеры простых последовательностей

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

Фундаментальной производящей функцией является функция постоянной последовательности 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 ,} равны 0). Более того, не может быть других степенных рядов с таким свойством. Таким образом, левая часть обозначает мультипликативную обратную величину 1 − 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, ... ⁽ которая пропускает x , x3 , ^x5 , ... ) можно получить производящую функцию $${\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 является биномиальным коэффициентом (^{н + 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}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}}$$

По индукции мы можем аналогично показать для положительных целых чисел m ≥ 1 , что ^{[10] [11]} $${\displaystyle n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},}$$

где {^н
_к} обозначают числа Стирлинга второго рода , а производящая функция $${\displaystyle \sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},}$$

так что мы можем сформировать аналогичные производящие функции над целыми m -ми степенями, обобщая результат в квадратном случае выше. В частности, поскольку мы можем записать $${\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}},}$$

мы можем применить хорошо известное конечно-суммовое тождество, включающее числа Стирлинга, чтобы получить ^[12] $${\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}=\sum _{j=0}^{m}{\begin{Bmatrix}m+1\\j+1\end{Bmatrix}}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}.}$$

Рациональные функции

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

Мы также замечаем, что класс рациональных производящих функций в точности соответствует производящим функциям, которые перечисляют квазиполиномиальные последовательности вида ^[13] $${\displaystyle f_{n}=p_{1}(n)\rho _{1}^{n}+\cdots +p_{\ell }(n)\rho _{\ell }^{n},}$$

где обратные корни, , являются фиксированными скалярами и где p _i ( n ) является полиномом от n для всех 1 ≤ i ≤ ℓ . ${\displaystyle \rho _{i}\in \mathbb {C} }$

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

является двумерной рациональной производящей функцией, то ее соответствующая диагональная производящая функция , $${\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},}$$

является алгебраическим . Например, если мы допустим ^[14] $${\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=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.}$$

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

Операции по производству функций

Умножение дает свертку

Умножение обычных производящих функций дает дискретную свертку ( произведение Коши ) последовательностей. Например, последовательность кумулятивных сумм (сравните с немного более общей формулой Эйлера–Маклорена ) последовательности с обычной производящей функцией G ( a _n ; x ) имеет производящую функцию, потому что ⁠ $${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$ $${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$$1/1 − х⁠ — это обычная производящая функция для последовательности (1, 1, ...) . См. также раздел о свертках в разделе приложений этой статьи ниже для дополнительных примеров решения задач со свертками производящих функций и интерпретаций.

Сдвиг индексов последовательности

Для целых чисел m ≥ 1 мы имеем следующие два аналогичных тождества для модифицированных производящих функций, перечисляющих сдвинутые варианты последовательностей ⟨ g _{n − m} ⟩ и ⟨ g _{n + m} ⟩ соответственно: $${\displaystyle {\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned}}}$$

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

Имеем следующие соответствующие разложения в степенной ряд для первой производной производящей функции и ее интеграла: $${\displaystyle {\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}}$$

Операция дифференциации-умножения второго тождества может быть повторена k раз, чтобы умножить последовательность на n ^k , но это требует чередования дифференциации и умножения. Если вместо этого выполнить k дифференциаций последовательно, эффект будет заключаться в умножении на k- й падающий факториал : $${\displaystyle z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

Используя числа Стирлинга второго рода , это можно преобразовать в другую формулу для умножения на следующим образом (см. основную статью о преобразованиях производящих функций ): ${\displaystyle n^{k}}$ $${\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

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

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

В этом разделе мы приводим формулы для производящих функций, перечисляющих последовательность { f _{an + b} }, заданную обычной производящей функцией F ( z ) , где a ≥ 2 , 0 ≤ b < a , а a и b — целые числа (см. основную статью о преобразованиях ). Для a = 2 это просто знакомое разложение функции на четную и нечетную части (т. е. четные и нечетные степени): $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}$$

В более общем случае предположим, что a ≥ 3 и что ω _a = exp ⁠2 πi/а⁠ обозначает a- й примитивный корень из единицы . Тогда, как применение дискретного преобразования Фурье , имеем формулу ^[15] $${\displaystyle \sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).}$$

Для целых чисел m ≥ 1 другая полезная формула, дающая несколько обратные арифметические прогрессии с понижением уровня — фактически повторяя каждый коэффициент m раз — генерируется тождеством ^[16] $${\displaystyle \sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}}\right\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}).}$$

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

Определения

Формальный степенной ряд (или функция) F ( z ) называется голономным , если он удовлетворяет линейному дифференциальному уравнению вида ^[17] $${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}$$

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

Поскольку мы можем очистить знаменатели, если это необходимо в предыдущем уравнении, мы можем предположить, что функции, c _i ( z ) являются полиномами по z . Таким образом, мы можем увидеть эквивалентное условие, что производящая функция является голономной, если ее коэффициенты удовлетворяют P -рекуррентности вида $${\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,}$$

для всех достаточно больших n ≥ n ₀ и где ĉ _i ( n ) являются фиксированными полиномами конечной степени от n . Другими словами, свойства, что последовательность является P -рекурсивной и имеет голономную производящую функцию, эквивалентны. Голономные функции замкнуты относительно операции произведения Адамара ⊙ на производящих функциях.

Примеры

Функции e ^z , log z , cos z , arcsin z , , дилогарифмическая функция Li ₂ ( z ) , обобщенные гипергеометрические функции _p F _q (...; ...; z ) и функции, определяемые степенным рядом ${\displaystyle {\sqrt {1+z}}}$ $${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}$$

и неконвергентный $${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}$$

все голономны.

Примеры P -рекурсивных последовательностей с голономными производящими функциями включают f _n ≔ ⁠1/н + 1⁠ (^{2 н}
_н) и f _n ≔ ⁠2 ^н/н ² + 1⁠ , где последовательности, такие каки log n, не являются P -рекурсивными из-за природы особенностей в их соответствующих производящих функциях. Аналогично, функции с бесконечным числом особенностей, такие как tan z , sec z , и Γ( z ) не являютсяголономными функциями. ${\displaystyle {\sqrt {n}}}$

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

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

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

Когда ряд сходится абсолютно , является дискретным по времени преобразованием Фурье последовательности a ₀ , a ₁ , ... . $${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$$

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

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

Например, если обычная производящая функция G ( an ; 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 , то используя гамма-функцию , биномиальный коэффициент или мультимножественный коэффициент . Обратите внимание, что предел при n , стремящемся к бесконечности отношения a _n к любому из этих выражений гарантированно равен 1; а не просто то, что a _n пропорционально им. $${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\!\right)\left({\frac {1}{r}}\right)^{n}\,,}$$

Часто этот подход можно повторять для генерации нескольких членов в асимптотическом ряду для _n . В частности, $${\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n};x\right)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}}\right)^{-\beta }\,.}$$

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

Подобный асимптотический анализ возможен для экспоненциальных производящих функций; с экспоненциальной производящей функцией это ⁠а _н/н !⁠ которая растет согласно этим асимптотическим формулам. Как правило, если производящая функция одной последовательности за вычетом производящей функции второй последовательности имеет радиус сходимости, который больше радиуса сходимости отдельных производящих функций, то две последовательности имеют одинаковый асимптотический рост.

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

Как выведено выше, обычная производящая функция для последовательности квадратов имеет вид: $${\displaystyle G(n^{2};x)={\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}\left({\frac {1}{1}}\right)^{n}=n^{2}.}$$

Асимптотический рост чисел Каталана

Обычная производящая функция для чисел Каталана имеет вид $${\displaystyle G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.}$$

При г = ⁠1/4⁠ , α = 1 , β = − ⁠1/2⁠ , А ( х ) = ⁠1/2⁠ , и B ( x ) = − ⁠1/2⁠ , мы можем заключить, что для каталонских чисел: $${\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}}\right)^{1}\Gamma \left(-{\frac {1}{2}}\right)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}}\right)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.}$$

Двумерные и многомерные производящие функции

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

Двумерный случай

Обычная производящая функция двумерного массива a _{m , n} (где n и m — натуральные числа) имеет вид: Например, поскольку (1 + x ) ⁿ является обычной производящей функцией для биномиальных коэффициентов для фиксированного n , можно запросить двумерную производящую функцию, которая генерирует биномиальные коэффициенты ( $${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$$^н
_к) для всех k и n . Для этого рассмотрим (1 + x ) ⁿ как последовательность в n и найдем производящую функцию в y , которая имеет эти значения последовательности в качестве коэффициентов. Поскольку производящая функция для n равна: ^{производящая функция для биномиальных} коэффициентов равна: Другие примеры таких функций включают следующие двухпеременные производящие функции для биномиальных коэффициентов , чисел Стирлинга и чисел Эйлера , где ω и z обозначают две переменные: ^[19] $${\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}}.}$$ $${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\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!}}\\[4px]{\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}}}$$

Многомерный случай

Многомерные производящие функции возникают на практике при вычислении количества таблиц сопряженности неотрицательных целых чисел с заданными суммами строк и столбцов. Предположим, что таблица имеет r строк и c столбцов; суммы строк равны t ₁ , t ₂ ... t _r , а суммы столбцов равны s ₁ , s ₂ ... s _c . Тогда, согласно IJ Good , ^[20] количество таких таблиц равно коэффициенту: в: $${\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}}$$ $${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$$

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

Определения

Разложения (формальных) непрерывных дробей типа Якоби и типа Стилтьеса ( J -дроби и S -дроби , соответственно), чьи h -е рациональные конвергенты представляют точные степенные ряды 2 h -го порядка , являются еще одним способом выражения типично расходящихся обычных производящих функций для многих специальных последовательностей с одной и двумя переменными. Конкретная форма непрерывных дробей типа Якоби ( J -дроби) разлагается, как в следующем уравнении, и имеет следующие соответствующие разложения в степенные ряды относительно z для некоторых конкретных, зависящих от приложения последовательностей компонентов, {ab _i } и { c _i } , где z ≠ 0 обозначает формальную переменную во втором разложении в степенной ряд, приведенном ниже: ^[21] $${\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 }}}}}}\\[4px]&=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}}}$$

Коэффициенты , обозначаемые сокращенно как j _n ≔ [ z ⁿ ] J ^[∞] ( z ) , в предыдущих уравнениях соответствуют матричным решениям уравнений: ${\displaystyle z^{n}}$ $${\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}},}$$

где j ₀ ≡ k _0,0 = 1 , j _n = k _{0, n} для n ≥ 1 , k _{r , s} = 0 если r > s , и где для всех целых чисел p , q ≥ 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 ≥ 0 (хотя на практике, когда h ≥ 2 ), мы можем определить рациональные h -е подходящие дроби к бесконечной J -дроби, J ^[∞] ( 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=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}}$$

покомпонентно через последовательности P _h ( z ) и 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}}}$$

Более того, рациональность сходящейся функции Conv _h ( z ) для всех h ≥ 2 подразумевает дополнительные конечно-разностные уравнения и свойства конгруэнтности, которым удовлетворяет последовательность j _n , и для M _h ≔ ab ₂ ⋯ ab _{h + 1 ,} если h ‖ M _{h ,} то мы имеем конгруэнтность $${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}$$

для несимволических, определенных выборов последовательностей параметров {ab _i } и { c _i } при h ≥ 2 , то есть когда эти последовательности не зависят неявно от вспомогательного параметра, такого как q , x или R, как в примерах, содержащихся в таблице ниже.

Примеры

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

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

Примеры

Квадратные числа

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

где ζ ( s) — дзета-функция Римана .

Приложения

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

• Найдите замкнутую формулу для последовательности, заданной в рекуррентном соотношении, например, чисел Фибоначчи .
• Найдите рекуррентные соотношения для последовательностей — форма производящей функции может подсказать рекуррентную формулу.
• Найдите связи между последовательностями — если производящие функции двух последовательностей имеют схожую форму, то сами последовательности могут быть связаны.
• Исследуйте асимптотическое поведение последовательностей.
• Докажите тождества, включающие последовательности.
• Решить задачи на перечисление в комбинаторике и закодировать их решения. Ладейные многочлены являются примером применения в комбинаторике.
• Оценивать бесконечные суммы.

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

Пример 1: Формула для суммы гармонических чисел

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

Самый простой случай имеет место, когда s _n = Σ^нк _=
0 a _k . Тогда мы знаем, что S ( z ) = ⁠А ( я )/1 − z⁠ для соответствующих обычных производящих функций.

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

Используя свертку с числителем, получаем , что также можно записать как $${\displaystyle {\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,,}$$ $${\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,}$$ $${\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.}$$

Пример 2: Модифицированные суммы биномиальных коэффициентов и биномиальное преобразование

В качестве другого примера использования генерирующих функций для связи последовательностей и манипулирования суммами, для произвольной последовательности ⟨ f _n ⟩ мы определяем две последовательности сумм для всех n ≥ 0 и пытаемся выразить вторые суммы через первые. Мы предлагаем подход с помощью генерирующих функций. $${\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{\tilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}}$$

Сначала мы используем биномиальное преобразование , чтобы записать производящую функцию для первой суммы как $${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).}$$

Поскольку производящая функция для последовательности ⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩ задается выражением, мы можем записать производящую функцию для второй суммы, определенной выше, в виде $${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}$$ $${\displaystyle {\tilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}}\right)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}}\right)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}}\right)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}}\right).}$$

В частности, мы можем записать эту модифицированную функцию генерации суммы в виде для a ( z ) = 6(1 − 3 z ) ³ , b ( z ) = 18(1 − 3 z ) ³ , c ( z ) = 9(1 − 3 z ) ³ и d ( z ) = (1 − 3 z ) ³ , где (1 − 3 z ) ³ = 1 − 9 z + 27 z ² − 27 z ³ . $${\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),}$$

Наконец, отсюда следует, что мы можем выразить вторые суммы через первые суммы в следующем виде: $${\displaystyle {\begin{aligned}{\tilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n}\right)\\[4px]&=(n+1)(n+2)(n+3)s_{n}-9n(n+1)(n+2)s_{n-1}+27(n-1)n(n+1)s_{n-2}-(n-2)(n-1)ns_{n-3}.\end{aligned}}}$$

Пример 3: Генерация функций для взаимно рекурсивных последовательностей

В этом примере мы переформулируем пример производящей функции, приведенный в разделе 7.3 книги Concrete Mathematics (см. также раздел 7.1 той же ссылки для красивых картинок рядов производящих функций). В частности, предположим, что мы ищем общее число способов (обозначенное U _n ) замостить прямоугольник 3 на n неотмеченными костяшками домино 2 на 1. Пусть вспомогательная последовательность V _n определена как число способов покрыть прямоугольник 3 на n минус угловая часть полного прямоугольника. Мы пытаемся использовать эти определения, чтобы дать формулу замкнутой формы для U _{n ,} не разбивая это определение далее для обработки случаев вертикальных и горизонтальных костяшек домино. Обратите внимание, что обычные производящие функции для наших двух последовательностей соответствуют рядам: $${\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}}$$

Если мы рассмотрим возможные конфигурации, которые могут быть заданы, начиная с левого края прямоугольника 3 на n , мы сможем выразить следующие взаимозависимые или взаимно рекурсивные рекуррентные соотношения для наших двух последовательностей, когда n ≥ 2, определенных выше, где U ₀ = 1 , U ₁ = 0 , V ₀ = 0 и V ₁ = 1 : $${\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}}$$

Поскольку для всех целых чисел m ≥ 0 производящие функции со смещенным индексом удовлетворяют ^{[примечание 1],} мы можем использовать начальные условия, указанные выше, и два предыдущих рекуррентных соотношения, чтобы увидеть, что у нас есть следующие два уравнения, связывающие производящие функции для этих последовательностей, заданных следующим образом : затем, решая систему уравнений (и это особый трюк нашего метода), следует, что $${\displaystyle z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,}$$ $${\displaystyle {\begin{aligned}U(z)&=2zV(z)+z^{2}U(z)+1\\V(z)&=zU(z)+z^{2}V(z)={\frac {z}{1-z^{2}}}U(z),\end{aligned}}}$$ $${\displaystyle U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}}\right)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}}\right)z^{2}}}.}$$

Таким образом, выполняя алгебраические упрощения последовательности, полученной в результате разложения второй дроби производящей функции в предыдущем уравнении, мы находим, что U _{2 n + 1} ≡ 0 и что для всех целых чисел n ≥ 0. Мы также отмечаем, что тот же метод смещенной производящей функции, примененный к рекуррентности второго порядка для чисел Фибоначчи, является прототипическим примером использования производящих функций для решения рекуррентных соотношений с одной переменной, который уже рассматривался или, по крайней мере, намекался в подразделе о рациональных функциях, приведенном выше. $${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,}$$

Свертка (произведения Коши)

Дискретная свертка членов двух формальных степенных рядов превращает произведение производящих функций в производящую функцию, перечисляющую свёрнутую сумму членов исходной последовательности (см. произведение Коши ).

1. Рассмотрим A ( z ) и B ( z ) — обычные производящие функции. $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k}}}$$
2. Рассмотрим A ( z ) и B ( z ) — экспоненциальные производящие функции. $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}}\right]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k}}$$
3. Рассмотрим тройную свёрнутую последовательность, полученную в результате произведения трёх обычных производящих функций $${\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l}}$$
4. Рассмотрим m -кратную свертку последовательности с самой собой для некоторого положительного целого числа m ≥ 1 (см. пример ниже для применения) $${\displaystyle C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}}$$

Умножение производящих функций или свертка их базовых последовательностей может соответствовать понятию независимых событий в определенных сценариях подсчета и вероятности. Например, если мы примем соглашение об обозначениях, что функция производства вероятности , или pgf , случайной величины Z обозначается как G _Z ( z ) , то мы можем показать, что для любых двух случайных величин ^[23], если X и Y независимы. Аналогично, количество способов заплатить n ≥ 0 центов в монетах достоинством в наборе {1, 5, 10, 25, 50} (т. е. в пенни, никелях, даймах, четвертаках и полдолларах соответственно) генерируется произведением и, более того, если мы позволим платить n центов монетами любого положительного целого достоинства, мы придем к генерации для количества таких комбинаций сдачи, генерируемых функцией производства функции распределения , расширенной бесконечным произведением символов q -Похгаммера $${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}$$ $${\displaystyle C(z)={\frac {1}{1-z}}{\frac {1}{1-z^{5}}}{\frac {1}{1-z^{10}}}{\frac {1}{1-z^{25}}}{\frac {1}{1-z^{50}}},}$$ $${\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n}\right)^{-1}\,.}$$

Пример: Производящая функция для каталонских чисел

Пример, в котором свертки производящих функций полезны, позволяет нам решить для конкретной функции замкнутой формы, представляющей обычную производящую функцию для чисел Каталана , C _n . В частности, эта последовательность имеет комбинаторную интерпретацию как число способов вставить скобки в произведение x ₀ · x ₁ ·⋯· x _n так, чтобы порядок умножения был полностью определен. Например, C ₂ = 2 , что соответствует двум выражениям x ₀ · ( x ₁ · x ₂ ) и ( x ₀ · x ₁ ) · x ₂ . Из этого следует, что последовательность удовлетворяет рекуррентному соотношению, заданному и, таким образом, имеет соответствующую свернутую производящую функцию, C ( z ) , удовлетворяющую $${\displaystyle C_{n}=\sum _{k=0}^{n-1}C_{k}C_{n-1-k}+\delta _{n,0}=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdots +C_{n-1}C_{0}+\delta _{n,0}\,,\quad n\geq 0\,,}$$ $${\displaystyle C(z)=z\cdot C(z)^{2}+1\,.}$$

Поскольку C (0) = 1 ≠ ∞ , мы приходим к формуле для этой производящей функции, заданной как $${\displaystyle C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.}$$

Обратите внимание, что первое уравнение, неявно определяющее C ( z ) выше, подразумевает то, что затем приводит к другому «простому» (по форме) разложению этой производящей функции в цепную дробь. $${\displaystyle C(z)={\frac {1}{1-z\cdot C(z)}}\,,}$$

Пример: остовные деревья вееров и свертки сверток

Веер порядка n определяется как граф на вершинах {0, 1, ..., n } с 2 n − 1 ребрами, соединенными в соответствии со следующими правилами: вершина 0 соединена одним ребром с каждой из других n вершин, а вершина соединена одним ребром со следующей вершиной k + 1 для всех 1 ≤ k < n . ^[24] Существует один веер порядка один, три веера порядка два, восемь вееров порядка три и т. д. Остовное дерево — это подграф графа, который содержит все исходные вершины и который содержит достаточно ребер, чтобы сделать этот подграф связным, но не так много ребер, чтобы в подграфе был цикл. Мы спрашиваем, сколько остовных деревьев f _n веера порядка n возможно для каждого n ≥ 1 . ${\displaystyle k}$

В качестве наблюдения мы можем подойти к вопросу, подсчитав количество способов соединения смежных множеств вершин. Например, когда n = 4 , мы имеем, что f ₄ = 4 + 3 · 1 + 2 · 2 + 1 · 3 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 = 21 , что является суммой по m -кратным сверткам последовательности g _n = n = [ z ⁿ ] ⁠з/(1 − z ) ²⁠ для m ≔ 1, 2, 3, 4. В более общем виде мы можем записать формулу для этой последовательности, из которой мы видим, что обычная производящая функция для этой последовательности задается следующей суммой сверток, из которой мы можем извлечь точную формулу для последовательности, взяв разложение в частичную дробь последней производящей функции. $${\displaystyle f_{n}=\sum _{m>0}\sum _{\scriptstyle k_{1}+k_{2}+\cdots +k_{m}=n \atop \scriptstyle k_{1},k_{2},\ldots ,k_{m}>0}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}\,,}$$ $${\displaystyle F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,,}$$

Неявные производящие функции и формула обращения Лагранжа

Часто встречаются производящие функции, заданные функциональным уравнением, а не явной спецификацией. Например, производящая функция T(z) для числа бинарных деревьев на n узлах (включая листья) удовлетворяет

$${\displaystyle T(z)=z\left(1+T(z)^{2}\right)}$$

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

Формула обращения Лагранжа  —  Пусть — формальный степенной ряд с ненулевым постоянным членом. Тогда функциональное уравнение допускает единственное решение в , которое удовлетворяет ${\textstyle \phi (z)\in C[[z]]}$ $${\displaystyle T(z)=z\phi (T(z))}$$ ${\textstyle T(z)\in C[[z]]}$

${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n}}$

где запись возвращает коэффициент в . ${\displaystyle [z^{n}]F(z)}$ ${\displaystyle z^{n}}$ ${\displaystyle F(z)}$

Применяя приведенную выше теорему к нашему функциональному уравнению, получаем (с ): ${\textstyle \phi (z)=1+z^{2}}$

$${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}}$$

С помощью биномиального расширения теоремы для четного формула возвращает . Это ожидаемо, поскольку можно доказать, что количество листьев бинарного дерева на единицу больше количества его внутренних узлов, поэтому общая сумма всегда должна быть нечетным числом. Однако для нечетного мы получаем ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$

${\displaystyle [z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2}}}}$

Выражение станет намного аккуратнее, если мы оставим число внутренних узлов: Теперь выражение станет просто ^-м каталонским числом. ${\displaystyle n}$ ${\displaystyle n}$

Введение свободного параметра (метод змеиного масла)

Иногда сумма s _n сложна, и ее не всегда легко оценить. Метод «Свободных параметров» — это еще один метод (названный Х. Вилфом «змеиным маслом») оценки этих сумм.

Оба метода, обсуждавшиеся до сих пор, имеют n в качестве предела в суммировании. Когда n не появляется явно в суммировании, мы можем рассматривать n как «свободный» параметр и рассматривать s _n как коэффициент F ( z ) = Σ s _n z ⁿ , изменять порядок суммирования по n и k и пытаться вычислить внутреннюю сумму.

Например, если мы хотим вычислить, мы можем рассматривать n как «свободный» параметр и задать $${\displaystyle s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,,}$$ $${\displaystyle F(z)=\sum _{n=0}^{\infty }{\left(\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\right)}z^{n}\,.}$$

Взаимозаменяющее суммирование («змеиное масло») дает $${\displaystyle F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,.}$$

Теперь внутренняя сумма равна ⁠z ^{м + 2 к}/(1 − z ) ^{m + 2 k + 1}⁠ . Таким образом $${\displaystyle {\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}}\right)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned}}}$$

Тогда мы получаем $${\displaystyle s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{\text{for }}m\geq 1\,,\\{}[n=0]&{\text{for }}m=0\,.\end{cases}}}$$

Полезно снова использовать тот же метод для суммы, но на этот раз взять m в качестве свободного параметра вместо n . Таким образом, мы устанавливаем $${\displaystyle G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}\right)z^{m}\,.}$$

Взаимозаменяющее суммирование («змеиное масло») дает $${\displaystyle G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,.}$$

Теперь внутренняя сумма равна (1 + z ) ^{n + k} . Таким образом $${\displaystyle {\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}}\right)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}}\right)^{k}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned}}}$$

Таким образом, для m ≥ 1 получаем то же самое, что и раньше. $${\displaystyle s_{n}=\left[z^{m}\right]z(1+z)^{n-1}=\left[z^{m-1}\right](1+z)^{n-1}={\binom {n-1}{m-1}}\,,}$$

Производящие функции доказывают сравнения

Мы говорим, что две производящие функции (степенные ряды) сравнимы по модулю m , что записывается как A ( z ) ≡ B ( z ) (mod m ), если их коэффициенты сравнимы по модулю m для всех n ≥ 0 , то есть, a _n ≡ b _n (mod m ) для всех соответствующих случаев целых чисел n (обратите внимание, что нам не нужно предполагать, что m здесь является целым числом — оно вполне может быть полиномиальным по некоторому неопределенному x , например). Если «более простая» производящая функция правой стороны, B ( z ) , является рациональной функцией z , то форма этой последовательности предполагает, что последовательность в конечном итоге является периодической по модулю фиксированных частных случаев целочисленных чисел m ≥ 2 . Например, мы можем доказать, что числа Эйлера , удовлетворяют следующему сравнению по модулю 3: ^[25] $${\displaystyle \langle E_{n}\rangle =\langle 1,1,5,61,1385,\ldots \rangle \longmapsto \langle 1,1,2,1,2,1,2,\ldots \rangle {\pmod {3}}\,,}$$ $${\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.}$$

Один полезный метод получения сравнений для последовательностей, перечисленных специальными производящими функциями по модулю любых целых чисел (т.е. не только простых степеней p ^k ), приведен в разделе о представлениях непрерывных дробей (даже несходящихся) обычных производящих функций с помощью J -дробей выше. Мы приводим один конкретный результат, связанный с генерацией рядов, расширенный посредством представления непрерывной дробью из « Лекций Ландо по производящим функциям» следующим образом:

Теорема: сравнения для рядов, порожденных разложениями цепных дробей  —  Предположим, что производящая функция A ( z ) представлена ​​бесконечной цепной дробью вида и что A _p ( z ) обозначает p -ю подходящую дробь к этому разложению цепной дроби, определенную так, что a _n = [ z ⁿ ] A _p ( z ) для всех 0 ≤ n < 2 p . Тогда: $${\displaystyle A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots }}}}}}}}$$

1. функция A _p ( z ) рациональна для всех p ≥ 2 , где мы предполагаем, что выполняется один из критериев делимости p | p ₁ , p ₁ p ₂ , p ₁ p ₂ p _{3 , то есть} p | p ₁ p ₂ ⋯ p _k для некоторого k ≥ 1 ; и
2. если целое число p делит произведение p ₁ p ₂ ⋯ p _k , то мы имеем A ( z ) ≡ A _k ( z ) (mod p ) .

Производящие функции также имеют другие применения в доказательстве сравнений для их коэффициентов. Мы приводим следующие два конкретных примера вывода сравнений специального случая для чисел Стирлинга первого рода и для функции статистической суммы p ( n ), которые показывают универсальность производящих функций в решении проблем, связанных с целочисленными последовательностями .

Числа Стерлинга по модулю малых целых чисел

Основная статья о числах Стирлинга, полученных с помощью конечных произведений $${\displaystyle S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,,}$$

дает обзор сравнений для этих чисел, полученных строго из свойств их производящей функции, как в разделе 4.6 справочника Вилфа Generatingfunctionology . Мы повторяем основной аргумент и замечаем, что при сокращении по модулю 2 эти конечные производящие функции произведения удовлетворяют

$${\displaystyle S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}}\right\rceil }(x+1)^{\left\lfloor {\frac {n}{2}}\right\rfloor }\,,}$$

что означает, что четность этих чисел Стерлинга совпадает с четностью биномиального коэффициента

$${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}}\right\rfloor }{k-\left\lceil {\frac {n}{2}}\right\rceil }}{\pmod {2}}\,,}$$

и, следовательно, показывает, что [^н
_к] четно, когда k < ⌊ ⁠н/2⁠ ⌋ .

Аналогично мы можем сократить правые произведения, определяющие функции генерации чисел Стирлинга по модулю 3, чтобы получить немного более сложные выражения, при условии, что $${\displaystyle {\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}}\right\rceil }(x+1)^{\left\lceil {\frac {n-1}{3}}\right\rceil }(x+2)^{\left\lfloor {\frac {n}{3}}\right\rfloor }\right)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}}\right\rceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}}\right\rfloor \\m-k-\left\lceil {\frac {n}{3}}\right\rceil \end{pmatrix}}\times 2^{\left\lceil {\frac {n}{3}}\right\rceil +\left\lfloor {\frac {n}{3}}\right\rfloor -(m-k)}&&{\pmod {3}}\,.\end{aligned}}}$$

Сравнения для функции распределения

В этом примере мы привлекаем часть машин бесконечных произведений, чьи разложения в степенные ряды генерируют разложения многих специальных функций и перечисляют функции статистической суммы. В частности, мы напоминаем, что функция статистической суммы p ( n ) генерируется обратным бесконечным произведением q -символа Похгаммера (или произведением z -символа Похгаммера, в зависимости от случая), заданным как $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z\right)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}}$$

Эта функция распределения удовлетворяет многим известным свойствам конгруэнтности , которые, в частности, включают следующие результаты, хотя все еще остается много открытых вопросов о формах связанных целочисленных конгруэнтностей для функции: ^[26] $${\displaystyle {\begin{aligned}p(5m+4)&\equiv 0{\pmod {5}}\\p(7m+5)&\equiv 0{\pmod {7}}\\p(11m+6)&\equiv 0{\pmod {11}}\\p(25m+24)&\equiv 0{\pmod {5^{2}}}\,.\end{aligned}}}$$

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

Во-первых, мы замечаем, что в функции, производящей биномиальные коэффициенты, все коэффициенты делятся на 5, за исключением тех, которые соответствуют степеням 1, z ⁵ , z ¹⁰ , ... и, более того, в этих случаях остаток коэффициента равен 1 по модулю 5. Таким образом, или эквивалентно Из этого следует, что $${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}$$ $${\displaystyle {\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,}$$ $${\displaystyle {\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.}$$ $${\displaystyle {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\left(1-z^{15}\right)\cdots }{\left((1-z)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots \right)^{5}}}\equiv 1{\pmod {5}}\,.}$$

Используя его бесконечное разложение в произведение, можно показать, что коэффициент при z ^{5 m + 5} в z · ((1 − z )(1 − z ² )⋯) ⁴ делится на 5 для всех m . ^[27] Наконец, поскольку мы можем приравнять коэффициенты при z ^{5 m + 5} в предыдущих уравнениях, чтобы доказать наш желаемый результат сравнения, а именно, что p (5 m + 4) ≡ 0 (mod 5) для всех m ≥ 0 . $${\displaystyle z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(1-z\right)\left(1-z^{2}\right)\cdots }}=z\cdot \left((1-z)\left(1-z^{2}\right)\cdots \right)^{4}\times {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(\left(1-z\right)\left(1-z^{2}\right)\cdots \right)^{5}}}\,,}$$ $${\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }p(n-1)z^{n}&={\frac {z}{(1-z)\left(1-z^{2}\right)\cdots }}\\[6px]&=z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{(1-z)\left(1-z^{2}\right)\cdots }}\times \left(1+z^{5}+z^{10}+\cdots \right)\left(1+z^{10}+z^{20}+\cdots \right)\cdots \end{aligned}}}$$

Преобразования производящих функций

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

Преобразования производящей функции могут вступать в игру, когда мы пытаемся выразить производящую функцию для сумм $${\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},}$$

в форме S ( z ) = g ( z ) A ( f ( z )) с участием исходной функции генерации последовательности. Например, если суммы являются , то функция генерации для модифицированных выражений суммы задается выражением ^[28] (см. также биномиальное преобразование и преобразование Стирлинга ). $${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}$$ $${\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)}$$

Существуют также интегральные формулы для преобразования между OGF последовательности, F ( z ) , и ее экспоненциальной производящей функцией, или EGF, F̂ ( z ) , и наоборот, заданные как $${\displaystyle {\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta }\right)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned}}}$$

при условии, что эти интегралы сходятся для соответствующих значений z .

Таблицы специальных производящих функций

Первоначальный список специальных математических рядов можно найти здесь . Ряд полезных и специальных функций генерации последовательностей можно найти в разделах 5.4 и 7.4 книги Concrete Mathematics и в разделе 2.5 книги Wilf's Generatingfunctionology . Другие специальные функции генерации, заслуживающие внимания, включают записи в следующей таблице, которая ни в коем случае не является полной. ^[29]

Смотрите также

• Функция, генерирующая момент
• Функция генерации вероятности
• Производящая функция преобразования
• Теорема взаимности Стэнли
• Целочисленное разбиение
• Комбинаторные принципы
• Циклическое просеивание
• Z-преобразование
• Умбральное исчисление
• Монеты в фонтане

Примечания

1. Кстати, у нас также есть соответствующая формула при m < 0, заданная как $${\displaystyle \sum _{n=0}^{\infty }g_{n+m}z^{n}={\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}\,.}$$

Ссылки

1. Этот альтернативный термин уже можно найти в EN Gilbert (1956), «Перечисление маркированных графов», Canadian Journal of Mathematics 3, стр. 405–411, но до 2000 года его использование было редким; с тех пор оно, по-видимому, увеличивается.
2. Кнут, Дональд Э. (1997). "§1.2.9 Генерирующие функции". Фундаментальные алгоритмы . Искусство программирования . Том 1 (3-е изд.). Эддисон-Уэсли. ISBN 0-201-89683-4.
3. Флажоле и Седжвик 2009, стр. 95
4. "Идентификация ряда Ламберта". Math Overflow . 2017.
5. Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Undergraduate Texts in Mathematics, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, MR  0434929, Zbl  0335.10001стр.42–43
6. Вильф 1994, стр. 56
7. Вильф 1994, стр. 59
8. Харди, GH; Райт, EM; Хит-Браун, DR; Сильверман, JH (2008). Введение в теорию чисел (6-е изд.). Oxford University Press. стр. 339. ISBN 9780199219858.
9. Кнут, Д. Э. (1992). «Сверточные многочлены». Mathematica J. 2 : 67–78. arXiv : math/9207221 . Bibcode : 1992math......7221K.
10. Spivey, Michael Z. (2007). «Комбинаторные суммы и конечные разности». Discrete Math . 307 (24): 3130–3146. doi : 10.1016/j.disc.2007.03.052 . MR  2370116.
11. Матар, Р. Дж. (2012). «Еще одна таблица интегралов». arXiv : 1207.5845 [math.CA].v4 экв. (0,4)
12. Грэм, Кнут и Паташник 1994, Таблица 265 в §6.1 для тождеств конечной суммы, включающих треугольники чисел Стирлинга.
13. Ландо 2003, §2.4
14. Пример из Stanley, Richard P.; Fomin, Sergey (1997). "§6.3". Enumerative Combinatorics: Volume 2. Cambridge Studies in Advanced Mathematics. Vol. 62. Cambridge University Press. ISBN 978-0-521-78987-5.
15. Кнут 1997, §1.2.9
16. Решение Грэма, Кнута и Паташника 1994, стр. 569, упражнение 7.36
17. Флажоле и Седжвик 2009, §B.4
18. Шнайдер, К. (2007). «Символическое суммирование помогает комбинаторике». Sém. Lothar. Combin . 56 : 1–36.
19. См. использование этих терминов в Graham, Knuth & Patashnik 1994, §7.4 о специальных функциях генерации последовательностей.
20. Good, IJ (1986). «О применении симметричных распределений Дирихле и их смесей к таблицам сопряженности». Annals of Statistics . 4 (6): 1159–1189. doi : 10.1214/aos/1176343649 .
21. Более полную информацию о свойствах J -дробь см.:
    • Флажоле, П. (1980). «Комбинаторные аспекты непрерывных дробей» (PDF) . Дискретная математика . 32 (2): 125–161. doi :10.1016/0012-365X(80)90050-3.
    • Уолл, Х.С. (2018) [1948]. Аналитическая теория цепных дробей. Дувр. ISBN 978-0-486-83044-5.
22. Смотрите следующие статьи:
    • Шмидт, Макси Д. (2016). «Непрерывные дроби для функций генерации квадратных рядов». arXiv : 1612.02778 [math.NT].
    • — (2017). «Цепные дроби типа Якоби для обычных производящих функций обобщенных факториальных функций». Журнал целочисленных последовательностей . 20. arXiv : 1610.09691 . 17.3.4 .
    • — (2017). «Цепные дроби типа Якоби и сравнения для биномиальных коэффициентов по модулю целых чисел h ≥ 2». arXiv : 1702.01374 [math.CO].
23. Грэм, Кнут и Паташник 1994, §8.3
24. Graham, Knuth & Patashnik 1994, Пример 6 в §7.3 для другого метода и полной настройки этой проблемы с использованием производящих функций. Этот более «замысловатый» подход приведен в Разделе 7.5 той же ссылки.
25. Ландо 2003, §5
26. Харди и др. 2008, §19.12
27. Харди, Г. Х.; Райт, Э. М. Введение в теорию чисел .стр.288, т.361
28. Грэм, Кнут и Паташник 1994, стр. 535, упражнение 5.71
29. См. также 1031 производящую функцию, найденную у Плуффа, Саймона (1992). Approximations de séries génératrices et quelques гипотез [ Аппроксимации производящих функций и несколько гипотез ] (магистратура) (на французском языке). Университет Квебека в Монреале. arXiv : 0911.4975 .

Цитаты

• Айгнер, Мартин (2007). Курс перечисления. Graduate Texts in Mathematics. Том 238. Springer. ISBN 978-3-540-39035-0.
• Дубиле, Питер; Рота, Джан-Карло ; Стэнли, Ричард (1972). «Об основах комбинаторной теории. VI. Идея производящей функции». Труды Шестого симпозиума в Беркли по математической статистике и вероятности . 2 : 267–318. Zbl  0267.05002.Перепечатано в Rota, Gian-Carlo (1975). "3. Идея производящей функции". Конечно-операторное исчисление . В сотрудничестве с P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko и R. Stanley . Academic Press. стр. 83–134. ISBN 0-12-596650-4. Збл  0328.05007.
• Флажоле, Филипп ; Седжвик, Роберт (2009). Аналитическая комбинаторика . Издательство Кембриджского университета. ISBN 978-0-521-89806-5. Збл  1165.05001.
• Goulden, Ian P.; Jackson, David M. (2004). Комбинаторное перечисление . Dover Publications . ISBN 978-0486435978.
• Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1994). «Глава 7: Генерирующие функции». Конкретная математика. Основа компьютерной науки (2-е изд.). Addison-Wesley. стр. 320–380. ISBN 0-201-55802-5. Збл  0836.00001.
• Ландо, Сергей К. (2003). Лекции по производящим функциям. Американское математическое общество. ISBN 978-0-8218-3481-7.
• Wilf, Herbert S. (1994). Generatingfunctionology (2-е изд.). Academic Press. ISBN 0-12-751956-4. Збл  0831.05001.

Внешние ссылки

• «Введение в обыкновенные производящие функции» Майка Заброцкого, Йоркский университет, математика и статистика
• «Производящая функция», Энциклопедия математики , EMS Press , 2001 [1994]
• Генерирующие функции, индексы мощности и размена монет на cut-the-knot
• «Производящие функции» Эда Пегга-младшего , Wolfram Demonstrations Project , 2007.