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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Белл серии

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

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

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

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

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

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

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

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

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

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

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

где п_п(Икс) представляет собой последовательность многочленов и ж(т) является функцией определенного вида. Последовательности Шеффера генерируются аналогичным образом. Смотрите основную статью обобщенные полиномы Аппеля за дополнительной информацией.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ displaystyle sum _ {n = 0} ^ { infty} a ^ {n} { binom {n + k} {k}} x ^ {n} = { frac {1} {(1-топор ) ^ {k + 1}}} ,.}

поскольку

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

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

{ Displaystyle G (п ^ {2}; х) = сумма _ {п = 0} ^ { infty} п ^ {2} х ^ {п} = { гидроразрыва {2} {(1-х) ^ {3}}} - { frac {3} {(1-x) ^ {2}}} + { frac {1} {1-x}} = { frac {x (x + 1)} {(1-x) ^ {3}}}.}

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

{ displaystyle { begin {align} G (n ^ {2}; x) & = sum _ {n = 0} ^ { infty} n ^ {2} x ^ {n} = sum _ {n = 0} ^ { infty} n (n-1) x ^ {n} + sum _ {n = 0} ^ { infty} nx ^ {n} & = x ^ {2} D ^ { 2} left [{ frac {1} {1-x}} right] + xD left [{ frac {1} {1-x}} right] & = { frac {2x ^ {2}} {(1-x) ^ {3}}} + { frac {x} {(1-x) ^ {2}}} = { frac {x (x + 1)} {(1 -x) ^ {3}}}. end {выравнивается}}}

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

{ displaystyle n ^ {m} = sum _ {j = 0} ^ {m} left {{ begin {matrix} m j end {matrix}} right } { frac {n !} {(ндж)!}},}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ Displaystyle (а_ {0}, а_ {0} + а_ {1}, а_ {0} + а_ {1} + а_ {2}, ldots)}

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

{ Displaystyle G (а_ {п}; х) cdot { гидроразрыва {1} {1-х}}}

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

Индексы смещения последовательности

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

{ Displaystyle { begin {align} z ^ {m} G (z) & = sum _ {n geq m} g_ {nm} z ^ {n} { frac {G (z) -g_ {0} -g_ {1} z- cdots -g_ {m-1} z ^ {m-1}} {z ^ {m}}} & = sum _ {n geq 0} g_ {n + m} z ^ {n}. end {выравнивается}}}

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

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

{ Displaystyle { begin {align} G ^ { prime} (z) & = sum _ {n geq 0} (n + 1) g_ {n + 1} z ^ {n} z cdot G ^ { prime} (z) & = sum _ {n geq 0} ng_ {n} z ^ {n} int _ {0} ^ {z} G (t) , dt & = сумма _ {n geq 1} { frac {g_ {n-1}} {n}} z ^ {n}. end {выравнивается}}}

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

{ displaystyle z ^ {k} G ^ {(k)} (z) = sum _ {n geq 0} n ^ { underline {k}} g_ {n} z ^ {n} = sum _ {n geq 0} n (n-1) dotsb (n-k + 1) g_ {n} z ^ {n} { text {для всех}} k in mathbb {N}.}

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

{ displaystyle sum _ {j = 0} ^ {k} left {{ begin {matrix} k j end {matrix}} right } z ^ {j} F ^ {(j) } (z) = sum _ {n geq 0} n ^ {k} f_ {n} z ^ {n} { text {для всех}} k in mathbb {N}.}

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

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

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

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

{ displaystyle sum _ {n geq 0} f_ {2n + 1} z ^ {2n + 1} = { frac {1} {2}} left (F (z) -F (-z) правильно).}

В более общем плане предположим, что ${ displaystyle a geq 3}$ и это ${ Displaystyle омега _ {а} = ехр влево (2 пи imath / а вправо)}$ обозначает ${ displaystyle a}$ ^th первобытный корень единства. Затем, как приложение дискретное преобразование Фурье, имеем формулу^[13]

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

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

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

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

Определения

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

