Лекция
Привет, сегодня поговорим про генератриса, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое генератриса, производящая функция , настоятельно рекомендую прочитать все из категории Теория вероятностей. Математическая статистика и Стохастический анализ .
В комбинаторике
генератриса -
производящая функция последовательности или образующая функция ( англ. Generating function ) последовательности
- это формальный степенной ряд
.
В математике можно выделить два больших направления: одно изучает непрерывные объекты, другое – дискретные. В реальном мире есть место и для того и для другого подхода и часто к изучению одного и того же явления можно подойти с разных точек зрения. Разумеется, между этими направлениями существует множество связей. Статья посвящена одной из них. Идея производящей функции очень простая. Сопоставим последовательности a0, a1, …, an, … (дискретному объекту) степенной ряд a0 + a1x + … + anxn + … (непре- рывный объект). Поступив так, мы подключаем к изучению дискретных объектов мощный арсенал средств математического анализа. Заметим, что в рассмотренных ниже примерах степенные ряды сходятся на некоторой окрестности нуля, хотя существует теория формальных степенных рядов, которая рассматривает и степенные ряды, сходящиеся только в точке 0. Справедлива теорема единственности: если при некотором положительном “с” функция f(x) представима в виде степенного ряда a0 + + a1x + … + anxn + … на интервале (−с, с), то коэффициенты ai ряда определяются однозначно. Есть и иные конструкции производящих функций – одна из них затронута в конце статьи. Мы будем использовать известные из базового курса математического анализа свойства степенных рядов без дополнительных указаний. Некоторые свойства и применения степенных рядов приведены в . Метод производящих функций очень продуктивен, в частности при решении комбинаторных задач. При- ведем некоторые начальные примеры. 1. Самым известным примером производящей функции является, конечно, бином Ньютона
Экспоненциальная производящая функция последовательности (образующая функция) - это формальный степенной ряд
.
Довольно часто производящая функция последовательности (образующая функция) последовательности является одновременно рядом Тейлора известной аналитической функции , и это можно использовать при исследовании свойств самой последовательности. Тем не менее, производящая функция последовательности необязательно соответствует аналитическая функция.
Например, два ряда
и 
имеют радиус сходимости ноль, то есть разбегаются во всех точках, кроме нуля, а в нуле оба дают 1, то есть как функции они совпадают; тем не менее, как производящая функция последовательности (то есть формальные ряды) они разные.
Производящая функция последовательности (образующие функции) предоставляют возможность просто описывать сложные последовательности в комбинаторике, а иногда помогают найти для них явные формулы. Метод производящая функция последовательности был разработан Эйлером в 50-х годах XVIII века .
и 
- производящая функция последовательности последовательностей и 
, то 
, где 
.
и 
- экспоненциальной производящая функция последовательности последовательностей и , то 
, где 
.пусть 
равно количеству вариантов представления числа 
в виде 
, где 
- неотъемлемые целые числа и
фиксировано, тогда
теперь число можно найти как коэффициент при 
в расписании 
по степеняx 
. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:
Производящая функция - это устройство, чем-то похожее на сумку. Вместо того, чтобы нести множество мелких предметов отдельно, что может быть неудобно, мы кладем их все в сумку, и тогда у нас остается только один предмет - сумка.
- Джордж Полиа , Математика и правдоподобные рассуждения (1954).
Производящая функция - это бельевая веревка, на которую мы вешаем последовательность чисел для отображения.
- Герберт Уилф , Генерирующая функциональность (1994).
Обыкновенная производящая функция последовательности п является
Когда термин " производящая функция" используется без уточнения, он обычно означает обычную производящую функцию.
Если п является функцией вероятности массовой из дискретной случайной величины , то ее обычная производящая функция называется функцией вероятности генерации .
Обычную производящую функцию можно обобщить на массивы с несколькими индексами. Например, обычная производящая функция двумерного массива a m, n (где n и m - натуральные числа) имеет вид
Экспоненциальная производящая функция последовательности п является
Экспоненциальные производящие функции обычно более удобны, чем обычные производящие функции для задач комбинаторного перечисления, которые включают помеченные объекты.
Производящая функция Пуассона последовательности п является
Серии Ламберта последовательности п является
Коэффициенты ряда Ламберта в разложениях в степенной ряд 
для целых чисел 
связаны суммой делителей 
. Основная статья содержит еще несколько классических или, по крайней мере, хорошо известных примеров, связанных со специальными арифметическими функциями в теории чисел . В серии Ламберта индекс n начинается с 1, а не с 0, поскольку в противном случае первый член не был бы определен.
Серии Белл из последовательности п является выражением с точки зрения как неопределенном х и простого р и задается
Формальные ряды Дирихле часто классифицируются как производящие функции, хотя они не являются строго формальными степенными рядами. Производящий ряд функций Дирихле последовательности п является
Функция генерирования ряд Дирихля особенно полезна , когда п является мультипликативной функцией , в этом случае он имеет Эйлера продукт выражение в терминах рядов Bell функции в
Если п является характером Дирихля , то его функция производящего ряда Дирихля называется L-рядом Дирихля . У нас также есть связь между парой коэффициентов в разложениях в ряд Ламберта выше и их DGF. А именно, мы можем доказать, что
если и только если 
где 
- дзета-функция Римана .
Идея создания функций может быть распространена на последовательности других объектов. Так, например, полиномиальные последовательности биномиального типа порождаются
где p n ( x ) - последовательность многочленов, а f ( t ) - функция определенного вида. Последовательности Шеффера генерируются аналогичным образом. См. Основную статью об обобщенных полиномах Аппеля для получения дополнительной информации.
Полиномы - это частный случай обычных производящих функций, соответствующих конечным последовательностям, или, что эквивалентно, последовательностям, которые обращаются в нуль после определенной точки. Они важны тем, что многие конечные последовательности можно с пользой интерпретировать как производящие функции, такие как полином Пуанкаре и другие.
Фундаментальной производящей функцией является постоянная последовательность 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., обычная производящая функция которой является геометрическим рядом
Левая часть - это разложение правой части в ряд Маклорена . В качестве альтернативы, равенство может быть подтверждено умножением степенного ряда слева на 1 - x и проверкой того, что результатом является постоянный степенной ряд 1 (другими словами, что все коэффициенты, кроме одного из x 0 , равны 0) . Более того, других степенных рядов с этим свойством быть не может. Следовательно, левая часть обозначает мультипликативную обратную единицу - x в кольце степенных рядов.
Выражения для обычной производящей функции других последовательностей легко выводятся из этого. Например, замена x → ax дает производящую функцию для геометрической последовательности 1, a , a 2 , a 3 , ... для любой константы a :
(Равенство также следует непосредственно из того факта, что левая часть является разложением правой части в ряд Маклорена.) В частности,
Можно также ввести регулярные "пробелы" в последовательности, заменив x некоторой степенью x , так, например, для последовательности 1, 0, 1, 0, 1, 0, 1, 0, .... получается порождающий функция
Возводя в квадрат исходную производящую функцию или находя производную обеих частей по x и делая замену переменной n → n + 1, можно увидеть, что коэффициенты образуют последовательность 1, 2, 3, 4, 5, ..., так что
а третья степень имеет в качестве коэффициентов треугольные числа 1, 3, 6, 10, 15, 21, ..., член которых n является биномиальным коэффициентом 
, чтобы
В более общем смысле, для любого неотрицательного целого числа k и ненулевого действительного значения a верно, что
С
можно найти обычную производящую функцию для последовательности 0, 1, 4, 9, 16, ... квадратных чисел путем линейной комбинации производящих последовательностей биномиальных коэффициентов:
Мы также можем поочередно расширять, чтобы сгенерировать ту же последовательность квадратов как сумму производных геометрического ряда в следующей форме:
По индукции аналогично можно показать для натуральных чисел 
что
где 
обозначают числа Стирлинга второго рода и где производящая функция
, так что аналогичные производящие функции можно составить по интегралу -я степень обобщает результат в приведенном выше квадратном случае. В частности, поскольку мы можем написать
, мы можем применить хорошо известное тождество с конечной суммой, включающее числа Стирлинга, чтобы получить это [10]
Обычная производящая функция последовательности может быть выражена как рациональная функция (отношение двух многочленов конечной степени) тогда и только тогда, когда последовательность является линейной рекурсивной последовательностью с постоянными коэффициентами; это обобщает приведенные выше примеры. И наоборот, каждая последовательность, порожденная частью многочленов, удовлетворяет линейной рекуррентности с постоянными коэффициентами; эти коэффициенты идентичны коэффициентам полинома знаменателя дроби (поэтому они могут быть непосредственно считаны). Это наблюдение показывает, что легко решить производящие функции последовательностей, определяемых линейным конечно-разностным уравнениемс постоянными коэффициентами, а значит, и для явных замкнутых формул для коэффициентов этих производящих функций. Прототипный пример здесь - вывести формулу Бине для чисел Фибоначчи с помощью методов производящих функций.
Отметим также, что класс рациональных производящих функций в точности соответствует производящим функциям, перечисляющим квазиполиномиальные последовательности вида [11]
где взаимные корни, 
, являются фиксированными скалярами и где 
является многочленом от для всех 
.
В общем, произведения Адамара рациональных функций порождают рациональные производящие функции. Аналогично, если
- двумерная рациональная производящая функция, то соответствующая ей диагональная производящая функция ,
, является алгебраическим . Например, если мы положим [12]
то производящая функция диагонального коэффициента этой производящей функции задается известной формулой OGF
Этот результат вычисляется многими способами, включая интегральную формулу Коши или контурное интегрирование , взятие комплексных вычетов или прямое манипулирование формальными степенными рядами от двух переменных.
Умножение обычных производящих функций дает дискретную свертку (произведение Коши ) последовательностей. Например, последовательность кумулятивных сумм (сравните с несколько более общей формулой Эйлера – Маклорена )
последовательности с обычной производящей функцией G ( a n ; x ) имеет производящую функцию
поскольку 1 / (1 - x ) - обычная производящая функция для последовательности (1, 1, ...). См. Также раздел о свертках в разделе приложений этой статьи ниже, где приведены дополнительные примеры решения проблем с помощью сверток производящих функций и интерпретаций.
Для целых чисел , мы имеем следующие два аналогичных тождества для модифицированных производящих функций, перечисляющих варианты сдвинутой последовательности 
а также 
, соответственно:
У нас есть следующие разложения в степенной ряд для первой производной производящей функции и ее интеграла:
Операцию дифференцирования-умножения второго тождества можно повторить. 
раз умножить последовательность на 
, но для этого нужно чередовать дифференцирование и умножение. Если вместо этого дифференцирования последовательно, эффект умножается на й падающий факториал :
Используя числа Стирлинга второго рода , это можно превратить в другую формулу для умножения наследующим образом (см. основную статью о преобразованиях производящих функций ):
Обращение отрицательного порядка этой формулы степеней последовательности, соответствующей операции повторного интегрирования, определяется преобразованием дзета-ряда и его обобщениями, определяемыми как основанное на производной преобразовании производящих функций , или, альтернативно, почленно путем выполнения интегрального преобразования в последовательности производящая функция. Связанные операции выполнения дробной интеграции на порождающей функции последовательности обсуждаются здесь .
В этом разделе мы приводим формулы для производящих функций, перечисляющих последовательность 
учитывая обычную производящую функцию 
где 
, 
, а также 
(см. основную статью о преобразованиях ). Для
, это просто знакомое разложение функции на четные и нечетные части (т.е. четные и нечетные степени):
В более общем плане предположим, что 
и это 
обозначает 
й примитивный корень из единицы . Тогда как приложение дискретного преобразования Фурье имеем формулу [13]
Для целых чисел , еще одна полезная формула, обеспечивающая несколько перевернутые арифметические прогрессии - эффективное повторение каждого коэффициентараз - порождаются тождеством [14]
Формальный степенной ряд (или функция) называется голономным, если он удовлетворяет линейному дифференциальному уравнению вида [15]
где коэффициенты 
находятся в области рациональных функций, 
. Эквивалентно, голономно, если векторное пространство над натянутое на множество всех его производных конечномерно.
Поскольку мы можем очистить знаменатели, если это необходимо в предыдущем уравнении, мы можем предположить, что функции, являются многочленами от 
. Таким образом, мы можем видеть эквивалентное условие голономности производящей функции, если ее коэффициенты удовлетворяют P-рекуррентности вида
для всех достаточно больших 
и где 
- фиксированные многочлены конечной степени от . Другими словами, свойства того, что последовательность P-рекурсивна и имеет голономную производящую функцию, эквивалентны. Голономные функции закрываются операцией произведения Адамара.
по производящим функциям.
Функции 
, 
, 
, 
, 
, функция дилогарифма
, обобщенные гипергеометрические функции 
а функции, определяемые степенным рядом 
и несходящиеся 
все голономны. Примеры P-рекурсивных последовательностей с голономными производящими функциями включают:
а также 
, где такие последовательности, как 
а также 
не являются P-рекурсивными из-за характера особенностей в соответствующих им производящих функциях. Точно так же функции с бесконечным числом особенностей, такие как
, 
, а также 
не являются голономными функциями.
Инструменты для обработки и работы с P-рекурсивными последовательностями в системе Mathematica включают пакеты программного обеспечения, предоставленные для некоммерческого использования на сайте программного обеспечения алгоритмической комбинаторики RISC Combinatorics Group . Несмотря на то, что это в основном закрытый исходный код, особенно мощные инструменты в этом программном пакете предоставляются пакетом Guess для угадывания P-повторений для произвольных входных последовательностей (полезно для экспериментальной математики и исследований) и пакетом Sigma , который может находить P-повторения для много сумм и решение для замкнутых решений P-рекуррент, включающих обобщенные гармонические числа . [16]Другие пакеты, перечисленные на этом конкретном сайте RISC, специально предназначены для работы с функциями генерации голономии . ( В зависимости от того, насколько подробно эта статья посвящена теме, существует множество других примеров полезных программных инструментов, которые можно перечислить здесь или на этой странице в другом разделе. )
Когда ряд абсолютно сходится ,
- дискретное преобразование Фурье последовательности a 0 , a 1 , ....
В расчетах часто скорость роста коэффициентов степенного ряда может использоваться для определения радиуса сходимости степенного ряда. Обратное тоже может иметь место; часто радиус сходимости производящей функции может использоваться для вывода асимптотического роста базовой последовательности.
Например, если обычная производящая функция G ( a n ; x ), имеющая конечный радиус сходимости r, может быть записана как
где каждая из A ( x ) и B ( x ) является функцией, аналитической для радиуса сходимости больше r (или целой ), и где B ( r ) ≠ 0, то
с использованием гамма-функции , биномиального коэффициента или коэффициента мультимножества .
Часто такой подход может повторяться для создания нескольких терминов в асимптотический ряд для в п . Об этом говорит сайт https://intellect.icu . В частности,
Затем можно искать асимптотический рост коэффициентов этой производящей функции, находя A , B , α, β и r для описания производящей функции, как указано выше.
Аналогичный асимптотический анализ возможен для экспоненциальных производящих функций. С экспоненциальной производящей функцией, то п / п ! который растет согласно этим асимптотическим формулам.
Как показано выше, обычная производящая функция для последовательности квадратов имеет вид
При r = 1, α = −1, β = 3, A ( x ) = 0 и B ( x ) = x +1 мы можем проверить, что квадраты растут, как и ожидалось, как и квадраты:
Обычная производящая функция для каталонских чисел:
При r = 1/4, α = 1, β = −1/2, A ( x ) = 1/2 и B ( x ) = −1/2 мы можем заключить, что для каталонских чисел
Для массивов с несколькими индексами можно определить производящие функции от нескольких переменных. Их называют многомерными производящими функциями или, иногда, суперпроизводящими функциями . Для двух переменных их часто называют двумерными производящими функциями .
Например, поскольку 
является обычной производящей функцией для биномиальных коэффициентов для фиксированного n , можно запросить двумерную производящую функцию, которая генерирует биномиальные коэффициенты
для всех k и n . Для этого рассмотримкак сама последовательность в n , и найти производящую функцию в y, которая имеет эти значения последовательности в качестве коэффициентов. Поскольку производящая функция для
является
производящая функция для биномиальных коэффициентов:
Разложения (формальных) цепных дробей типа Якоби и Стилтьеса (соответственно J-дробей и S-дробей ),
рациональные конвергенты представляют 
степенные ряды с точным порядком - еще один способ выразить обычно расходящиеся обычные производящие функции для многих специальных одно- и двумерных последовательностей. Конкретная форма цепных дробей типа Якоби (J-дроби) раскрывается, как в следующем уравнении, и имеет следующие соответствующие разложения в степенной ряд по отношению к для некоторых конкретных, зависящих от приложения последовательностей компонентов, 
а также 
, где 
обозначает формальную переменную во втором разложении степенного ряда, приведенном ниже: [17]
Коэффициенты 
, сокращенно обозначаемый 
, в предыдущих уравнениях соответствуют матричным решениям уравнений
где 
, 
для , 
если 
, и где для всех целых чисел 
, мы имеем соотношение формулы сложения, задаваемое формулой
Для 
(хотя на практике, когда 
), можно определить рациональную 
сходится к бесконечной J-дроби, 
, расширенный на
покомпонентно по последовательностям, 
а также 
, рекурсивно определяемый
Более того, рациональность сходящейся функции 
для всех влечет дополнительные конечно-разностные уравнения и свойства сравнения, которым удовлетворяет последовательность 
, а для
если 
тогда у нас есть сравнение
для несимвольного, детерминированного выбора последовательностей параметров, а также , когда , т. е. когда эти последовательности неявно не зависят от вспомогательного параметра, такого как 
, , или же 
как в примерах, приведенных в таблице ниже.
В следующей таблице приведены примеры формул закрытых формул для последовательностей компонентов, найденных вычислительным методом (и впоследствии доказавших свою правильность в цитируемых ссылках [18] ) в нескольких частных случаях предписанных последовательностей., порожденные общими разложениями J-дробей, определенных в первом пункте. Здесь мы определяем
и параметры , 
а также чтобы быть неизвестными в отношении этих разложений, где предписанные последовательности , перечисленных путем разложения этих J-фракции определены в терминах Q-Похгаммере символа , символ Похгаммера , и биномиальных коэффициенты .
|
 |
 |
 |
