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

Эта статья о производящих функциях в математике. О производящих функциях в классической механике см. Производящая функция (физика) . Информацию о генераторах в компьютерном программировании см. в разделе Генератор (компьютерное программирование) . Информацию о производящей функции момента в статистике см. в разделе « Производящая функция момента» .

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще одним преимуществом экспоненциальных производящих функций является то, что они полезны при переносе линейных рекуррентных соотношений в область дифференциальных уравнений . Например, возьмем последовательность Фибоначчи { f _n } , которая удовлетворяет линейному рекуррентному соотношению f _{n +2} = f _{n +1} + f _n . Соответствующая показательная производящая функция имеет вид

$$\operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}$$

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

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

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

$$\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 равен

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

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

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

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

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

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

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

Серия Белл

Ряд Белла последовательности a _n представляет собой выражение как через неопределенное x , так и через простое число p и определяется выражением

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

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

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

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

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

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

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

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

тогда и только тогда, когда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С

$$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, ... квадратных чисел с помощью линейной комбинации порождающих последовательностей с биномиальными коэффициентами:

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

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

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

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

где { ^н
_k } обозначают числа Стирлинга второго рода и где производящая функция

$$\sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},$$

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

$${\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}},$$

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

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

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

Основная статья: Линейно-рекурсивная последовательность

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

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

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

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

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

$$F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}$$

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

$$\operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},$$

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

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

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

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

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

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

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

Основная статья: Продукт Коши

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

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

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

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

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

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

Для целых чисел m ≥ 1 мы имеем следующие два аналогичных тождества для модифицированных производящих функций, перечисляющих варианты сдвинутой последовательности ⟨ g _{n - m} ⟩ и ⟨ g _{n + m} ⟩ соответственно:

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

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

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

$${\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- й падающий факториал :

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

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

$$\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 это просто знакомое разложение функции на четную и нечетную части (т.е. четные и нечетные степени):

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

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

$$\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 ) называется голономным , если он удовлетворяет линейному дифференциальному уравнению вида

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

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

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

$${\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 ^С , log z , cos z , arcsin z , ${\sqrt {1+z}}$, дилогарифма функция Li ₂ ( z ) , обобщенные гипергеометрические функции _p F _q (...; ...; z ) и функции, определяемые степенным рядом

$$\sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}$$

и несходящийся

$$\sum _{n=0}^{\infty }n!\cdot z^{n}$$

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

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

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

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

дискретного

Основная статья: Преобразование Фурье дискретного времени

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

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

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

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

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

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

$$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, тогда

$$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 _для . В частности,

$$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 для описания производящей функции, как указано выше.

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

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

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

$$G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.$$

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

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

каталонских

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

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

$$G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.$$

При г = 1 / 4 , α знак равно 1 , β знак равно - 1 / 2 , А ( Икс ) = 1 / 2 и B ( Икс ) знак равно - 1/2 , мы можем заключить , что для каталонских чисел

$$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 ) для всех k и n . Для этого рассмотрим (1 + x ) ^н себя как последовательность в n и найдите производящую функцию в y , которая имеет эти значения последовательности в качестве коэффициентов. Поскольку производящая функция для ^н является

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

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

$$\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 обозначает формальную переменную во втором разложении по степеням, приведенном ниже:

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

Коэффициенты $z^{n}$, сокращенно обозначаемый j _n ≔ [ z ^н ] Дж ^[∞] ( z ) в предыдущих уравнениях соответствуют матричным решениям уравнений

$${\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 мы имеем формулу сложения отношение, заданное

$$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 ) , расширенный на

$$\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 ) , определенные рекурсивно формулой

$${\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 _х, тогда у нас есть соответствие

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

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

Примеры

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

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

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

Примеры

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

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

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

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

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

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

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

$$\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 ) , определяемой формулой

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

Серия Белл

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

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

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

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

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

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

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

$$\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 . Затем, по словам Эй Джей Гуда , количество таких таблиц является коэффициентом

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

в

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

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

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

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

$${\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 = Σ ^н
_{k знак равно 0} а _k . Тогда мы знаем, что S ( z ) = A ( z ) / 1 − z для соответствующих обычных производящих функций.

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

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

где Нк ₌ 1 + 1 / 2 + ⋯ + 1 / k — номера гармоник . Позволять

$$H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}$$

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

$$H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,$$

и таким образом

$$S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.$$

С использованием

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

свертка с числителем дает

$$s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,$$

что также можно записать как

$$\sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.$$

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

В качестве еще одного примера использования производящих функций для связи последовательностей и манипулирования суммами для произвольной последовательности ⟨ f _n ⟩ мы определяем две последовательности сумм

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

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

$$S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).$$

Поскольку производящая функция для последовательности ⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩ определяется выражением

$$6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)$$

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

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

Наконец, отсюда следует, что мы можем выразить вторые суммы через первые суммы в следующем виде:

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

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

$${\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}$$

Поскольку мы имеем это для всех целых чисел m ≥ 0 , производящие функции со сдвигом по индексу удовлетворяют

$$z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,$$

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

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

из чего затем следует, решая систему уравнений (и это особая хитрость нашего метода), что

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

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

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

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

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

1. Рассмотрим A ( z ) и B ( z ) — обычные производящие функции.
   $$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 ) — экспоненциальные производящие функции.
   $$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. Рассмотрим тройную свернутую последовательность, полученную в результате произведения трех обычных производящих функций
   $$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 (применение см. в примере ниже)
   $$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 ) , тогда мы можем показать, что для любых двух случайных величин

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

если X и Y независимы. Аналогично, количество способов заплатить n ≥ 0 центов монетами номиналов из набора {1, 5, 10, 25, 50} (т. е. в пенни, пятицентовиках, десятицентовиках, четвертях и полдолларах соответственно) равно созданный продуктом

$$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 символов произведением - Поххаммера. из

$$\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_{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 ) , удовлетворяющую

$$C(z)=z\cdot C(z)^{2}+1\,.$$

Поскольку C (0) = 1 ≠ ∞ , мы приходим к формуле для этой производящей функции, задаваемой следующим образом:

$$C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.$$

Обратите внимание, что первое уравнение, неявно определяющее C ( z ) выше, подразумевает, что

$$C(z)={\frac {1}{1-z\cdot C(z)}}\,,$$

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

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

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

В качестве наблюдения мы можем подойти к этому вопросу, подсчитав количество способов соединения соседних наборов вершин. Например, когда 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 ^н ] z / (1 - z ) ² для м ≔ 1, 2, 3, 4 . В более общем смысле мы можем записать формулу для этой последовательности как

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

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

$$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 узлах (включая листья) удовлетворяет условию

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

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

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

$$T(z)=z\phi (T(z))$$

допускает единственное решение в ${\textstyle T(z)\in C[[z]]}$, что удовлетворяет

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

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

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

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

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

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

Выражение станет намного аккуратнее, если мы позволим $n$ быть числом внутренних узлов: теперь выражение просто становится $n$^й Каталонский номер.

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

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

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

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

$$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 как «свободный» параметр и устанавливать

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

Перестановочное суммирование («змеиное масло») дает

$$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 к + 1} . Таким образом

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

Тогда мы получаем

$$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 . Таким образом, мы установили

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

Перестановочное суммирование («змеиное масло») дает

$$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} . Таким образом

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

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

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

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

удовлетворяют следующему сравнению по модулю 3:

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

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

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

$$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 _п ( z ) для всех 0 ≤ n < 2 п . Затем:

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 ), которые показывают универсальность производящих функций при решении задач, связанных с целочисленными последовательностями .

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

Основная статья о числах Стирлинга, порожденных конечными произведениями

$$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 каждая из этих производящих функций конечного произведения удовлетворяет

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

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

$${\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 ] четен всякий раз, когда k < ⌊ п / 2 ⌋ .

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

$${\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 - Похгаммера в зависимости от обстоятельств), определяемым выражением

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

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

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

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

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

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

все коэффициенты делятся на 5, кроме тех, которые соответствуют степеням 1, z ⁵ , С ¹⁰ , ... и причем в этих случаях остаток коэффициента равен 1 по модулю 5. Таким образом,

$${\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,$$

или эквивалентно

$${\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.$$

Отсюда следует, что

$${\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\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 м + 5} в z · ((1 - z )(1 - z ² )⋯) ⁴ делится на 5 для всех m . Наконец, поскольку

$${\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 м + 5} в предыдущих уравнениях, чтобы доказать желаемый результат сравнения, а именно, что p (5 m + 4) ≡ 0 (mod 5) для всех m ≥ 0 .

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

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

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

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

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

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

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

$$S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)$$

(см. также биномиальное преобразование и преобразование Стирлинга ).

Существуют также интегральные формулы для преобразования между OGF последовательности, F ( z ) и ее экспоненциальной производящей функцией или EGF, F̂ ( z ) и наоборот, заданными формулой

$${\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 -разностные полиномы

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

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

Полиномы

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

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

для некоторой аналитической функции F с разложением в степенной ряд такой, что F (0) = 1 .

Мы говорим, что семейство полиномов f ₀ , f ₁ , f ₂ , ... образует семейство свертки , если deg f _n ≤ n выполняется следующее условие свертки и если для всех x , y и для всех n ≥ 0 :

$$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} , и
• Для произвольного (фиксированного) $x,y,t\in \mathbb {C}$, эти полиномы удовлетворяют формулам свертки вида

$${\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\in \mathbb {C}$мы модифицировали производящие функции для этих полиномиальных последовательностей свертки, заданных формулой

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

где 𝓕 _t ( z ) неявно определяется функциональным уравнением вида 𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^т ) . Более того, мы можем использовать матричные методы (как в ссылке), чтобы доказать, что для данных двух полиномиальных последовательностей свертки, ⟨ f _n ( x ) ⟩ и ⟨ g _n ( x ) ⟩ , с соответствующими соответствующими производящими функциями, F ( z ) ^х и г ( z ) ^х , то для произвольного t имеем тождество

$$\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 ) ^т , так называемые древесные полиномы , числа Белла , B ( n ) , полиномы Лагерра и полиномы свертки Стирлинга .

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

