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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

Метод был разработан Эйлером в 1750-х годах.

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

Производя́щая фу́нкция (или генератри́са[источник не указан 231 день]) последовательности — это формальный степенной ряд

.

Комментарий[править | править вики-текст]

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

и

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

Свойства[править | править вики-текст]

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

Примеры использования[править | править вики-текст]

В комбинаторике[править | править вики-текст]

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

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

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

В теории вероятностей[править | править вики-текст]

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

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

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

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

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

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

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

.

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

Вариации и обобщения[править | править вики-текст]

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

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

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

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]