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

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

Если дана последовательность чисел , то из них можно построить формальный степенной ряд

,

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

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

,

у которого коэффициент перед поделён на факториал числа .

Содержание

Замечания

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

  и  

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

Свойства

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

Примеры использования

В комбинаторике

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

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

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

 

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

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

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

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

 

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

 
 

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

 

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

 

В теории вероятностей

 

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

 

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

 

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

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

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

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

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

 .

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

Вариации и обобщения

Производящая функция Дирихле

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

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

История

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

Примечания

  1. Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.

Литература

Ссылки