{ Displaystyle G (a_ {n}; x) = { frac {A (x) + B (x) left (1 - { frac {x} {r}} right) ^ {- beta} } {х ^ { альфа}}}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения

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

{ displaystyle { begin {align} J ^ {[ infty]} (z) & = { cfrac {1} {1-c_ {1} z - { cfrac {{ text {ab}} _ { 2} z ^ {2}} {1-c_ {2} z - { cfrac {{ text {ab}} _ {3} z ^ {2}} { ddots}}}}}} & = 1 + c_ {1} z + left ({ text {ab}} _ {2} + c_ {1} ^ {2} right) z ^ {2} + left (2 { text {ab} } _ {2} c_ {1} + c_ {1} ^ {3} + { text {ab}} _ {2} c_ {2} right) z ^ {3} + cdots. End {выровнено }}}

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

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

где ${ Displaystyle J_ {0} Equiv k_ {0,0} = 1}$ , ${ displaystyle j_ {n} = k_ {0, n}}$ для ${ Displaystyle п geq 1}$ , ${ displaystyle k_ {r, s} = 0}$ если ${ displaystyle r> s}$ , и где для всех целых чисел ${ displaystyle p, q geq 0}$ , у нас есть формула сложения отношение, данное

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

Свойства $час$ ^th сходящиеся функции

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

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

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

{ displaystyle { begin {align} 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 {align}}}

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

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

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

Примеры

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

${ displaystyle j_ {n}}$	${ displaystyle c_ {1}}$	${ Displaystyle c_ {я} (я geq 2)}$	${ Displaystyle { текст {ab}} _ {я} (я geq 2)}$
${ Displaystyle д ^ {п ^ {2}}}$	${ displaystyle q}$	${ displaystyle q ^ {2h-3} left (q ^ {2h} + q ^ {2h-2} -1 right)}$	${ displaystyle q ^ {6h-10} left (q ^ {2h-2} -1 right)}$
${ Displaystyle (а; д) _ {п}}$	${ displaystyle 1-a}$	${ displaystyle q ^ {h-1} -aq ^ {h-2} left (q ^ {h} + q ^ {h-1} -1 right)}$	${ displaystyle aq ^ {2h-4} (aq ^ {h-2} -1) (q ^ {h-1} -1)}$
${ displaystyle left (zq ^ {- n}; q right) _ {n}}$	${ displaystyle { frac {q-z} {q}}}$	${ displaystyle { frac {q ^ {h} -z-qz + q ^ {h} z} {q ^ {2h-1}}}}$	${ Displaystyle { гидроразрыва {(д ^ {ч-1} -1) (д ^ {ч-1} -z) cdot z} {д ^ {4ч-5}}}}$
${ displaystyle { frac {(a; q) _ {n}} {(b; q) _ {n}}}}$	${ displaystyle { frac {1-a} {1-b}}}$	${ displaystyle { frac {q ^ {i-2} left (q + abq ^ {2i-3} + a (1-q ^ {i-1} -q ^ {i}) + b (q ^ {i} -q-1) right)} {(1-bq ^ {2i-4}) (1-bq ^ {2i-2})}}}$	${ displaystyle { frac {q ^ {2i-4} (1-bq ^ {i-3}) (1-aq ^ {i-2}) (a-bq ^ {i-2}) (1- q ^ {i-1})} {(1-bq ^ {2i-5}) (1-bq ^ {2i-4}) ^ {2} (1-bq ^ {2i-3})}}}$
${ displaystyle alpha ^ {n} cdot left ({ frac {R} { alpha}} right) _ {n}}$	${ displaystyle R}$	${ Displaystyle R + 2 альфа (я-1)}$	${ Displaystyle (я-1) альфа (R + (я-2) альфа)}$
${ Displaystyle (-1) ^ {п} { binom {х} {п}}}$	${ displaystyle -x}$	${ displaystyle - { frac {(x + 2 (i-1) ^ {2})} {(2i-1) (2i-3)}}}$	${ displaystyle { begin {case} - { frac {(x-i + 2) (x + i-1)} {4 cdot (2i-3) ^ {2}}} & i geq 3; - { frac {1} {2}} x (x + 1) & i = 2. end {case}}}$
${ Displaystyle (-1) ^ {п} { binom {х + п} {п}}}$	${ Displaystyle - (х + 1)}$	${ displaystyle { frac {(x-2i (i-2) -1)} {(2i-1) (2i-3)}}}$	${ displaystyle { begin {case} - { frac {(x-i + 2) (x + i-1)} {4 cdot (2i-3) ^ {2}}} & i geq 3; - { frac {1} {2}} x (x + 1) & i = 2. end {case}}}$

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

Примеры

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

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

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

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

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

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

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

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

где у нас есть тождество частного случая для производящей функции делительная функция, ${ Displaystyle д (п) эквив сигма _ {0} (п)}$ , данный

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

Белл серии

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

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

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

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

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

{ Displaystyle OperatorName {DG} (a_ {k}; s) = zeta (s) ^ {m}}

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

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

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

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

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

в

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

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

{ displaystyle { begin {align} e ^ {z + wz} & = sum _ {m, n geq 0} { binom {n} {m}} w ^ {m} { frac {z ^ {n}} {n!}} e ^ {w (e ^ {z} -1)} & = sum _ {m, n geq 0} left {{ begin {matrix} n m end {matrix}} right } w ^ {m} { frac {z ^ {n}} {n!}} { frac {1} {(1-z) ^ {w} }} & = sum _ {m, n geq 0} left [{ begin {matrix} n m end {matrix}} right] w ^ {m} { frac {z ^ {n }} {n!}} { frac {1-w} {e ^ {(w-1) z} -w}} & = sum _ {m, n geq 0} left langle { begin {matrix} n m end {matrix}} right rangle w ^ {m} { frac {z ^ {n}} {n!}} { frac {e ^ {w} -e ^ {z}} {we ^ {z} -ze ^ {w}}} & = sum _ {m, n geq 0} left langle { begin {matrix} m + n + 1 m end {matrix}} right rangle { frac {w ^ {m} z ^ {n}} {(m + n + 1)!}}. end {выравнивается}}}

Приложения

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

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

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

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

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

{ displaystyle H (z) = { dfrac { sum _ {n geq 1} {{ frac {1} {n}} z ^ {n}}} {1-z}} ,,}

и поэтому

{ displaystyle S (z) = sum _ {n geq 1} {s_ {n} z ^ {n}} = { dfrac { sum _ {n geq 1} {{ frac {1} { n}} z ^ {n}}} {(1-z) ^ {2}}} ,.}

С помощью ${ displaystyle { frac {1} {(1-z) ^ {2}}} = sum _ {n geq 0} {(n + 1) z ^ {n}}}$ , свертка с числителем дает

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

который также можно записать как

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

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

В качестве другого примера использования производящих функций для связывания последовательностей и управления суммами для произвольной последовательности ${ Displaystyle langle f_ {п} rangle}$ определим две последовательности сумм

{ displaystyle s_ {n}: = sum _ {m = 0} ^ {n} { binom {n} {m}} f_ {m} 3 ^ {n-m}}

{ displaystyle { widetilde {s}} _ {n}: = sum _ {m = 0} ^ {n} { binom {n} {m}} (m + 1) (m + 2) (m +3) f_ {m} 3 ^ {nm},}

для всех ${ Displaystyle п geq 0}$ , и постарайтесь выразить вторую сумму через первую. Мы предлагаем подход, основанный на производящих функциях.

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

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

Поскольку производящая функция для последовательности ${ Displaystyle langle (п + 1) (п + 2) (п + 3) е_ {п} rangle}$ дан кем-то ${ Displaystyle 6F (z) + 18zF ^ { prime} (z) + 9z ^ {2} F ^ { prime prime} (z) + z ^ {3} F ^ {(3)} (z) }$ , мы можем записать производящую функцию для второй суммы, определенной выше, в виде

{ displaystyle { widetilde {S}} (z) = { frac {6} {(1-3z)}} F left ({ frac {z} {1-3z}} right) + { frac {18z} {(1-3z) ^ {2}}} F ^ { prime} left ({ frac {z} {1-3z}} right) + { frac {9z ^ {2} } {(1-3z) ^ {3}}} F ^ { prime prime} left ({ frac {z} {1-3z}} right) + { frac {z ^ {3}} {(1-3z) ^ {4}}} F ^ {(3)} left ({ frac {z} {1-3z}} right).}

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

{ Displaystyle а (z) cdot S (z) + b (z) cdot zS ^ { prime} (z) + c (z) cdot z ^ {2} S ^ { prime prime} ( z) + d (z) cdot z ^ {3} S ^ {(3)} (z),}

для ${ Displaystyle а (г) = 6 (1-3z) ^ {3}}$ , ${ displaystyle b (z) = 18 (1-3z) ^ {3}}$ , ${ Displaystyle c (z) = 9 (1-3z) ^ {3}}$ , и ${ Displaystyle d (z) = (1-3z) ^ {3}}$ где ${ displaystyle (1-3z) ^ {3} = 1-9z + 27z ^ {2} -27z ^ {3}}$ .

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

{ displaystyle { begin {align} { widetilde {s}} _ {n} & = [z ^ {n}] left (6 (1-3z) ^ {3} sum _ {n geq 0 } s_ {n} z ^ {n} +18 (1-3z) ^ {3} sum _ {n geq 0} ns_ {n} z ^ {n} +9 (1-3z) ^ {3} sum _ {n geq 0} n (n-1) s_ {n} z ^ {n} + (1-3z) ^ {3} sum _ {n geq 0} n (n-1) ( n-2) s_ {n} z ^ {n} right) & = (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 {выравнивается}} }

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

В этом примере мы переформулируем пример производящей функции, приведенный в разделе 7.3. Конкретная математика (см. также раздел 7.1 того же справочника, в котором приведены красивые изображения производящих рядов функций). В частности, предположим, что мы ищем общее количество путей (обозначенных ${ displaystyle U_ {n}}$ ) выложить плитку ${ Displaystyle 3 раз п}$ прямоугольник с немаркированным ${ Displaystyle 2 раз 1}$ домино. Пусть вспомогательная последовательность, ${ displaystyle V_ {n}}$ , можно определить как количество способов покрытия ${ Displaystyle 3 раз п}$ rectangle-minus-corner секция полного прямоугольника. Мы стремимся использовать эти определения, чтобы дать закрытая форма формула для ${ displaystyle U_ {n}}$ не разрушая это определение, чтобы рассмотреть случаи вертикального и горизонтального домино. Обратите внимание, что обычные производящие функции для наших двух последовательностей соответствуют ряду

{ Displaystyle U (z) = 1 + 3z ^ {2} + 11z ^ {4} + 41z ^ {6} + cdots}

{ Displaystyle V (z) = z + 4z ^ {3} + 15z ^ {5} + 56z ^ {7} + cdots.}

Если мы рассмотрим возможные конфигурации, которые можно дать, начиная с левого края ${ Displaystyle 3 раз п}$ прямоугольник, мы можем выразить следующие взаимозависимые, или взаимно рекурсивный, рекуррентные соотношения для наших двух последовательностей, когда ${ Displaystyle п geq 2}$ определено, как указано выше, где ${ displaystyle U_ {0} = 1}$ , ${ displaystyle U_ {1} = 0}$ , ${ displaystyle V_ {0} = 0}$ , и ${ displaystyle V_ {1} = 1}$ :

{ displaystyle { begin {align} U_ {n} & = 2V_ {n-1} + U_ {n-2} V_ {n} & = U_ {n-1} + V_ {n-2}. конец {выровнено}}}

Поскольку у нас есть это для всех целых чисел ${ Displaystyle м geq 0}$ , производящие функции со сдвигом индекса удовлетворяют ${ Displaystyle z ^ {m} G (z) = sum _ {n geq m} g_ {n-m} z ^ {n}}$ (кстати, у нас есть и соответствующая формула, когда ${ displaystyle m <0}$ данный ${ displaystyle sum _ {n geq 0} g_ {n + m} z ^ {n} = { frac {G (z) -g_ {0} -g_ {1} z- cdots -g_ {m) -1} z ^ {m-1}} {z ^ {m}}}}$ ), мы можем использовать указанные выше начальные условия и предыдущие два рекуррентных соотношения, чтобы увидеть, что у нас есть следующие два уравнения, связывающие производящие функции для этих последовательностей, задаваемые формулой

{ Displaystyle { begin {align} 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 {align}}}

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

{ Displaystyle U (z) = { frac {1-z ^ {2}} {1-4z ^ {2} + z ^ {4}}} = { frac {1} {3 - { sqrt { 3}}}} cdot { frac {1} {1- (2 + { sqrt {3}}) z ^ {2}}} + { frac {1} {3 + { sqrt {3} }}} cdot { frac {1} {1- (2 - { sqrt {3}}) z ^ {2}}}.}

Таким образом, выполняя алгебраические упрощения последовательности, полученной в результате разложения производящей функции на вторые частичные дроби в предыдущем уравнении, мы находим, что ${ Displaystyle U_ {2n + 1} эквив 0}$ и это

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

для всех целых чисел ${ Displaystyle п geq 0}$ . Отметим также, что тот же метод сдвинутой производящей функции применяется к второму порядку. повторение для Числа Фибоначчи является прототипическим примером использования производящих функций для решения рекуррентных отношений в одной переменной, уже рассмотренной или, по крайней мере, намекаемой в подразделе рациональные функции приведено выше.

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

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

1. рассмотреть А(z) и B(z) - обычные производящие функции.

{ Displaystyle С (z) = A (z) B (z) Leftrightarrow [z ^ {n}] C (z) = sum _ {k = 0} ^ {n} {a_ {k} b_ {nk }}}

2. рассмотреть А(z) и B(z) - экспоненциальные производящие функции.

{ Displaystyle C (z) = A (z) B (z) Leftrightarrow [z ^ {n} / n!] C (z) = sum _ {k = 0} ^ {n} { binom {n } {k}} a_ {k} b_ {nk}}

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

{ Displaystyle C (z) = F (z) G (z) H (z) Leftrightarrow [z ^ {n}] C (z) = sum _ {j + k + ell = n} f_ {j} g_ {k} h _ { ell}}

4. рассмотрите

{ displaystyle m}

-кратная свертка последовательности с самой собой для некоторого натурального числа

{ Displaystyle м geq 1}

(см. пример приложения ниже)

{ Displaystyle C (z) = G (z) ^ {m} Leftrightarrow [z ^ {n}] C (z) = sum _ {k_ {1} + k_ {2} + cdots + k_ {m } = n} g_ {k_ {1}} g_ {k_ {2}} cdots g_ {k_ {m}}}

Умножение производящих функций или свертка их базовых последовательностей может соответствовать понятию независимых событий в определенных сценариях подсчета и вероятности. Например, если мы примем условное обозначение, что функция, производящая вероятность, или pgf, случайной величины ${ displaystyle Z}$ обозначается ${ Displaystyle G_ {Z} (г)}$ , то можно показать, что для любых двух случайных величин ^[22]

{ Displaystyle G_ {X + Y} (z) = G_ {X} (z) G_ {Y} (z),}

если ${ displaystyle X}$ и ${ displaystyle Y}$ независимы. Точно так же количество способов оплаты ${ Displaystyle п geq 0}$ центов номиналом в монетах достоинств в наборе ${ displaystyle {1,5,10,25,50 }}$ (т. е. в монетах, никелях, десятицентовиках, четвертях и полдолларах соответственно) генерируется продуктом

{ displaystyle C (z) = { frac {1} {1-z}} { frac {1} {1-z ^ {5}}} { frac {1} {1-z ^ {10} }} { frac {1} {1-z ^ {25}}} { frac {1} {1-z ^ {50}}},}

и более того, если мы позволим ${ displaystyle n}$ центов, подлежащих выплате монетами любого положительного целочисленного достоинства, мы приходим к генерированию количества таких комбинаций сдачи, генерируемых функция распределения производящая функция, расширенная бесконечным символ q-Pochhammer продукт ${ Displaystyle prod _ {п geq 1} (1-z ^ {n}) ^ {- 1}}$ .

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

Пример, где полезны свертки производящих функций, позволяет нам решить для конкретной функции замкнутой формы, представляющей обычную производящую функцию для Каталонские числа, ${ displaystyle C_ {n}}$ . В частности, эта последовательность имеет комбинаторную интерпретацию как количество способов вставить круглые скобки в произведение. ${ Displaystyle x_ {0} cdot x_ {1} cdots x_ {n}}$ так что порядок умножения полностью указан. Например, ${ displaystyle C_ {2} = 2}$ что соответствует двум выражениям ${ Displaystyle х_ {0} cdot (х_ {1} cdot x_ {2})}$ и ${ Displaystyle (х_ {0} cdot x_ {1}) cdot x_ {2}}$ . Отсюда следует, что последовательность удовлетворяет рекуррентному соотношению, заданному формулой

{ displaystyle C_ {n} = sum _ {k = 0} ^ {n-1} C_ {k} C_ {n-1-k} + delta _ {n, 0} = C_ {0} C_ { n-1} + C_ {1} C_ {n-2} + cdots + C_ {n-1} C_ {0} + delta _ {n, 0}, n geq 0,}

и поэтому имеет соответствующую свернутую производящую функцию, ${ displaystyle C (z)}$ , удовлетворяющий

{ Displaystyle C (z) = z cdot C (z) ^ {2} +1.}

поскольку ${ Displaystyle С (0) = 1 neq infty}$ , тогда мы приходим к формуле для этой производящей функции, заданной как

{ displaystyle { begin {align} C (z) & = { frac {1 - { sqrt {1-4z}}} {2z}} & = sum _ {n geq 0} { гидроразрыв {1} {n + 1}} { binom {2n} {n}} z ^ {n}. end {align}}}

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

{ Displaystyle С (z) = { гидроразрыва {1} {1-z cdot C (z)}},}

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

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

А поклонник порядка ${ displaystyle n}$ определяется как граф на вершинах ${ Displaystyle {0,1, ldots, п }}$ с участием ${ displaystyle 2n-1}$ ребра соединяются по следующим правилам: Вершина ${ displaystyle 0}$ соединяется одним ребром друг с другом ${ displaystyle n}$ вершины и вершины ${ displaystyle k}$ соединяется одним ребром со следующей вершиной ${ displaystyle k + 1}$ для всех ${ Displaystyle 1 Leq к <п}$ .^[23] Есть один вентилятор первого порядка, три вентилятора второго порядка, восемь вентиляторов третьего порядка и так далее. А остовное дерево является подграфом графа, который содержит все исходные вершины и который содержит достаточно ребер, чтобы сделать этот подграф связным, но не так много ребер, чтобы в подграфе был цикл. Спрашиваем, сколько остовных деревьев ${ displaystyle f_ {n}}$ любителя порядка ${ displaystyle n}$ возможны для каждого ${ Displaystyle п geq 1}$ .

В качестве наблюдения мы можем подойти к вопросу, подсчитав количество способов соединения смежных наборов вершин. Например, когда ${ displaystyle n = 4}$ у нас есть это ${ Displaystyle F_ {4} = 4 + 3 CDOT 1 + 2 CDOT 2 + 1 CDOT 3 + 2 CDOT 1 CDOT 1 + 1 CDOT 2 CDOT 1 + 1 CDOT 1 CDOT 2 + 1 cdot 1 cdot 1 cdot 1 cdot 1 = 21}$ , который представляет собой сумму по ${ displaystyle m}$ -кратные свертки последовательности ${ displaystyle g_ {n} = n = [z ^ {n}] z / (1-z) ^ {2}}$ для ${ displaystyle m: = 1,2,3,4}$ . В более общем смысле, мы можем записать формулу для этой последовательности как

{ displaystyle f_ {n} = sum _ {m> 0} sum _ { scriptstyle k_ {1} + k_ {2} + cdots + k_ {m} = n atop scriptstyle k_ {1}, k_ {2}, ldots, k_ {m}> 0} g_ {k_ {1}} g_ {k_ {2}} cdots g_ {k_ {m}},}

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

{ Displaystyle { begin {align} F (z) & = G (z) + G (z) ^ {2} + G (z) ^ {3} + cdots [6pt] & = { frac {G (z)} {1-G (z)}} [6pt] & = { frac {z} {(1-z) ^ {2} -z}} = { frac {z} { 1–3z + z ^ {2}}}, end {align}}}

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

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

Представляем бесплатный параметр (метод змеиного масла)

Иногда сумма ${ displaystyle s_ {n}}$ сложно, и его не всегда легко оценить. Другой метод (названный Х. Уилфом «змеиное масло») - это метод «свободного параметра» для оценки этих сумм.

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

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

{ displaystyle s_ {n} = sum _ {k geq 0} {{ binom {n + k} {m + 2k}} { binom {2k} {k}} { frac {(-1) ^ {k}} {k + 1}}} quad (m, n in mathbb {N} _ {0})}

мы можем лечить ${ displaystyle n}$ как "свободный" параметр и установите

{ Displaystyle F (Z) = сумма _ {п geq 0} { left [ сумма _ {к geq 0} {{ binom {n + k} {m + 2k}} { binom {2k } {k}} { frac {(-1) ^ {k}} {k + 1}}} right]} z ^ {n}}

Перестановка суммирования («змеиный жир») дает

{ Displaystyle F (z) = sum _ {k geq 0} {{ binom {2k} {k}} { frac {(-1) ^ {k}} {k + 1}} z ^ { -k}} sum _ {n geq 0} {{ binom {n + k} {m + 2k}} z ^ {n + k}}}

Теперь внутренняя сумма ${ displaystyle { frac {z ^ {m + 2k}} {(1-z) ^ {m + 2k + 1}}}}$ . Таким образом

{ displaystyle { begin {align} F (z) & = { frac {z ^ {m}} {(1-z) ^ {m + 1}}} sum _ {k geq 0} {{ frac {1} {k + 1}} { binom {2k} {k}} ({ frac {-z} {(1-z) ^ {2}}}) ^ {k}} & = { frac {z ^ {m}} {(1-z) ^ {m + 1}}} sum _ {k geq 0} {C_ {k} ({ frac {-z} {(1 -z) ^ {2}}}) ^ {k}} quad { text {(где}} C_ {k} = k ^ { text {th}} { text {каталонское число)}} & = { frac {z ^ {m}} {(1-z) ^ {m + 1}}} { frac {1 - { sqrt {1 + { frac {4z} {(1-z) ^ {2}}}}}} { frac {-2z} {(1-z) ^ {2}}}} & = { frac {-z ^ {m-1}} {2 (1 -z) ^ {m-1}}} (1 - { frac {1 + z} {1-z}}) & = { frac {z ^ {m}} {(1-z) ^ {m}}} = z { frac {z ^ {m-1}} {(1-z) ^ {m}}}. end {выравнивается}}}

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

{ displaystyle s_ {n} = { binom {n-1} {m-1}} quad { text {for}} quad m geq 1 quad, quad s_ {n} = [n = 0] quad { text {for}} quad m = 0.}

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

Мы говорим, что две производящие функции (степенные ряды) конгруэнтны по модулю ${ displaystyle m}$ , написано ${ Displaystyle А (г) эквив В (г) { pmod {м}}}$ если их коэффициенты конгруэнтны по модулю ${ displaystyle m}$ для всех ${ Displaystyle п geq 0}$ , т.е. ${ Displaystyle а_ {п} эквив б_ {п} { pmod {м}}}$ для всех соответствующих случаев целых чисел ${ displaystyle n}$ (обратите внимание, что нам не нужно предполагать, что ${ displaystyle m}$ здесь целое число - оно вполне может быть полиномиально значным в некоторых неопределенных ${ displaystyle x}$ , Например). Если "проще"правая производящая функция, ${ displaystyle B (z)}$ , является рациональной функцией ${ displaystyle z}$ , то вид этих последовательностей предполагает, что последовательность в конечном итоге периодический фиксированные по модулю частные случаи целочисленных ${ displaystyle m geq 2}$ . Например, мы можем доказать, что Числа Эйлера, ${ Displaystyle langle E_ {n} rangle = langle 1,1,5,61,1385, ldots rangle longmapsto langle 1,1,2,1,2,1,2, ldots rangle { pmod {3}}}$ , удовлетворяют следующему сравнению по модулю ${ displaystyle 3}$ :^[24]

{ displaystyle sum _ {n geq 0} E_ {n} z ^ {n} = { frac {1-z ^ {2}} {1 + z ^ {2}}} { pmod {3} }.}

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

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

{ Displaystyle А (г)}

представлен бесконечным непрерывная дробь формы

{ displaystyle A (z) = { frac {1} {1-c_ {1} z}} { frac {p_ {1} z ^ {2}} {1-c_ {2} z}} { гидроразрыв {p_ {2} z ^ {2}} {1-c_ {3} z}} cdots,}

и это

{ displaystyle A_ {p} (z)}

обозначает

{ displaystyle p ^ {th}}

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

{ displaystyle a_ {n} = [z ^ {n}] A_ {p} (z)}

для всех

{ displaystyle 0 leq n <2p}

. Тогда 1) функция

