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

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

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

Определение[править | править код]

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

.

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

.

Замечания[править | править код]

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

и

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

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

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

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

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

Число композиций

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

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

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

Чилсо связных графов

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

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

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

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

из которого следует простое рекуррентное соотношение для , позволяющее быстро найти первые члены этой последовательности[2]

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

Примечания[править | править код]

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.
  2. Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.

Литература[править | править код]

  • Табачников С.Л., Фукс Д.Б. Математический дивертисмент. — МЦНМО, 2011. — ISBN 978-5-94057-731-7.
  • В. Феллер. Глава XI. Целочисленные величины. Производящие функции // Введение в теорию вероятностей и её приложения = An introduction to probability theory and its applicatons / Пер. с англ. Р. Л. Добрушина, А. А. Юшкевича, С. А. Молчанова; С предисловием А. Н. Колмогорова; Под ред. Е. Б. Дынкина. — 2-е изд. — М.: Мир, 1964. — С. 270—272.

Ссылки[править | править код]