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

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

Если дана последовательность $\{a_n\}$$\{a_{n}\}$ чисел $a_0,a_1,a_2,a_3,\dots <!--\; \dots \; -->$$a_{0},a_{1},a_{2},a_{3},\ldots$, то из них можно построить формальный степенной ряд

$A(t)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_n{t}^n=a_0+a_{1}t+a_2{t}^2+a_3{t}^3+\cdots <!--\; \cdots \; -->$$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(t)$ этой последовательности.

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

$A(t)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n{t}^n}{n!}=a_0+a_{1}t+\frac{a_2}{2}{t}^2+\frac{a_3}{6}{t}^3+\cdots <!--\; \cdots \; -->$$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$$a_n$ поделён на факториал числа $n$$n$.

ЗамечанияПравить

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

$\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(3^n{)}^n{x}^n$$\sum _{{n=0}}^{\infty }(3^{n})^{n}x^{n}$  и $\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(2^n{)}^n{x}^n$$\sum _{{n=0}}^{\infty }(2^{n})^{n}x^{n}$ 

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

СвойстваПравить

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

• Произведение производящих функций $A(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_n{x}^n$$A(x)=\sum _{{n=0}}^{\infty }a_{n}x^{n}$  и $B(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{b}_n{x}^n$$B(x)=\sum _{{n=0}}^{\infty }b_{n}x^{n}$  последовательностей $\{a_n\}$$\{a_{n}\}$  и $\{b_n\}$$\{b_{n}\}$  является производящей функцией свёртки $c_n=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_k{b}_{n-<!--\; -\; -->k}$$c_{n}=\sum _{{k=0}}^{n}a_{k}b_{{n-k}}$  этих последовательностей:

$A(x)B(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_n{x}^n.$$A(x)B(x)=\sum _{{n=0}}^{\infty }c_{n}x^{n}.$ 

• Если $A(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_n\frac{x^n}{n!}$$A(x)=\sum _{{n=0}}^{\infty }a_{n}{\frac {x^{n}}{n!}}$  и $B(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{b}_n\frac{x^n}{n!}$$B(x)=\sum _{{n=0}}^{\infty }b_{n}{\frac {x^{n}}{n!}}$  — экспоненциальные производящие функции последовательностей $\{a_n\}$$\{a_{n}\}$  и $\{b_n\}$$\{b_{n}\}$ , то их произведение $A(x)\cdot <!--\; \cdot \; -->B(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_n\frac{x^n}{n!}$$A(x)\cdot B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!}}$  является экспоненциальной производящей функцией последовательности $c_n=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})a_k{b}_{n-<!--\; -\; -->k}$$c_{n}=\sum _{{k=0}}^{n}{n \choose k}a_{k}b_{{n-k}}$ .

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

В комбинаторикеПравить

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

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

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

$\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{B}_m^n{x}^n=(1+x+x^2+\cdots <!--\; \cdots \; -->{)}^m=(1-<!--\; -\; -->x{)}^{-<!--\; -\; -->m}.$$\sum _{{n=0}}^{\infty }B_{m}^{n}x^{n}=(1+x+x^{2}+\cdots )^{m}=(1-x)^{{-m}}.$ 

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

$B_m^n=(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{-<!--\; -\; -->m}{n})=\frac{m(m+1)\cdots <!--\; \cdots \; -->(m+n-<!--\; -\; -->1)}{n!}=(\genfrac{}{}{0ex}{}{m+n-<!--\; -\; -->1}{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$$a_n$  число всех графов с вершинами $\{1,\dots <!--\; \dots \; -->,n\}$$\{1,\dots,n\}$  и через $c_n$$c_n$  число всех связных графов с этими вершинами.

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

$1,2,8,64,1024,32768,2097152,\dots <!--\; \dots \; -->$$1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \dots$ 

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

$a(x)=a_1\cdot <!--\; \cdot \; -->x+\frac{1}{2}\cdot <!--\; \cdot \; -->a_2\cdot <!--\; \cdot \; -->x^2+\cdots <!--\; \cdots \; -->+\frac{1}{n!}\cdot <!--\; \cdot \; -->a_n\cdot <!--\; \cdot \; -->x^n+\dots <!--\; \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 <!--\; \cdot \; -->x+\frac{1}{2}\cdot <!--\; \cdot \; -->c_2\cdot <!--\; \cdot \; -->x^2+\cdots <!--\; \cdots \; -->+\frac{1}{n!}\cdot <!--\; \cdot \; -->c_n\cdot <!--\; \cdot \; -->x^n+\dots <!--\; \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\ne <!--\; \ne \; -->0$$x\neq 0$ , тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:

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

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

$1,1,4,38,728,26704,1866256,251548592,66296291072,\dots <!--\; \dots \; -->$$1,\ 1,\ 4,\ 38,\ 728,\ 26704,\ 1866256,\ 251548592,\ 66296291072,\ \dots$ 

В теории вероятностейПравить

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

$\mathbb{P}(X=j)=p_j,j=0,1,...;\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{p}_j=1$${\mathbb {P}}(X=j)=p_{j},\;j=0,1,...;\quad \sum \limits _{{j=0}}^{{\infty }}p_{j}=1$ 

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

$P(s)=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{p}_k{s}^k,$$P(s)=\sum _{{k=0}}^{\infty }\;p_{k}s^{k},$ 

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

$P^{\prime }(s)=\underset{k=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}k{p}_k{s}^{k-<!--\; -\; -->1}.$$P'(s)=\sum _{{k=1}}^{\infty }{kp_{k}s^{{k-1}}}.$ 

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

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

$q_k=\mathbb{P}(X>k)=\underset{j=k+1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{p}_j;Q(s)=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{q}_k{s}^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)$$P(s)$  свойством: $Q(s)=\frac{1-<!--\; -\; -->P(s)}{1-<!--\; -\; -->s}$$Q(s)={\frac {1-P(s)}{1-s}}$  при $|s|<1$ . Из этого по теореме о среднем следует, что математическое ожидание равно просто значению этой функции в единице:

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

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

$M[X(X-<!--\; -\; -->1)]=\sum <!--\; \sum \; -->k(k-<!--\; -\; -->1)p_k=P^{″}(1)=2Q^{\prime }(1)$$M[X(X-1)]=\sum {k(k-1)p_{k}}=P''(1)=2Q'(1)$ 

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

$D[X]=P^{″}(1)+P^{\prime }(1)-<!--\; -\; -->P^{\prime 2}(1)=2Q^{\prime }(1)+Q(1)-<!--\; -\; -->Q^2(1)$$D[X]=P''(1)+P'(1)-P'^{2}(1)=2Q'(1)+Q(1)-Q^{2}(1)$ .

В случае бесконечной дисперсии $\underset{s\to <!--\; \to \; -->1}{lim}{P}^{″}(s)=\mathrm{\infty <!--\; \infty \; -->}$$\lim _{{s\to 1}}P''(s)=\infty$ .

Вариации и обобщенияПравить

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

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

$\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n}{n^s}$$\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}$ .

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

  $\mathrm{\zeta <!--\; \zeta \; -->}(s)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{1}{n^s}.$$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}.$ 

• Если $\mathrm{\alpha <!--\; \alpha \; -->}(s)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n}{n^s}$$\alpha (s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}$  и $\mathrm{\beta <!--\; \beta \; -->}(s)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{b_n}{n^s}$$\beta (s)=\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}$  — производящие функции Дирихле последовательностей $\{a_n\}$$\{a_{n}\}$  и $\{b_n\}$$\{b_{n}\}$ , то их произведение $\mathrm{\alpha <!--\; \alpha \; -->}(s)\cdot <!--\; \cdot \; -->\mathrm{\beta <!--\; \beta \; -->}(s)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{c_n}{n^s}$$\alpha (s)\cdot \beta (s)=\sum _{n=0}^{\infty }{\frac {c_{n}}{n^{s}}}$  является производящей функцией Дирихле свёртки Дирихле — последовательности $c_n=\underset{d\mid <!--\; \mid \; -->n}{\sum <!--\; \sum \; -->}{a}_d{b}_{n/d}$$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.

СсылкиПравить

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