{ displaystyle A_ {p} (z)}

рационально для всех

{ displaystyle p geq 2}

где мы предполагаем, что один из критериев делимости

{ displaystyle p | p_ {1}, p_ {1} p_ {2}, p_ {1} p_ {2} p_ {3} cdots}

выполняется, т.е.

{ displaystyle p | p_ {1} p_ {2} cdots p_ {k}}

для некоторых

{ Displaystyle к geq 1}

; и 2) если целое число

{ displaystyle p}

делит продукт

{ displaystyle p_ {1} p_ {2} cdots p_ {k}}

, то имеем

{ Displaystyle А (г) эквив А_ {к} (г) { pmod {р}}}

.

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

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

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

{ displaystyle S_ {n} (x): = sum _ {k = 0} ^ {n} left [{ begin {matrix} n k end {matrix}} right] x ^ {k } = x (x + 1) (x + 2) cdots (x + n-1), n geq 1,}

предоставляет обзор сравнений для этих чисел, полученных строго на основе свойств их производящей функции, как в разделе 4.6 справочника акций Уилфа. Генерацияфункционологии. Мы повторяем основной аргумент и замечаем, что при уменьшении по модулю ${ displaystyle 2}$ каждая из этих производящих функций конечного произведения удовлетворяет

{ Displaystyle S_ {п} (х) = [х (х + 1)] cdot [х (х + 1)] cdots = х ^ { lceil п / 2 rceil} (х + 1) ^ { lfloor n / 2 rfloor},}

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

