Генерирующая функция

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

Если 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)

Экспоненциальная производящая функция последовательности 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 равен

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

Коэффициенты ряда Ламберта в разложениях по степеням

$${\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)}$$

для целых чисел n ≥ 1 связаны суммой делителей

$${\displaystyle b_{n}=\sum _{d|n}a_{d}.}$$

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

В ряду Ламберта индекс n начинается с 1, а не с 0, поскольку в противном случае первый член был бы неопределенным.

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

Ряд Белла последовательности a n _{представляет} собой выражение как через неопределенное x, так и через простое число p и определяется формулой ^[4]

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

Производящие функции ряда Дирихле (ПФР)

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

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

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

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

Если n является характером Дирихле _, то его производящая функция ряда Дирихле называется L -рядом Дирихле . У нас также есть связь между парой коэффициентов в приведенных выше разложениях в ряд Ламберта и их DGF. А именно, мы можем доказать, что

$${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}$$

если и только если

$${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),}$$

где ζ ( s ) – дзета-функция Римана . ^[7]

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

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

$${\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). . Более того, другого степенного ряда с этим свойством быть не может. Таким образом, левая часть обозначает мультипликативную величину, обратную 1 - x в кольце степенных рядов.

Из этого легко выводятся выражения для обычной производящей функции других последовательностей. Например, замена ^x → ax дает производящую функцию для геометрической последовательности 1, a , a2 , a3 ^, ... для любой константы 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 , x ³ , x ⁵ , ... ) получаем производящую функцию

$${\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 , что ^{[8] [9]}

$${\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}}},}$$

мы можем применить известное тождество конечной суммы, включающее числа Стирлинга , чтобы получить, что ^[10]

$${\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}}}.}$$

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

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

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

$${\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},}$$

является алгебраическим . Например, если мы позволим ^[12]

$${\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}}}.}$$

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

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

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

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

$${\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 - х(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 = exp2 πи/аобозначает a- й примитивный корень из единицы . Тогда в качестве применения дискретного преобразования Фурье имеем формулу ^[13]

$${\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 раз — генерируется тождеством ^[14]

$${\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}).}$$

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

Определения

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

$${\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 -рекурсивными последовательностями и голономными производящими функциями

Инструменты для обработки и работы с 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 (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, тогда

$${\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 }}}}.}$$

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

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

Например, поскольку (1 + x ) ⁿ — обычная производящая функция для биномиальных коэффициентов при фиксированном n , можно запросить двумерную производящую функцию, которая генерирует биномиальные коэффициенты (^н
_к) для всех k и n . Для этого рассмотрим саму (1 + x ) ⁿ как последовательность в n и найдем производящую функцию в y , которая имеет эти значения последовательности в качестве коэффициентов. ^{Поскольку} производящая функция для 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 -дроби соответственно), чьи h -ые рациональные подходящие дроби представляют собой степенные ряды с точностью 2 h -порядка , являются еще одним способом выражения обычно расходящихся обычных производящих функций для множество специальных одно- и двухмерных последовательностей. Конкретная форма цепных дробей типа Якоби ( J -дроби ) разлагается, как в следующем уравнении, и имеет следующие соответствующие разложения в степенные ряды по z для некоторых конкретных, зависящих от приложения последовательностей компонентов, {ab _i } и { c _i } , где z ≠ 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 }}}}}}\\[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 -х сходящихся функций

Для 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 _х , тогда у нас есть соответствие

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

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

Примеры

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

Радиусы сходимости этих рядов, соответствующие приведенному выше определению 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}}$$

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

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

$${\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 ) ≡ σ ₀ ( 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}}}.}$$

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

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

Производящая функция ряда Дирихле

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

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

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

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

где ζ ( s ) — дзета-функция Римана , имеет обычную производящую функцию:

$${\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 }$$

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

Многомерные производящие функции возникают на практике при вычислении количества таблиц сопряженности неотрицательных целых чисел с заданными суммами строк и столбцов. Предположим, что в таблице имеется r строк и c столбцов; суммы строк равны t ₁ , t ₂ ... t _r , а суммы столбцов равны s ₁ , s ₂ ... s _c . Тогда, по мнению И. Дж. Гуда , ^[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}}}.}$$

В двумерном случае примеры неполиномиальной двойной суммы так называемых « двойных » или « супер » производящих функций вида

$${\displaystyle G(w,z):=\sum _{m,n\geq 0}g_{m,n}w^{m}z^{n}}$$

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

$${\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}}}$$

Приложения

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

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

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

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

Например, мы можем манипулировать

$${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$

Нк ₌ 1 +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 ⟩ мы определяем две последовательности сумм

$${\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}}}$$

n ≥ 0

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

$${\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).}$$

В частности, мы можем записать эту модифицированную функцию, производящую сумму, в виде

$${\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),}$$

а ( z ) знак равно 6 (1 - 3 z ) ³б ( 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 {\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 книги « Конкретная математика» (красивые изображения рядов производящих функций см. также в разделе 7.1 того же справочника). В частности, предположим, что мы ищем общее количество способов (обозначаемых Un ) замостить прямоугольник размером 3 на n немаркированными кусочками домино _{размером} 2 на 1. Пусть вспомогательная последовательность V _n определяется как количество способов покрытия секции прямоугольника минус углы размером 3хn в полном прямоугольнике. Мы стремимся использовать эти определения, чтобы дать формулу замкнутой формы для Un _, не разбивая это определение дальше для рассмотрения случаев вертикального и горизонтального домино. Обратите внимание, что обычные производящие функции для наших двух последовательностей соответствуют ряду

$${\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 и что

$${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,}$$

n ≥ 0рекуррентностичисел Фибоначчирациональным функции,

Свертка (продукты Коши)

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

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 ) , тогда мы можем показать, что для любых двух случайных величин ^[22]

$${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}$$

XYn ≥ 0

$${\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}}},}$$

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

