Производящая функция последовательности | это... Что такое Производящая функция последовательности? (original) (raw)
Производя́щая фу́нкция последовательности — это формальный степенной ряд
.
Зачастую производящая функция последовательности чисел является рядом Тейлора некоторой аналитической функции, что может использоваться для изучения свойств самой последовательности. Однако, в общем случае производящая функция не обязана быть аналитической. Например, оба ряда
и
имеют радиус сходимости ноль, то есть расходятся во всех точках, кроме нуля, а в нуле оба равны 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