|---|---|---|---|
 |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
|
 |
 |
 |
|
Радиусы сходимости этих рядов, соответствующих приведенному выше определению J-дробей типа Якоби, в общем случае отличаются от радиусов сходимости соответствующих разложений в степенные ряды, определяющих обычные производящие функции этих последовательностей.
Производящими функциями для последовательности квадратных чисел a n = n 2 являются:
В качестве примера тождества ряда Ламберта, не приведенного в основной статье , мы можем показать, что для
у нас есть это [19]
где у нас есть тождество частного случая для производящей функции функции делителя ,
, данный
используя дзета-функцию Римана .
Последовательность a k, порожденная производящей функцией ряда Дирихле (DGF), соответствующей:
где - дзета-функция Римана , имеет обычную производящую функцию:
Многовариантные производящие функции возникают на практике при вычислении количества таблиц непредвиденных обстоятельств неотрицательных целых чисел с заданными суммами по строкам и столбцам. Предположим, что в таблице есть r строк и c столбцов; суммы строк
и суммы столбцов 
. Тогда, согласно IJ Good , [20] количество таких таблиц является коэффициентом
в
В двумерном случае неполиномиальные примеры двойной суммы так называемых " двойных " или " супер " производящих функций вида
включают следующие производящие функции с двумя переменными для биномиальных коэффициентов , чисел Стирлинга и чисел Эйлера : [21]
Производящие функции дают нам несколько методов для управления суммами и установления тождеств между суммами.
Самый простой случай возникает, когда 
. Тогда мы знаем, что
для соответствующих обычных производящих функций.
Например, мы можем манипулировать 
, где 
- гармонические числа . Позволять
- обычная производящая функция номеров гармоник. потом
и поэтому
С использованием 
, Свертка с выходами числителя
который также можно записать как
В качестве еще одного примера использования производящих функций для связывания последовательностей и управления суммами для произвольной последовательности 
определим две последовательности сумм
для всех 
, и постараемся выразить вторую сумму через первую. Мы предлагаем подход, основанный на производящих функциях.
Сначала мы используем биномиальное преобразование, чтобы записать производящую функцию для первой суммы как
Поскольку производящая функция для последовательности 
дан кем-то 
, мы можем записать производящую функцию для второй суммы, определенной выше, в виде
В частности, мы можем записать эту модифицированную функцию генерации суммы в виде
для 
, 
, 
, а также 
где 
.
Наконец, отсюда следует, что мы можем выразить вторую сумму через первые суммы в следующей форме:
В этом примере мы переформулируем пример производящей функции, приведенный в разделе 7.3 « Конкретной математики» (см. Также раздел 7.1 того же справочника, где приведены красивые изображения производящих рядов функций). В частности, предположим, что мы ищем общее количество путей (обозначенных
) выложить 
прямоугольник с немаркированным 
домино. Пусть вспомогательная последовательность,
, можно определить как количество способов преодоления rectangle-minus-corner секция полного прямоугольника. Мы стремимся использовать эти определения, чтобы дать формулу в замкнутой форме дляне разрушая это определение, чтобы рассмотреть случаи вертикального и горизонтального домино. Обратите внимание, что обычные производящие функции для наших двух последовательностей соответствуют ряду
Если мы рассмотрим возможные конфигурации, которые можно дать, начиная с левого края прямоугольник, мы можем выразить следующие взаимозависимые или взаимно рекурсивные рекуррентные отношения для наших двух последовательностей, когда
определено, как указано выше, где 
, 
, 
, а также 
:
Поскольку у нас есть это для всех целых чисел 
, производящие функции со сдвигом индекса удовлетворяют 
(кстати, у нас есть и соответствующая формула, когда 
дано 
), мы можем использовать указанные выше начальные условия и предыдущие два рекуррентных соотношения, чтобы увидеть, что у нас есть следующие два уравнения, связывающие производящие функции для этих последовательностей, задаваемые формулой
что затем подразумевает, решая систему уравнений (и это особый трюк нашего метода здесь), что
Таким образом, выполняя алгебраические упрощения последовательности, полученной в результате разложения производящей функции на вторые частичные дроби в предыдущем уравнении, мы находим, что 
и это
для всех целых чисел . Мы также отмечаем, что тот же метод смещенных производящих функций, применяемый к рекуррентным функциям второго порядка для чисел Фибоначчи, является типичным примером использования производящих функций для решения рекуррентных соотношений в одной переменной, уже рассмотренной или, по крайней мере, намекаемой в подразделе, посвященном рациональным функции, указанные выше.
Дискретная свертка членов двух формальных степенных рядов превращает произведение производящих функций в производящую функцию, перечисляющую свернутую сумму исходных членов последовательности (см. Произведение Коши ).
1. Рассмотрим A ( z ) и B ( z ) обычные производящие функции.
2. Рассмотрим A ( z ) и B ( z ) экспоненциальные производящие функции.
3.Рассмотрим тройную свернутую последовательность, полученную из произведения трех обычных производящих функций.
4. рассмотрите -кратная свертка последовательности с самой собой для некоторого положительного целого числа (см. пример приложения ниже)
Умножение производящих функций или свертка лежащих в их основе последовательностей может соответствовать понятию независимых событий в определенных сценариях подсчета и вероятности. Например, если мы примем условное обозначение, что функция, генерирующая вероятность , или pgf , случайной величины
обозначается 
, то можно показать, что для любых двух случайных величин [22]
если 
а также 
независимы. Точно так же количество способов оплаты центов номиналом в монетах достоинств в наборе 
(т. е. в копейках, никелях, десятицентовиках, четвертях и полдолларах соответственно) генерируется продуктом
и более того, если мы позволим центы , чтобы быть выплачен в монетах любого натурального номинала, мы приходим к генерации для числа таких комбинаций изменений, вырабатываемого статсумма порождающей функции расширенной бесконечной д-Похгаммер символа продуктом
.
Пример, в котором полезны свертки производящих функций, позволяет нам найти конкретную функцию замкнутой формы, представляющую обычную производящую функцию для каталонских чисел ,
. В частности, эта последовательность имеет комбинаторную интерпретацию как количество способов вставить круглые скобки в произведение.
так что порядок умножения полностью указан. Например,
что соответствует двум выражениям 
а также 
. Отсюда следует, что последовательность удовлетворяет рекуррентному соотношению, заданному формулой
и, следовательно, имеет соответствующую свернутую производящую функцию, 
, удовлетворяющий
С 
, тогда мы приходим к формуле для этой производящей функции, заданной как
Обратите внимание, что первое уравнение, неявно определяющее выше означает, что
что затем приводит к другому "простому" (как по форме) разложению этой производящей функции в цепную дробь.
Вентилятор порядка определяется как граф на вершинах 
с участием 
ребра соединяются по следующим правилам: Вершина 
соединяется одним ребром друг с другом вершины и вершины соединяется одним ребром со следующей вершиной 
для всех 
. [23] Есть один веер первого порядка, три вентилятора второго порядка, восемь вентиляторов третьего порядка и так далее. Остов подграф графа , который содержит все исходные вершины и который содержит достаточно края , чтобы сделать этот подграф подключен, но не так много ребер , что существует цикл в подграфа. Спрашиваем, сколько остовных деревьев
любителя порядка возможны для каждого .
В качестве наблюдения мы можем подойти к вопросу, посчитав количество способов соединения смежных наборов вершин. Например, когда
у нас есть это 
, который представляет собой сумму по -кратные свертки последовательности 
для 
. В более общем смысле, мы можем записать формулу для этой последовательности как
из которого мы видим, что обычная производящая функция для этой последовательности задается следующей суммой сверток как
из которого мы можем извлечь точную формулу для последовательности, взяв частичное разложение последней производящей функции.
Иногда сумма 
сложно, и его не всегда легко оценить. Другой метод (названный Х. Уилфом «змеиное масло») - это метод «свободного параметра» для оценки этих сумм.
Оба обсуждаемых до сих пор метода как предел при суммировании. Когда n не появляется явно в суммировании, мы можем рассматривать как «бесплатный» параметр и рассматривать как коэффициент 
изменим порядок суммирования на а также , и попробуйте вычислить внутреннюю сумму.
Например, если мы хотим вычислить
мы можем лечить как "свободный" параметр и установите
Суммирование местами («змеиный жир») дает
Теперь внутренняя сумма 
. Таким образом
Тогда получаем
Мы говорим, что две производящие функции (степенные ряды) конгруэнтны по модулю , написано 
если их коэффициенты сравнимы по модулю для всех , т. е. 
для всех соответствующих случаев целых чисел (обратите внимание, что нам не нужно предполагать, что здесь целое число - оно вполне может быть полиномиально значным в некоторых неопределенных , Например). Если " более простая " правая производящая функция,
, является рациональной функцией , то вид этих последовательностей предполагает, что последовательность в конечном итоге является периодической по модулю фиксированных частных случаев целочисленных
. Например, мы можем доказать, что числа Эйлера ,
, удовлетворяют следующему сравнению по модулю 
: [24]
Один из наиболее полезных, если не откровенно мощных, методов получения сравнений для последовательностей, перечисляемых специальными производящими функциями по модулю любых целых чисел (т. Е. Не только степеней простых чисел 
) дан в разделе, посвященном представлению непрерывными дробями (даже несходящихся) обычных производящих функций J-дробями выше. Мы процитируем один конкретный результат, относящийся к генерации рядов, расширенных посредством представления цепной дробью, из лекций Ландо о производящих функциях следующим образом:
Теорема: (Сравнения для рядов , порожденных разложениями непрерывных дробей). Предположим, что производящая функция
представлена бесконечной цепной дробью вида
и это 
обозначает 
сходящаяся к этому разложению цепной дроби, определенная таким образом, что 
для всех 
. Тогда 1) функция рационально для всех 
где мы предполагаем, что один из критериев делимости 
выполняется, т. е. 
для некоторых 
; и 2) если целое число
делит продукт 
, то имеем 
.
Производящие функции также могут использоваться в других целях при доказательстве сравнений для их коэффициентов. Мы приводим следующие два конкретных примера, выводящих частные сравнения чисел Стирлинга первого рода и статистической суммы (математика). 
которые демонстрируют универсальность производящих функций при решении задач, связанных с целочисленными последовательностями .
Основная статья о числах Стирлинга , порожденная конечных продуктами
предоставляет обзор сравнений для этих чисел, полученных строго из свойств их производящей функции, как в разделе 4.6 справочника Уилфа по акции Generatingfunctionology . Мы повторяем основной аргумент и замечаем, что при уменьшении по модулю
, каждая из этих производящих функций конечного произведения удовлетворяет
что означает, что четность этих чисел Стирлинга совпадает с четностью биномиального коэффициента
и, следовательно, показывает, что 
даже когда 
.
Точно так же мы можем уменьшить правые произведения, определяющие производящие функции числа Стирлинга по модулю для получения несколько более сложных выражений при условии, что
В этом примере мы задействуем часть механизма бесконечных произведений, разложения в степенной ряд которых порождают разложения многих специальных функций и перечисляют функции разбиения. В частности, напомним , что статсумма генерируется обратным бесконечным произведением символа q-Поххаммера (или произведением z-Поххаммера, в зависимости от случая), задаваемым формулой
Эта статистическая сумма удовлетворяет многим известным свойствам сравнения , которые, в частности, включают следующие результаты, хотя все еще остается много открытых вопросов о формах связанных целочисленных сравнений для функции: [25]
Мы покажем, как использовать производящие функции и манипуляции с конгруэнциями для формальных степенных рядов, чтобы дать очень элементарное доказательство первого из этих сравнений, перечисленных выше.
Во-первых, заметим, что производящая функция биномиального коэффициента, 
, удовлетворяет тому, что каждый из его коэффициентов делится на 
за исключением тех, которые соответствуют полномочиям 
, все из которых в противном случае имеют остаток 
по модулю . Таким образом, мы можем написать
что, в частности, показывает нам, что
Отсюда легко видеть, что делит каждый коэффициент 
в бесконечном произведении разложения
Наконец, поскольку мы можем записать производящую функцию для статистической суммы как
мы можем приравнять коэффициенты при 
в предыдущих уравнениях, чтобы доказать желаемый результат сравнения, а именно: 
для всех .
Есть ряд преобразований производящих функций, которые предоставляют другие приложения (см. Основную статью ). Преобразование обычной производящей функции (OGF) последовательности обеспечивает метод преобразования производящей функции для одной последовательности в производящую функцию, перечисляющую другую. Эти преобразования обычно включают интегральные формулы, включающие последовательность OGF (см. Интегральные преобразования ) или взвешенные суммы по производным высшего порядка этих функций (см. Преобразования производных ).
Преобразования производящей функции могут вступить в игру, когда мы стремимся выразить производящую функцию для сумм
в виде 
с участием функции создания исходной последовательности. Например, если суммы
, то производящая функция для модифицированных сумм выражений имеет вид 
[26] (см. Также биномиальное преобразование и преобразование Стирлинга ).
Существуют также интегральные формулы для преобразования между OGF последовательности, , и его экспоненциальная производящая функция, или EGF, 
, и наоборот
при условии, что эти интегралы сходятся при подходящих значениях .
Генерирующие функции используются для:
Примеры полиномиальных последовательностей, генерируемых более сложными производящими функциями, включают:
Другие последовательности, генерируемые более сложными производящими функциями:
В статье Кнута под названием « Полиномы свертки » [27] обобщенный класс последовательностей полиномов свертки определяется их специальными производящими функциями вида
для некоторой аналитической функции 
с расширением степенного ряда таким, что 
. Мы говорим, что семейство многочленов,
, образует сверточное семейство, если
и если выполняется следующее условие свертки для всех 
и для всех :
Мы видим, что для семейств сверток, не являющихся тождественно нулевыми, это определение эквивалентно требованию, чтобы последовательность имела обычную производящую функцию первой формы, указанной выше.
Последовательность полиномов свертки, определенная в обозначениях выше, имеет следующие свойства:
имеет биномиальный тип
а также 
, а также
эти полиномы удовлетворяют формулам свертки вида
Для фиксированного ненулевого параметра 
, мы модифицировали производящие функции для этих последовательностей полиномов свертки, заданных формулой
где 
неявно определяется функциональным уравнением вида
. Более того, мы можем использовать матричные методы (как в справочнике), чтобы доказать, что с учетом двух последовательностей полиномов свертки,
а также 
, с соответствующими производящими функциями, 
а также 
, то для произвольных 
у нас есть личность
Примеры полиномиальных последовательностей свертки включают биномиальный степенной ряд ,
, так называемые древесные многочлены , числа Белла ,
, То многочлены Лагерра , и Стирлинга свертка многочлены .
Первоначальный список специальных математических рядов находится здесь . Ряд полезных и специальных функций, генерирующих последовательность, можно найти в разделах 5.4 и 7.4 « Конкретной математики» и в разделе 2.5 « Генераторная функциональность» Уилфа . Другие особые функции генерации, которые следует отметить, включают записи в следующей таблице, которая никоим образом не является полной. [28]
Джордж Полиа пишет по математике и правдоподобным рассуждениям :
Название «производящая функция» принадлежит Лапласу . Однако, не называя его, Эйлер использовал устройство производящих функций задолго до Лапласа [..]. Он применил этот математический инструмент к нескольким задачам комбинаторного анализа и теории чисел .
Метод производящих функций был разработан Эйлером в 1750-х годах; классическим примером служит пентагональная теорема Эйлера.
Переводна русский язык « производящая функция последовательности » термина « generating function » с английского не достаточно удачным. Лучше использовать вместо более употребляемый термин в украинском математической литературе - « образующая функция », которому соответствует русское « производящая функция »
Надеюсь, эта статья про генератриса, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое генератриса, производящая функция и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория вероятностей. Математическая статистика и Стохастический анализ
- номер гармоники первого порядка
число Фибоначчи и
обозначает возрастающий факториал или символ Поххаммера и некоторое целое число
- функция полилогарифма и
является обобщенным гармоническим числом для
является числом Стирлинга второго рода и где отдельные члены в разложении удовлетворяют
Комментарии
Оставить комментарий
Теория вероятностей. Математическая статистика и Стохастический анализ
Термины: Теория вероятностей. Математическая статистика и Стохастический анализ