{ displaystyle left [{ begin {matrix} п k end {matrix}} right] Equiv { binom { lfloor n / 2 rfloor} {k- lceil n / 2 rceil} } { pmod {2}},}

и, следовательно, показывает, что ${ displaystyle left [{ begin {matrix} n k end {matrix}} right]}$ даже когда ${ displaystyle k < left lceil { frac {n} {2}} right rceil}$ .

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

{ Displaystyle { begin {align} left [{ begin {matrix} n m end {matrix}} right] & Equiv [x ^ {m}] left (x ^ { lceil n / 3 rceil} (x + 1) ^ { lceil (n-1) / 3 rceil} (x + 2) ^ { lfloor n / 3 rfloor} right) && { pmod {3}} & Equiv sum _ {k = 0} ^ {m} { binom { lceil (n-1) / 3 rceil} {k}} { binom { lfloor n / 3 rfloor} { mk- lceil n / 3 rceil}} times 2 ^ { lceil n / 3 rceil + lfloor n / 3 rfloor - (mk)} && { pmod {3}}. end {выровнено} }}

Сравнения для статистической суммы

В этом примере мы задействуем часть механизма бесконечных произведений, разложения в степенной ряд которых порождают разложения многих специальных функций и перечисляют функции распределения. В частности, напомним, что то функция распределения ${ Displaystyle р (п)}$ порождается взаимным бесконечным символ q-Pochhammer продукт (или продукт z-Pochhammer, в зависимости от случая), предоставленный

