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

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

Если дана последовательность ${\displaystyle \{a_{n}\}}$ чисел ${\displaystyle a_{0},a_{1},a_{2},a_{3},\ldots }$, то из них можно построить формальный степенной ряд

${\displaystyle A(t)=\sum _{n=0}^{\infty }a_{n}t^{n}=a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+\dotsb }$,

который называется производящей функцией ${\displaystyle A(t)}$ этой последовательности.

Близким понятием является экспоненциальная производящая функция последовательности ${\displaystyle \{a_{n}\}}$ — степенной ряд

${\displaystyle A(t)=\sum _{n=0}^{\infty }{\frac {a_{n}t^{n}}{n!}}=a_{0}+a_{1}t+{\frac {a_{2}}{2}}t^{2}+{\frac {a_{3}}{6}}t^{3}+\dotsb }$,

у которого коэффициент перед ${\displaystyle t^{n}}$ поделён на факториал числа ${\displaystyle n}$.

Замечания

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

${\displaystyle \sum _{n=0}^{\infty }(3^{n})^{n}x^{n}}$ и ${\displaystyle \sum _{n=0}^{\infty }(2^{n})^{n}x^{n}}$

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

Свойства

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

• Произведение производящих функций ${\displaystyle A(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$ и ${\displaystyle B(x)=\sum _{n=0}^{\infty }b_{n}x^{n}}$ последовательностей ${\displaystyle \{a_{n}\}}$ и ${\displaystyle \{b_{n}\}}$ является производящей функцией свёртки ${\displaystyle c_{n}=\sum _{k=0}^{n}a_{k}b_{n-k}}$ этих последовательностей:

${\displaystyle A(x)B(x)=\sum _{n=0}^{\infty }c_{n}x^{n}.}$

• Если ${\displaystyle A(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$ и ${\displaystyle B(x)=\sum _{n=0}^{\infty }b_{n}{\frac {x^{n}}{n!}}}$ — экспоненциальные производящие функции последовательностей ${\displaystyle \{a_{n}\}}$ и ${\displaystyle \{b_{n}\}}$, то их произведение ${\displaystyle A(x)\cdot B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!}}}$ является экспоненциальной производящей функцией последовательности ${\displaystyle c_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{n-k}}$.

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

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

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

Пусть ${\displaystyle B_{m}^{n}}$ — это количество композиций целого положительного числа n длины m, то есть, представлений n в виде ${\displaystyle n=k_{1}+k_{2}+\cdots +k_{m}}$, где ${\displaystyle \{k_{i}\}}$ — целые положительные числа. Число ${\displaystyle B_{m}^{n}}$ также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества ${\displaystyle \{1,2,\dots ,m\}}$ (при этом каждый член ${\displaystyle k_{i}}$ в композиции можно трактовать как количество элементов i в выборке).

При фиксированном m производящей функцией последовательности ${\displaystyle B_{m}^{0},B_{m}^{1},\dots }$ является:

${\displaystyle \sum _{n=0}^{\infty }B_{m}^{n}x^{n}=(1+x+x^{2}+\cdots )^{m}=(1-x)^{-m}.}$

Поэтому число ${\displaystyle B_{m}^{n}}$ может быть найдено как коэффициент при ${\displaystyle x^{n}}$ в разложении ${\displaystyle (1-x)^{-m}}$ по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:

${\displaystyle B_{m}^{n}=(-1)^{n}{-m \choose n}={\frac {m(m+1)\cdots (m+n-1)}{n!}}={m+n-1 \choose n}.}$

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

Обозначим через ${\displaystyle a_{n}}$ число всех графов с вершинами ${\displaystyle \{1,\dots ,n\}}$ и через ${\displaystyle c_{n}}$ число всех связных графов с этими вершинами.

Заметим, что ${\displaystyle a_{n}=2^{\binom {n}{2}}}$. В частности легко посчитать первые члены этой последовательности

${\displaystyle 1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \dots }$

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

${\displaystyle a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n!}}\cdot a_{n}\cdot x^{n}+\dots }$

${\displaystyle c(x)=c_{1}\cdot x+{\tfrac {1}{2}}\cdot c_{2}\cdot x^{2}+\dots +{\tfrac {1}{n!}}\cdot c_{n}\cdot x^{n}+\dots }$

