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

Производя́щая фу́нкция после́довательности — алгебраическое понятие, которое позволяет работать с разными комбинаторными объектами аналитическими методами. Они дают гибкий способ описывать соотношения в комбинаторике, а иногда помогают вывести явные формулы для числа комбинаторных объектов определённого типа.

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

Близким понятием является экспоненциальная производящая функция последовательности  — степенной ряд
 ,
у которого коэффициент перед  поделён на факториал числа .

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

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

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

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

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

В комбинаторике 
Число композиций

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

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

Число связных графов
Обозначим через  число всех графов с вершинами  и через  число всех связных графов с этими вершинами.

Заметим, что . В частности легко посчитать первые члены этой последовательности
 

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

В теории вероятностей 
 Если  — положительная целочисленная случайная величина (частный случай дискретной), имеющая распределение вероятностей
 
то её математическое ожидание может быть выражено через производящую функцию последовательности 
 
как значение первой производной в единице:  (стоит отметить, что ряд для P(s) сходится, по крайней мере, при ). Действительно,
 

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

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

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

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

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

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

 Производящей функцией Дирихле последовательности единиц 1,1,… является дзета-функция Римана:
 

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

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

Примечания

Литература

Ссылки 
 Производящие функции

Комбинаторика
Теория вероятностей