{ Displaystyle { begin {align} sum _ {n geq 1} p (n) z ^ {n} & = { frac {1} {(1-z) (1-z ^ {2}) (1-z ^ {3}) cdots}} [4pt] & = 1 + z + 2z ^ {2} + 3z ^ {3} + 5z ^ {4} + 7z ^ {5} + 11z ^ {6} + cdots. End {align}}}

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

{ displaystyle { begin {align} 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 {align}}}

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

Во-первых, заметим, что производящая функция биномиального коэффициента, ${ Displaystyle 1 / (1-я) ^ {5}}$ , удовлетворяет тому, что каждый из его коэффициентов делится на ${ displaystyle 5}$ за исключением тех, которые соответствуют полномочиям ${ displaystyle 1, z ^ {5}, z ^ {10}, ldots}$ , все из которых в противном случае имеют остаток ${ displaystyle 1}$ по модулю ${ displaystyle 5}$ . Таким образом, мы можем написать

{ displaystyle { frac {1} {(1-z) ^ {5}}} Equiv { frac {1} {1-z ^ {5}}} { pmod {5}} qquad iff qquad { frac {1-z ^ {5}} {(1-z) ^ {5}}} Equiv 1 { pmod {5}},}

что, в частности, показывает нам, что

{ Displaystyle { гидроразрыва {(1-z ^ {5}) (1-z ^ {10}) (1-z ^ {15}) cdots} { left {(1-z) (1- z ^ {2}) (1-z ^ {3}) cdots right } ^ {5}}} Equiv 1 { pmod {5}}.}

