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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Примеры использования[править | править вики-текст]

В комбинаторике[править | править вики-текст]

Пусть 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}^\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} = \frac{m(m+1)\cdots(m+n-1)}{n!} = {m+n-1 \choose n}.

В теории вероятностей[править | править вики-текст]

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

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

P(s)=\sum_{k=0}^\infty\;p_k s^k,

как значение первой производной в единице: M[X] = P'(1) (стоит отметить, что ряд для P(s) сходится, по крайней мере, при |s|\le 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}.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]