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

• Разделы:
  • Примеры использования
  • Вариации и обобщения
  • Литература
  • Ссылки

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

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

∑n=0∞anxn{displaystyle sum _{n=0}^{infty }a_{n}x^{n}}.

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

∑n=0∞(3n)nxn{displaystyle sum _{n=0}^{infty }(3^{n})^{n}x^{n}} и ∑n=0∞(2n)nxn{displaystyle sum _{n=0}^{infty }(2^{n})^{n}x^{n}}

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

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

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

Содержание

• 1 Свойства
• 2 Примеры использования
  • 2.1 В комбинаторике
  • 2.2 В теории вероятностей
• 3 Вариации и обобщения
  • 3.1 Экспоненциальная производящая функция
• 4 Литература
• 5 Ссылки

Свойства

• Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.
• Произведение производящих функций A(x)=∑n=0∞anxn{displaystyle A(x)=sum _{n=0}^{infty }a_{n}x^{n}}  и B(x)=∑n=0∞bnxn{displaystyle B(x)=sum _{n=0}^{infty }b_{n}x^{n}}  последовательностей {an}{displaystyle {a_{n}}}  и {bn}{displaystyle {b_{n}}}  является производящей функцией свёртки cn=∑k=0nakbn−k{displaystyle c_{n}=sum _{k=0}^{n}a_{k}b_{n-k}}  этих последовательностей:

A(x)B(x)=∑n=0∞cnxn.{displaystyle A(x)B(x)=sum _{n=0}^{infty }c_{n}x^{n}.} 

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

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

Пусть Bmn{displaystyle B_{m}^{n}}

  — это количество композиций неотрицательного целого числа n длины m, то есть, представлений n в виде n=k1+k2+⋯+km{displaystyle n=k_{1}+k_{2}+cdots +k_{m}} , где {ki}{displaystyle {k_{i}}}  — неотрицательные целые числа. Число Bmn{displaystyle B_{m}^{n}}  также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества {1,2,…,m}{displaystyle {1,2,dots ,m}}  (при этом каждый член ki{displaystyle k_{i}}  в композиции можно трактовать как количество элементов i в выборке).

При фиксированном m производящей функцией последовательности Bm0,Bm1,…{displaystyle B_{m}^{0},B_{m}^{1},dots }

  является:

∑n=0∞Bmnxn=(1+x+x2+⋯)m=(1−x)−m.{displaystyle sum _{n=0}^{infty }B_{m}^{n}x^{n}=(1+x+x^{2}+cdots )^{m}=(1-x)^{-m}.} 

Поэтому число Bmn{displaystyle B_{m}^{n}}

  может быть найдено как коэффициент при xn{displaystyle x^{n}}  в разложении (1−x)−m{displaystyle (1-x)^{-m}}  по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:

Bmn=(−1)n(−mn)=m(m+1)⋯(m+n−1)n!=(m+n−1n).{displaystyle B_{m}^{n}=(-1)^{n}{-m choose n}={frac {m(m+1)cdots (m+n-1)}{n!}}={m+n-1 choose n}.} 

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

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

P(X=j)=pj,j=0,1,…;∑j=0∞pj=1{displaystyle mathbb {P} (X=j)=p_{j},;j=0,1,…;quad sum limits _{j=0}^{infty }p_{j}=1} 

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

P(s)=∑k=0∞pksk,{displaystyle P(s)=sum _{k=0}^{infty };p_{k}s^{k},} 

как значение первой производной в единице: M[X]=P′(1){displaystyle M[X]=P'(1)}

  (стоит отметить, что ряд для P(s) сходится, по крайней мере, при |s|≤1{displaystyle |s|leq 1} ). Действительно,

P′(s)=∑k=1∞kpksk−1.{displaystyle P'(s)=sum _{k=1}^{infty }{kp_{k}s^{k-1}}.} 

При подстановке s=1{displaystyle s=1}

  получим величину P′(1)=∑k=1∞kpk{displaystyle P'(1)=sum _{k=1}^{infty }{kp_{k}}} , которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то lims→1P′(s)=∞{displaystyle lim _{sto 1}P'(s)=infty }  — а X{displaystyle X}  имеет бесконечное математическое ожидание, P′(1)=M[X]=∞{displaystyle P'(1)=M[X]=infty } 

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

qk=P(X>j)=∑j=k+1∞pj;Q(s)=∑k=0∞qksk.{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}.} 

Эта производящая функция связана с определённой ранее функцией P(s){display
style P(s)}

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

M[X]=P′(1)=Q(1){displaystyle M[X]=P'(1)=Q(1)} 

• Диференцируя P′(s)=∑k=1∞kpksk−1{displaystyle P'(s)=sum _{k=1}^{infty }{kp_{k}s^{k-1}}}  и используя соотношение P′(s)=Q(s)−(1−s)Q′(s){displaystyle P'(s)=Q(s)-(1-s)Q'(s)} , получим:

M[X(X−1)]=∑k(k−1)pk=P″(1)=2Q′(1){displaystyle M[X(X-1)]=sum {k(k-1)p_{k}}=P»(1)=2Q'(1)} 

Чтобы получить дисперсию D[X]{displaystyle D[X]}

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

D[X]=P″(1)+P′(1)−P′2(1)=2Q′(1)+Q(1)−Q2(1){displaystyle D[X]=P»(1)+P'(1)-P’^{2}(1)=2Q'(1)+Q(1)-Q^{2}(1)} .

В случае бесконечной дисперсии lims→1P″(s)=∞{displaystyle lim _{sto 1}P»(s)=infty }

 .

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

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

Экспоненциальная производящая функция последовательности {an}{displaystyle {a_{n}}}

  — это формальный степенной ряд

• ∑n=0∞anxnn!{displaystyle sum _{n=0}^{infty }a_{n}{frac {x^{n}}{n!}}} .

  • Если A(x)=∑n=0∞anxnn!{displaystyle A(x)=sum _{n=0}^{infty }a_{n}{frac {x^{n}}{n!}}}  и B(x)=∑n=0∞bnxnn!{displaystyle B(x)=sum _{n=0}^{infty }b_{n}{frac {x^{n}}{n!}}}  — экспоненциальные производящие функции последовательностей {an}{displaystyle {a_{n}}}  и {bn}{displaystyle {b_{n}}} , то их произведение A(x)B(x)=∑n=0∞cnxnn!{displaystyle A(x)B(x)=sum _{n=0}^{infty }c_{n}{frac {x^{n}}{n!}}}  является экспоненциальной производящей функцией последовательности cn=∑k=0n(nk)akbn−k{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.

Ссылки

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