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

.

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

и

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

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

Метод производящих функций был разработан Эйлером в 1750-х годах.

Свойства

• Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.
• Произведение производящих функций и последовательностей и является производящей функцией свёртки этих последовательностей:

Примеры использования

В комбинаторике

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

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

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

В теории вероятностей

• Если — положительная целочисленная случайная величина (частный случай дискретной), имеющая распределение вероятностей

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

как значение первой производной в единице: (стоит отметить, что ряд для P(s) сходится, по крайней мере, при ). Действительно,

При подстановке получим величину , которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то -- а имеет бесконечное математическое ожидание,

• Теперь возьмём производящую функцию последовательности «хвостов» распределения

Эта производящая функция связана с определённой ранее функцией свойством: при . Из этого по теореме о среднем следует, что математическое ожидание равно просто значению этой функции в единице:

• Диференцируя и используя соотношение , получим:

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

.

В случае бесконечной дисперсии .

Вариации и обобщения

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

  .

  • Если и — экспоненциальные производящие функции последовательностей и , то их произведение является экспоненциальной производящей функцией последовательности .

Литература

• Бронштейн Е. М. Производящие функции // Соросовский Образовательный Журнал. — 2001. — Т. 7. — № 2. — С. 103—108.
• Воронин С., Кулагин А. Метод производящих функций // Квант. — 1984. — № 5.
• Ландо С. К. Лекции по комбинаторике. — МЦНМО, 1994.
• В. Феллер. Глава XI. Целочисленные величины. Производящие функции // Введение в теорию вероятностей и её приложения = An introduction to probability theory and its applicatons / Пер. с англ. Р. Л. Добрушина, А. А. Юшкевича, С. А. Молчанова; С предисловием А. Н. Колмогорова; Под ред. Е. Б. Дынкина. — 2-е изд. — М.: Мир, 1964. — С. 270—272.
• Herbert S. Wilf. Generatingfunctionology. — Academic Press, 1994. — ISBN 0-12-751956-4

Ссылки

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