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

У этого термина существуют и другие значения, см. Производящая функция.

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

$\sum_{n=0}^\infty a_n x^n$.

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

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

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

Производящие функции дают возможность просто описывать многие сложные последовательности в комбинаторике, а иногда помогают найти для них явные формулы.

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

Свойства

• Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.
• Произведение производящих функций $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.$

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

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

Пусть $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}.$

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

• Если $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|\le 1$). Действительно,

$P'(s)=\sum_{k=1}^\infty{k p_k s^{k-1}}.$

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

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

$q_k=\mathbb{P}(X>j)=\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{k p_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=0}^\infty a_n \frac{x^n}{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)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}$.

Литература

• Бронштейн Е. М. Производящие функции // Соросовский Образовательный Журнал. — 2001. — Т. 7. — № 2. — С. 103—108.
• Воронин С., Кулагин А. Метод производящих функций // Квант. — 1984. — № 5.
• Ландо С. К. Лекции по комбинаторике. — МЦНМО, 1994.
• В. Феллер. Глава 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

Ссылки

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