Оба ряда расходятся при ${\displaystyle x\neq 0}$, тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:

${\displaystyle 1+a(x)=e^{c(x)},}$

из которого следует простое рекуррентное соотношение для ${\displaystyle c_{n}}$, позволяющее быстро найти первые члены этой последовательности^[1]

${\displaystyle 1,\ 1,\ 4,\ 38,\ 728,\ 26704,\ 1866256,\ 251548592,\ 66296291072,\ \dots }$

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

• Если ${\displaystyle X}$ — положительная целочисленная случайная величина (частный случай дискретной), имеющая распределение вероятностей

${\displaystyle \mathbb {P} (X=j)=p_{j},\;j=0,1,...;\quad \sum \limits _{j=0}^{\infty }p_{j}=1}$

то её математическое ожидание может быть выражено через производящую функцию последовательности ${\displaystyle \{p_{i}\}}$

${\displaystyle P(s)=\sum _{k=0}^{\infty }\;p_{k}s^{k},}$

как значение первой производной в единице: ${\displaystyle M[X]=P'(1)}$ (стоит отметить, что ряд для P(s) сходится, по крайней мере, при ${\displaystyle |s|\leq 1}$). Действительно,

${\displaystyle P'(s)=\sum _{k=1}^{\infty }{kp_{k}s^{k-1}}.}$

При подстановке ${\displaystyle s=1}$ получим величину ${\displaystyle P'(1)=\sum _{k=1}^{\infty }{kp_{k}}}$, которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то ${\displaystyle \lim _{s\to 1}P'(s)=\infty }$ — а ${\displaystyle X}$ имеет бесконечное математическое ожидание, ${\displaystyle P'(1)=M[X]=\infty }$

• Теперь возьмём производящую функцию ${\displaystyle Q(s)}$ последовательности «хвостов» распределения ${\displaystyle \{q_{k}\}}$

${\displaystyle q_{k}=\mathbb {P} (X>k)=\sum _{j=k+1}^{\infty }{p_{j}};\quad Q(s)=\sum _{k=0}^{\infty }\;q_{k}s^{k}.}$

Эта производящая функция связана с определённой ранее функцией ${\displaystyle P(s)}$ свойством: ${\displaystyle Q(s)={\frac {1-P(s)}{1-s}}}$ при ${\displaystyle |s|<1}$. Из этого по теореме о среднем следует, что математическое ожидание равно значению этой функции в единице:

${\displaystyle M[X]=P'(1)=Q(1)}$

• Дифференцируя ${\displaystyle P'(s)=\sum _{k=1}^{\infty }{kp_{k}s^{k-1}}}$ и используя соотношение ${\displaystyle P'(s)=Q(s)-(1-s)Q'(s)}$, получим:

${\displaystyle M[X(X-1)]=\sum {k(k-1)p_{k}}=P''(1)=2Q'(1)}$

Чтобы получить дисперсию ${\displaystyle D[X]}$, к этому выражению надо прибавить ${\displaystyle M[X]-M^{2}[X]}$, что приводит к следующим формулам для вычисления дисперсии:

${\displaystyle D[X]=P''(1)+P'(1)-P'^{2}(1)=2Q'(1)+Q(1)-Q^{2}(1)}$.

В случае бесконечной дисперсии ${\displaystyle \lim _{s\to 1}P''(s)=\infty }$.

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

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

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

${\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}}$.

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

  ${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}.}$

• Если ${\displaystyle \alpha (s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}}$ и ${\displaystyle \beta (s)=\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}}$ — производящие функции Дирихле последовательностей ${\displaystyle \{a_{n}\}}$ и ${\displaystyle \{b_{n}\}}$, то их произведение ${\displaystyle \alpha (s)\cdot \beta (s)=\sum _{n=0}^{\infty }{\frac {c_{n}}{n^{s}}}}$ является производящей функцией Дирихле свёртки Дирихле — последовательности ${\displaystyle c_{n}=\sum _{d\mid n}a_{d}b_{n/d}}$.

История

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

Примечания

1. Харари Ф., Палмер Э. Перечисление графов. — Мир, 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.

Ссылки

• Производящие функции