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