Первоначальный список специальных математических рядов можно найти здесь . Ряд полезных и специальных функций, генерирующих последовательность, можно найти в разделах 5.4 и 7.4 « Конкретной математики» Уилфа» и в разделе 2.5 «Производящей функции . Другие специальные генерирующие функции включают записи в следующей таблице, которая ни в коем случае не является полной.

Формальный степенной ряд	Формула производящей функции	Примечания
$\sum _{n=0}^{\infty }{\binom {m+n}{n}}\left(H_{n+m}-H_{m}\right)z^{n}$	${\frac {1}{(1-z)^{m+1}}}\ln {\frac {1}{1-z}}$	$H_{n}$ первого порядка это номер гармоники
$\sum _{n=0}^{\infty }B_{n}{\frac {z^{n}}{n!}}$	${\frac {z}{e^{z}-1}}$	$B_{n}$ это число Бернулли
$\sum _{n=0}^{\infty }F_{mn}z^{n}$	${\frac {F_{m}z}{1-(F_{m-1}+F_{m+1})z+(-1)^{m}z^{2}}}$	$F_{n}$ является числом Фибоначчи и $m\in \mathbb {Z} ^{+}$
$\sum _{n=0}^{\infty }\left\{{\begin{matrix}n\\m\end{matrix}}\right\}z^{n}$	$(z^{-1})^{\overline {-m}}={\frac {z^{m}}{(1-z)(1-2z)\cdots (1-mz)}}$	$x^{\overline {n}}$ обозначает возрастающий факториал или символ Поххаммера и некоторое целое число $m\geq 0$
$\sum _{n=0}^{\infty }\left[{\begin{matrix}n\\m\end{matrix}}\right]z^{n}$	$z^{\overline {m}}=z(z+1)\cdots (z+m-1)$
$\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}4^{n}(4^{n}-2)B_{2n}z^{2n}}{(2n)\cdot (2n)!}}$	$\ln {\frac {\tan(z)}{z}}$
$\sum _{n=0}^{\infty }{\frac {(1/2)^{\overline {n}}z^{2n}}{(2n+1)\cdot n!}}$	$z^{-1}\arcsin(z)$
$\sum _{n=0}^{\infty }H_{n}^{(s)}z^{n}$	${\frac {\operatorname {Li} _{s}(z)}{1-z}}$	$\operatorname {Li} _{s}(z)$ - функция полилогарифма и $H_{n}^{(s)}$ — обобщенное число гармоник для $\Re (s)>1$
$\sum _{n=0}^{\infty }n^{m}z^{n}$	$\sum _{0\leq j\leq m}\left\{{\begin{matrix}m\\j\end{matrix}}\right\}{\frac {j!\cdot z^{j}}{(1-z)^{j+1}}}$	$\left\{{\begin{matrix}n\\m\end{matrix}}\right\}$ является числом Стирлинга второго рода и где отдельные члены разложения удовлетворяют ${\frac {z^{i}}{(1-z)^{i+1}}}=\sum _{k=0}^{i}{\binom {i}{k}}{\frac {(-1)^{k-i}}{(1-z)^{k+1}}}$
$\sum _{k<n}{\binom {n-k}{k}}{\frac {n}{n-k}}z^{k}$	$\left({\frac {1+{\sqrt {1+4z}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {1+4z}}}{2}}\right)^{n}$
$\sum _{n_{1},\ldots ,n_{m}\geq 0}\min(n_{1},\ldots ,n_{m})z_{1}^{n_{1}}\cdots z_{m}^{n_{m}}$	${\frac {z_{1}\cdots z_{m}}{(1-z_{1})\cdots (1-z_{m})(1-z_{1}\cdots z_{m})}}$	Случай с двумя переменными определяется выражением $M(w,z):=\sum _{m,n\geq 0}\min(m,n)w^{m}z^{n}={\frac {wz}{(1-w)(1-z)(1-wz)}}$
$\sum _{n=0}^{\infty }{\binom {s}{n}}z^{n}$	$(1+z)^{s}$	$s\in \mathbb {C}$
$\sum _{n=0}^{\infty }{\binom {n}{k}}z^{n}$	${\frac {z^{k}}{(1-z)^{k+1}}}$	$k\in \mathbb {N}$
$\sum _{n=1}^{\infty }\log {(n)}z^{n}$	$\left.-{\frac {\partial }{\partial s}}\operatorname {{Li}_{s}(z)} \right|_{s=0}$

История

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

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

См. также

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

Ссылки

Цитаты

• Айгнер, Мартин (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.