Отсюда легко видеть, что ${ displaystyle 5}$ делит каждый коэффициент ${ displaystyle z ^ {5m + 1}}$ в бесконечном произведении разложения

{ Displaystyle г cdot { гидроразрыва {(1-z ^ {5}) (1-z ^ {10}) cdots} {(1-z) (1-z ^ {2}) cdots}} = z cdot left {(1-z) (1-z ^ {2}) cdots right } ^ {4} times { frac {(1-z ^ {5}) (1- z ^ {10}) cdots} { left {(1-z) (1-z ^ {2}) cdots right } ^ {5}}}.}.

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

{ displaystyle { begin {align} & { frac {z} {(1-z) (1-z ^ {2}) cdots}} [5pt] = {} & z cdot { frac { (1-z ^ {5}) (1-z ^ {10}) cdots} {(1-z) (1-z ^ {2}) cdots}} times (1 + z ^ {5} + z ^ {10} + cdots) (1 + z ^ {10} + z ^ {20} + cdots) cdots [5pt] = {} & z + sum _ {n geq 2} p ( п-1) г ^ {п}, end {выровнено}}}

мы можем приравнять коэффициенты при ${ displaystyle z ^ {5m + 5}}$ в предыдущих уравнениях, чтобы доказать желаемый результат сравнения, а именно: ${ Displaystyle р (5м + 4) эквив 0 { pmod {5}}}$ для всех ${ Displaystyle м geq 0}$ .

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

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

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

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

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

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

{ Displaystyle F (z) = int _ {0} ^ { infty} { widehat {F}} (tz) e ^ {- t} , dt}

{ displaystyle { widehat {F}} (z) = { frac {1} {2 pi}} int _ {- pi} ^ { pi} F left (ze ^ {- imath vartheta} right) e ^ {e ^ { imath vartheta}} , d vartheta,}

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

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

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

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

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

Примеры

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

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

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

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

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

{ Displaystyle F (z) ^ {x} = exp left (x log F (z) right) = sum _ {n geq 0} f_ {n} (x) z ^ {n}, }