$${\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 ₂ . Отсюда следует, что последовательность удовлетворяет рекуррентному соотношению, заданному формулой

$${\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\,,}$$

C ( z )

$${\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 . ^[23] Имеется один вентилятор первого порядка, три вентилятора второго порядка, восемь вентиляторов третьего порядка и так далее. Опорное дерево — это подграф графа, который содержит все исходные вершины и который содержит достаточно ребер, чтобы сделать этот подграф связным, но не так много ребер, чтобы в подграфе существовал цикл. Мы спрашиваем, сколько остовных деревьев f _n веера порядка n возможно для каждого n ≥ 1 . ${\displaystyle k}$

В качестве наблюдения мы можем подойти к этому вопросу, подсчитав количество способов соединения соседних наборов вершин. Например, когда n = 4 , мы имеем, что f ₄ = 4 + 3 · 1 + 2 · 2 + 1 · 3 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 = 21 , что является суммой по m -кратным сверткам последовательности g _n = n = [ z ⁿ ]я/(1 - z ) ²для м ≔ 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}}$

где обозначение возвращает коэффициент in . ${\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 , и попытайтесь вычислить внутреннюю сумму.

Например, если мы хотим вычислить

$${\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}\,,}$$

n

$${\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}}\,.}$$

Теперь внутренняя сумма равназ ^{м + 2 к}/(1 - z ) ^{м + 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}}}$$

Таким образом мы получаем

$${\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 ≥ 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 . Например, мы можем доказать, что числа Эйлера ,

$${\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}}\,,}$$

^[24]

$${\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.}$$

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

Теорема: сравнения для рядов, порожденных разложением цепных дробей  .  Предположим, что производящая функция A ( z ) представлена ​​бесконечной цепной дробью вида

$${\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 }}}}}}}}$$

и что A _p ( z ) обозначает p -ю подходящую дробь к этому разложению в цепную дробь, определенную так, что a _n = [ z ⁿ ] A _p ( z ) для всех 0 ≤ n < 2 p . Затем:

1. функция A _p ( z ) рациональна для всех p ≥ 2 , где мы предполагаем, что один из критериев делимости p | p ₁ , p ₁ p ₂ , p ₁ p ₂ p ₃ встречается, то есть 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 стандартного справочника Уилфа « Генерирующая функция» . Мы повторяем основной аргумент и замечаем, что при уменьшении по модулю 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}}}$$

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

$${\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}}}$$

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

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

$${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}$$

1, z ⁵ , z ¹⁰ , ...

$${\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}}\,.}$$

Используя бесконечное разложение произведения

$${\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}}}\,,}$$

z ^{5 m + 5}z · ((1 - z )(1 - z ² )⋯) ⁴m^[26]

$${\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}}}$$

z ^{5 m + 5}p (5 m + 4) ≡ 0 (mod 5)m ≥ 0

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

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

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

$${\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},}$$

в форме S ( z ) = g ( z ) A ( f ( z )) с использованием производящей функции исходной последовательности. Например, если суммы

$${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}$$

^[27]

$${\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 .

Другие приложения

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

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

Другие генерирующие функции

Примеры

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

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

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

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

Полиномы свертки

Статья Кнута под названием « Полиномы свертки » ^[28] определяет обобщенный класс последовательностей полиномов свертки с помощью их специальных производящих функций вида

$${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$

FF (0) = 1

Мы говорим, что семейство многочленов 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}}}$$

Для фиксированного ненулевого параметра мы модифицировали производящие функции для этих полиномиальных последовательностей свертки, заданных формулой ${\displaystyle t\in \mathbb {C} }$

$${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$

𝓕 _t ( z )функциональным уравнением𝓕 _t ( z ) знак равно F ( x 𝓕 _t ( z ) ^t )⟨ f _n ( x ) ⟩⟨ g _n ( x ) ⟩F ( z ) ^xG ( z ) ^xt

$${\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 ) , полиномы Лагерра и свертку Стирлинга. полиномы .

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

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

Цитаты

• Айгнер, Мартин (2007). Курс счета. Тексты для аспирантов по математике. Том. 238. Спрингер. ISBN 978-3-540-39035-0.
• Дубилет, Питер; Рота, Джан-Карло ; Стэнли, Ричард (1972). «Об основах комбинаторной теории. VI. Идея производящей функции». Труды шестого симпозиума Беркли по математической статистике и теории вероятностей . 2 : 267–318. Збл  0267.05002.Перепечатано в Роте, Джан-Карло (1975). «3. Идея производящей функции». Конечное операторное исчисление . При сотрудничестве П. Дубилета, К. Грина, Д. Каханера, А. Одлизко и Р. Стэнли . Академическая пресса. стр. 83–134. ISBN 0-12-596650-4. Збл  0328.05007.
• Флажоле, Филипп ; Седжвик, Роберт (2009). Аналитическая комбинаторика . Издательство Кембриджского университета. ISBN 978-0-521-89806-5. Збл  1165.05001.
• Гулден, Ян П.; Джексон, Дэвид М. (2004). Комбинаторное перечисление . Дуврские публикации . ISBN 978-0486435978.
• Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1994). «Глава 7: Генерирующие функции». Конкретная математика. Основы информатики (2-е изд.). Аддисон-Уэсли. стр. 320–380. ISBN 0-201-55802-5. Збл  0836.00001.
• Ландо, Сергей К. (2003). Лекции по производящим функциям. Американское математическое общество. ISBN 978-0-8218-3481-7.
• Уилф, Герберт С. (1994). Генерирующая функционалология (2-е изд.). Академическая пресса. ISBN 0-12-751956-4. Збл  0831.05001.

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

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