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

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

Если дана последовательность $\{a_n\}$ чисел $a_0,a_1,a_2,a_3,\dots$, то из них можно построить формальный степенной ряд

$A(t)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{t}^n=a_0+a_{1}t+a_2{t}^2+a_3{t}^3+\cdots$,

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

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

$A(t)=\sum _{n=0}^{\mathrm{\infty }}\frac{a_n{t}^n}{n!}=a_0+a_{1}t+\frac{a_2}{2}{t}^2+\frac{a_3}{6}{t}^3+\cdots$,

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

Замечания

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

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

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

Свойства

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

• Произведение производящих функций $A(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ и $B(x)=\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}{c}_n{x}^n.$

• Если $A(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{x^n}{n!}$ и $B(x)=\sum _{n=0}^{\mathrm{\infty }}{b}_n\frac{x^n}{n!}$ — экспоненциальные производящие функции последовательностей $\{a_n\}$ и $\{b_n\}$, то их произведение $A(x)\cdot B(x)=\sum _{n=0}^{\mathrm{\infty }}{c}_n\frac{x^n}{n!}$ является экспоненциальной производящей функцией последовательности $c_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{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}^{\mathrm{\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(\genfrac{}{}{0ex}{}{-m}{n})=\frac{m(m+1)\cdots (m+n-1)}{n!}=(\genfrac{}{}{0ex}{}{m+n-1}{n}).$

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

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

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

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

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

$a(x)=a_1\cdot x+\frac{1}{2}\cdot a_2\cdot x^2+\dots +\frac{1}{n!}\cdot a_n\cdot x^n+\dots$

$c(x)=c_1\cdot x+\frac{1}{2}\cdot c_2\cdot x^2+\dots +\frac{1}{n!}\cdot c_n\cdot x^n+\dots$

Оба ряда расходятся при $x\ne 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,...;\sum _{j=0}^{\mathrm{\infty }}{p}_j=1$

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

$P(s)=\sum _{k=0}^{\mathrm{\infty }}{p}_k{s}^k,$

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

$P^{\prime }(s)=\sum _{k=1}^{\mathrm{\infty }}k{p}_k{s}^{k-1}.$

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

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

$q_k=\mathbb{P}(X>k)=\sum _{j=k+1}^{\mathrm{\infty }}{p}_j;Q(s)=\sum _{k=0}^{\mathrm{\infty }}{q}_k{s}^k.$

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

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

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

$M[X(X-1)]=\sum k(k-1)p_k=P^{″}(1)=2Q^{\prime }(1)$

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

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

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

В математическом анализе

• Производящая функция дзета-функции Римана от чётного неотрицательного аргумента равна:

$\sum _{n=0}^{\mathrm{\infty }}\zeta (2n)x^n=-\frac{\pi \sqrt{x}\cot (\pi \sqrt{x})}{2}$

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

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

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

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

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

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

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

История

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:КнигаШаблон:Недоступная ссылка
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

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