для некоторой аналитической функции ${ displaystyle F}$ с расширением степенного ряда так, что ${ Displaystyle F (0) = 1}$ . Мы говорим, что семейство многочленов, ${ displaystyle f_ {0}, f_ {1}, f_ {2}, ldots}$ , образует извилистая семья если ${ Displaystyle deg {е_ {п} } Leq п}$ и если выполняется следующее условие свертки для всех ${ displaystyle x, y}$ и для всех ${ Displaystyle п geq 0}$ :

{ displaystyle f_ {n} (x + y) = f_ {n} (x) f_ {0} (y) + f_ {n-1} (x) f_ {1} (y) + cdots + f_ { 1} (x) f_ {n-1} (y) + f_ {0} (x) f_ {n} (y).}

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

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

Последовательность ${ Displaystyle п! CDOT F_ {п} (х)}$ имеет биномиальный тип
Специальные значения последовательности включают ${ displaystyle f_ {n} (1) = [z ^ {n}] F (z)}$ и ${ displaystyle f_ {n} (0) = delta _ {n, 0}}$ , и
Для произвольных (фиксированных) ${ displaystyle x, y, t in mathbb {C}}$ эти многочлены удовлетворяют формулам свертки вида

{ Displaystyle { begin {align} f_ {n} (x + y) & = sum _ {k = 0} ^ {n} f_ {k} (x) f_ {nk} (y) f_ { n} (2x) & = sum _ {k = 0} ^ {n} f_ {k} (x) f_ {nk} (x) xnf_ {n} (x + y) & = (x + y ) sum _ {k = 0} ^ {n} kf_ {k} (x) f_ {nk} (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_ {nk} (y + t (nk))} {y + t (nk)}}. end {align}}}

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

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

где ${ Displaystyle { mathcal {F}} _ {т} (г)}$ неявно определяется функциональное уравнение формы ${ displaystyle { mathcal {F}} _ {t} (z) = F left (x { mathcal {F}} _ {t} (z) ^ {t} right)}$ . Более того, мы можем использовать матричные методы (как в справочнике), чтобы доказать, что с учетом двух последовательностей полиномов свертки, ${ Displaystyle langle f_ {п} (х) rangle}$ и ${ Displaystyle langle g_ {п} (х) rangle}$ , с соответствующими производящими функциями, ${ Displaystyle F (г) ^ {х}}$ и ${ Displaystyle G (г) ^ {х}}$ , то для произвольных ${ displaystyle t}$ у нас есть личность

{ Displaystyle [z ^ {n}] влево (G (z) F left (zG (z) ^ {t} right) right) ^ {x} = sum _ {k = 0} ^ { n} F_ {k} (x) G_ {nk} (x + tk).}

Примеры полиномиальных последовательностей свертки включают биномиальный степенной ряд, ${ displaystyle { mathcal {B}} _ {t} (z) = 1 + z { mathcal {B}} _ {t} (z) ^ {t}}$ , так называемый древовидные многочлены, то Номера звонков, ${ Displaystyle B (п)}$ , то Полиномы Лагерра, а Полиномы свертки Стирлинга.

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

Найден начальный список специальных математических рядов. Вот. Ряд полезных и специальных функций генерации последовательностей можно найти в разделах 5.4 и 7.4. Конкретная математика и в разделе 2.5 Уилфа Генерацияфункционологии. Другие особые функции генерации, которые следует отметить, включают записи в следующей таблице, которая никоим образом не является полной.^[28]

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

История

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

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

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

Заметки

^ Дональд Э. Кнут, Искусство программирования, Том 1. Основные алгоритмы (третье издание) Эддисон-Уэсли. ISBN 0-201-89683-4. Раздел 1.2.9: «Производящие функции».
^ Этот альтернативный термин уже можно найти у Е.Н. Гилберт (1956), «Перечисление помеченных графов», Канадский математический журнал 3, п. 405–411, но его использование редко до 2000 года; с тех пор он, кажется, увеличивается.
^ Флажолет и Седжвик (2009), стр.95.
^ Апостол, Том М. (1976), Введение в аналитическую теорию чисел, Тексты для бакалавриата по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, Г-Н 0434929, Zbl 0335.10001 стр.42–43
^ Уилф (1994) стр.56
^ Уилф (1994) стр.59
^ Харди и Райт (2008). Введение в теорию чисел (Шестое изд.). Нью-Йорк: Издательство Оксфордского университета. п.339.
^ Спайви, Майкл З. (2007). «Комбинаторные суммы и конечные разности». Дискретная математика. 307 (24): 3130–3146. Дои:10.1016 / j.disc.2007.03.052. Г-Н 2370116.
^ Матар, Р. Дж. (2012). «Еще одна таблица интегралов». arXiv:1207.5845 [math.CA ]. v4 экв. (0,4)
^ См. Таблицу 265 в разделе 6.1. Конкретная математика для тождеств с конечной суммой, включающих треугольники с числами Стирлинга.
^ См. Раздел 2.4 в книге Ландо. Лекции по генерирующим функциям (2002).
^ Пример из раздела 6.3 книги Р. П. Стэнли. Перечислительная комбинаторика (Том 2).
^ См. Раздел 1.2.9 в книге Кнута. Искусство программирования (Том 1).
^ Решение упражнения 7.36 на странице 569 в книге Грэма, Кнута и Патшника.
^ Флажолет и Седжвик (2010). Аналитическая комбинаторика. Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-89806-5. (Раздел B.4)
^ Шнайдер, К. (2007). «Символьное суммирование помогает комбинаторике». Сем.ЛотарьКомбинат. 56: 1–36.
^ См. Статью П. Флажоле. Комбинаторные аспекты непрерывных дробей (1980), а также ссылаются на работу Х.С. Аналитическая теория цепных дробей (1948) для более полной информации о свойствах J-дробей.
^
См. Следующие статьи:
^ «Идентичность серии Ламберта». Математическое переполнение. 2017.
^ Хорошо, И. Дж. (1986). «О приложениях симметричных распределений Дирихле и их смесей к таблицам сопряженности». Анналы статистики. 4 (6): 1159–1189. Дои:10.1214 / aos / 1176343649.
^ См. Использование этих терминов в разделе 7.4. Конкретная математика о специальных функциях, производящих последовательность.
^ Раздел 8.3 в Конкретная математика.
^ См. Пример 6 в разделе 7.3. Конкретная математика для другого метода и полной настройки этой задачи с помощью генерирующих функций. Это больше "запутанный"подход изложен в разделе 7.5 той же ссылки.
^ См. Раздел 5 Ландо Лекции по генерирующим функциям.
^ См. Раздел 19.12 классической книги Харди и Райта. Введение в теорию чисел.
^ Решение упражнения 5.71 на странице 535 в Конкретная математика Грэхем, Кнут и Паташник.
^ Кнут, Д. Э. (1992). «Полиномы свертки». Mathematica J. 2: 67–78. arXiv:математика / 9207221. Bibcode:1992математика ...... 7221K.
^ См. Также 1031 Генерирующие функции найдено в упомянутой статье Вот.

