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

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

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

Зачастую производящая функция интересующей последовательности $\{ a_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 \}$, то $A(x)B(x)=\sum_{n=0}^\infty c_n x^n$, где $c_n = \sum_{k=0}^n a_k b_{n-k}$.

Примеры

Пусть $B_m^n$ — это число сочетаний с повторениями, то есть представлений числа $n$ в виде $n=k_1+k_2+\cdots+k_m$, где $\{k_i\}$ — неотрицательные целые числа. Тогда

$\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} = m(m+1)\cdots(m+n-1)/n! = {m+n-1 \choose n}.$

Применение в теории вероятностей

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

$\mathbb{P}(X=j) = p_i,\; j=0,1,...;\quad \sum\limits_{j=0}^{\infty} p_j = 1$

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

$P(s)=\sum_{k=0}^\infty\;p_k s^k$ (заметим, что ряд сходится по-крайней мере при $|s|<1$)

как значение первой производной в единице: $M[X] = P'(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, Volume I second edition / Под ред. Е. Б. Дынкина. — 2-е изд. — М.: Мир, 1964. — С. 270—272.

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Производящая функция последовательности. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---