13-06-2023
Производя́щая фу́нкция последовательности — это формальный степенной ряд
Зачастую производящая функция последовательности чисел является рядом Тейлора некоторой аналитической функции, что может использоваться для изучения свойств самой последовательности. Однако, в общем случае производящая функция не обязана быть аналитической. Например, оба ряда
имеют радиус сходимости ноль, то есть расходятся во всех точках, кроме нуля, а в нуле оба равны 1, то есть как функции они совпадают; тем не менее, как формальные ряды они различаются.
Производящие функции дают возможность просто описывать многие сложные последовательности в комбинаторике, а иногда помогают найти для них явные формулы.
Метод производящих функций был разработан Эйлером в 1750-х годах.
Содержание |
Пусть — это количество композиций неотрицательного целого числа n длины m, то есть, представлений n в виде , где — неотрицательные целые числа. Число также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества (при этом каждый член в композиции можно трактовать как количество элементов i в выборке).
При фиксированном m производящей функцией последовательности является:
Поэтому число может быть найдено как коэффициент при в разложении по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:
то её математическое ожидание может быть выражено через производящую функцию последовательности
как значение первой производной в единице: (стоит отметить, что ряд для P(s) сходится, по крайней мере, при ). Действительно,
При подстановке получим величину , которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то -- а имеет бесконечное математическое ожидание,
Эта производящая функция связана с определённой ранее функцией свойством: при . Из этого по теореме о среднем следует, что математическое ожидание равно просто значению этой функции в единице:
Чтобы получить дисперсию , к этому выражению надо прибавить , что приводит к следующим формулам для вычисления дисперсии:
В случае бесконечной дисперсии .
Производящая функция последовательности.