использованная литература

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

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

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

[1] Дональд Э. Кнут, Искусство программирования, Том 1. Основные алгоритмы (третье издание) Эддисон-Уэсли. ISBN 0-201-89683-4. Раздел 1.2.9: «Производящие функции».

[2] Этот альтернативный термин уже можно найти у Е.Н. Гилберт (1956), «Перечисление помеченных графов», Канадский математический журнал 3, п. 405–411, но его использование редко до 2000 года; с тех пор он, кажется, увеличивается.

[3] Флажолет и Седжвик (2009), стр.95.

[4] Апостол, Том М. (1976), Введение в аналитическую теорию чисел, Тексты для бакалавриата по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, Г-Н 0434929, Zbl 0335.10001 стр.42–43

[W56-5] Уилф (1994) стр.56

[W59-6] Уилф (1994) стр.59

[7] Харди и Райт (2008). Введение в теорию чисел (Шестое изд.). Нью-Йорк: Издательство Оксфордского университета. п.339.

[8] Спайви, Майкл З. (2007). «Комбинаторные суммы и конечные разности». Дискретная математика. 307 (24): 3130–3146. Дои:10.1016 / j.disc.2007.03.052. Г-Н 2370116.

[9] Матар, Р. Дж. (2012). «Еще одна таблица интегралов». arXiv:1207.5845 [math.CA ]. v4 экв. (0,4)

[10] См. Таблицу 265 в разделе 6.1. Конкретная математика для тождеств с конечной суммой, включающих треугольники с числами Стирлинга.

[GFLECT-11] См. Раздел 2.4 в книге Ландо. Лекции по генерирующим функциям (2002).

[12] Пример из раздела 6.3 книги Р. П. Стэнли. Перечислительная комбинаторика (Том 2).

[TAOCPV1-13] См. Раздел 1.2.9 в книге Кнута. Искусство программирования (Том 1).

[14] Решение упражнения 7.36 на странице 569 в книге Грэма, Кнута и Патшника.

[15] Флажолет и Седжвик (2010). Аналитическая комбинаторика. Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-89806-5. (Раздел B.4)

[16] Шнайдер, К. (2007). «Символьное суммирование помогает комбинаторике». Сем.ЛотарьКомбинат. 56: 1–36.

[17] См. Статью П. Флажоле. Комбинаторные аспекты непрерывных дробей (1980), а также ссылаются на работу Х.С. Аналитическая теория цепных дробей (1948) для более полной информации о свойствах J-дробей.

[18] См. Следующие статьи:
Непрерывные дроби для функций, производящих квадратный ряд (2016)
Непрерывные дроби типа Якоби для обыкновенных производящих функций обобщенных факторных функций (2017)
Цепные дроби типа Якоби и сравнения для биномиальных коэффициентов по модулю целых чисел ${ displaystyle h geq 2}$ (2017)

[19] Непрерывные дроби для функций, производящих квадратный ряд (2016)

[20] Непрерывные дроби типа Якоби для обыкновенных производящих функций обобщенных факторных функций (2017)

[21] Цепные дроби типа Якоби и сравнения для биномиальных коэффициентов по модулю целых чисел ${ displaystyle h geq 2}$ (2017)

[19] «Идентичность серии Ламберта». Математическое переполнение. 2017.

[Good_1986-20] Хорошо, И. Дж. (1986). «О приложениях симметричных распределений Дирихле и их смесей к таблицам сопряженности». Анналы статистики. 4 (6): 1159–1189. Дои:10.1214 / aos / 1176343649.

[21] См. Использование этих терминов в разделе 7.4. Конкретная математика о специальных функциях, производящих последовательность.

[22] Раздел 8.3 в Конкретная математика.

[23] См. Пример 6 в разделе 7.3. Конкретная математика для другого метода и полной настройки этой задачи с помощью генерирующих функций. Это больше "запутанный"подход изложен в разделе 7.5 той же ссылки.

[24] См. Раздел 5 Ландо Лекции по генерирующим функциям.

[25] См. Раздел 19.12 классической книги Харди и Райта. Введение в теорию чисел.

[26] Решение упражнения 5.71 на странице 535 в Конкретная математика Грэхем, Кнут и Паташник.

[27] Кнут, Д. Э. (1992). «Полиномы свертки». Mathematica J. 2: 67–78. arXiv:математика / 9207221. Bibcode:1992математика ...... 7221K.

[28] См. Также 1031 Генерирующие функции найдено в упомянутой статье Вот.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

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

Определения

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

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

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

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

Белл серии

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

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

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

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

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

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

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

Индексы смещения последовательности

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

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

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

Определения

Примеры

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

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

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

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

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

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

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

Определения

Свойства часth сходящиеся функции

Примеры

Примеры

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

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

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

Белл серии

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

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

Приложения

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

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

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

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

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

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

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

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

Представляем бесплатный параметр (метод змеиного масла)

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

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

Сравнения для статистической суммы

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

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

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

Примеры

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

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

История

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

Заметки

использованная литература

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

Свойства $час$ ^th сходящиеся функции