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

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

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

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

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

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

$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$,

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

Замечания

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \dots$

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

$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$

$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$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$M[X]=P'(1)=Q(1)$

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

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

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

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

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

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

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

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

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

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

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

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

История

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

Литература

• Бронштейн Е. М. Производящие функции // Соросовский Образовательный Журнал. — 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.

Ссылки

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