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

• Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.
• Произведение производящих функций ${\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 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 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>j)=\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=0}^{\infty }a_{n}{\frac {x^{n}}{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)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}}$ .

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

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