Производя́щая фу́нкция после́довательности — алгебраическое понятие, которое позволяет работать с разными комбинаторными объектами аналитическими методами. Они дают гибкий способ описывать соотношения в комбинаторике, а иногда помогают вывести явные формулы для числа комбинаторных объектов определённого типа.
Если дана последовательность
чисел
, то из них можно построить формальный степенной ряд
-
,
который называется производящей функцией
этой последовательности.
Близким понятием является экспоненциальная производящая функция последовательности
— степенной ряд
-
,
у которого коэффициент перед
поделён на факториал числа
.
Замечания
Зачастую производящая функция последовательности чисел является рядом Тейлора некоторой аналитической функции, что может использоваться для изучения свойств самой последовательности. Однако, в общем случае производящая функция не обязана быть аналитической. Например, оба ряда
-
и
имеют радиус сходимости ноль, то есть расходятся во всех точках, кроме нуля, а в нуле оба равны 1, то есть как функции они совпадают; тем не менее, как формальные ряды они различаются.
Свойства
- Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.
- Произведение производящих функций
и
последовательностей
и
является производящей функцией свёртки
этих последовательностей:
-
- Если
и
— экспоненциальные производящие функции последовательностей
и
, то их произведение
является экспоненциальной производящей функцией последовательности
.
Примеры использования
В комбинаторике
- Число композиций
Пусть
— это количество композиций неотрицательного целого числа n длины m, то есть, представлений n в виде
, где
— неотрицательные целые числа. Число
также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества
(при этом каждый член
в композиции можно трактовать как количество элементов i в выборке).
При фиксированном m производящей функцией последовательности
является:
-
Поэтому число
может быть найдено как коэффициент при
в разложении
по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:
-
- Число связных графов
Обозначим через
число всех графов с вершинами
и через
число всех связных графов с этими вершинами.
Заметим, что
. В частности легко посчитать первые члены этой последовательности
-
Рассмотрим экспоненциальные производящие функции этих последовательностей:
-
-
Оба ряда расходятся при
, тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:
-
из которого следует простое рекуррентное соотношение для
, позволяющее быстро найти первые члены этой последовательности[1]
-
В теории вероятностей
-
то её математическое ожидание может быть выражено через производящую функцию последовательности
-
как значение первой производной в единице:
(стоит отметить, что ряд для P(s) сходится, по крайней мере, при
). Действительно,
-
При подстановке
получим величину
, которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то
— а
имеет бесконечное математическое ожидание,
- Теперь возьмём производящую функцию
последовательности «хвостов» распределения
-
Эта производящая функция связана с определённой ранее функцией
свойством:
при
.
Из этого по теореме о среднем следует, что математическое ожидание равно просто значению этой функции в единице:
-
- Дифференцируя
и используя соотношение
, получим:
-
Чтобы получить дисперсию
, к этому выражению надо прибавить
, что приводит к следующим формулам для вычисления дисперсии:
-
.
В случае бесконечной дисперсии
.
Примечания
- ↑ Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
Литература
- Бронштейн Е. М. Производящие функции // Соросовский Образовательный Журнал. — 2001. — Т. 7, № 2. — С. 103—108.
- Воронин С., Кулагин А. Метод производящих функций // Квант. — 1984. — № 5.
- Ландо С. К. Лекции по комбинаторике. — МЦНМО, 1994.
- Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. (недоступная ссылка)
- Табачников С.Л., Фукс Д.Б. Математический дивертисмент. — МЦНМО, 2011. — ISBN 978-5-94057-731-7.
- Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.
- В. Феллер. Глава 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.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .