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

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

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

[math]\displaystyle{ A(t)=\sum_{n=0}^\infty a_n t^n=a_0+a_1t+a_2t^2+a_3t^3+\dotsb }[/math],

который называется производящей функцией [math]\displaystyle{ A(t) }[/math] этой последовательности.

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

[math]\displaystyle{ A(t)=\sum_{n=0}^\infty \frac{a_n t^n}{n!}=a_0+a_1t+\frac{a_2}{2}t^2+\frac{a_3}{6}t^3+\dotsb }[/math],

у которого коэффициент перед [math]\displaystyle{ a_n }[/math] поделён на факториал числа [math]\displaystyle{ n }[/math].

Замечания

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

[math]\displaystyle{ \sum_{n=0}^\infty (3^n)^n x^n }[/math] и [math]\displaystyle{ \sum_{n=0}^\infty (2^n)^n x^n }[/math]

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

Свойства

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

• Произведение производящих функций [math]\displaystyle{ A(x)=\sum_{n=0}^\infty a_n x^n }[/math] и [math]\displaystyle{ B(x)=\sum_{n=0}^\infty b_n x^n }[/math] последовательностей [math]\displaystyle{ \{a_n\} }[/math] и [math]\displaystyle{ \{b_n\} }[/math] является производящей функцией свёртки [math]\displaystyle{ c_n = \sum_{k=0}^n a_k b_{n-k} }[/math] этих последовательностей:

[math]\displaystyle{ A(x)B(x)=\sum_{n=0}^\infty c_n x^n. }[/math]

• Если [math]\displaystyle{ A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!} }[/math] и [math]\displaystyle{ B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!} }[/math] — экспоненциальные производящие функции последовательностей [math]\displaystyle{ \{a_n\} }[/math] и [math]\displaystyle{ \{b_n\} }[/math], то их произведение [math]\displaystyle{ A(x)\cdot B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!} }[/math] является экспоненциальной производящей функцией последовательности [math]\displaystyle{ c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k} }[/math].

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

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

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

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

При фиксированном m производящей функцией последовательности [math]\displaystyle{ B_m^0, B_m^1, \dots }[/math] является:

[math]\displaystyle{ \sum_{n=0}^\infty B_m^n x^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}. }[/math]

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

[math]\displaystyle{ B_m^n = (-1)^n {-m\choose n} = \frac{m(m+1)\cdots(m+n-1)}{n!} = {m+n-1 \choose n}. }[/math]

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

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

Заметим, что [math]\displaystyle{ a_n=2^{\binom n 2} }[/math]. В частности легко посчитать первые члены этой последовательности

[math]\displaystyle{ 1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \dots }[/math]

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

[math]\displaystyle{ a(x)=a_1\cdot x+\tfrac12\cdot a_2\cdot x^2+\dots+\tfrac1{n!}\cdot a_n\cdot x^n+\dots }[/math]

[math]\displaystyle{ c(x)=c_1\cdot x+\tfrac12\cdot c_2\cdot x^2+\dots+\tfrac1{n!}\cdot c_n\cdot x^n+\dots }[/math]

Оба ряда расходятся при [math]\displaystyle{ x\ne 0 }[/math], тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:

[math]\displaystyle{ 1+a(x)=e^{c(x)}, }[/math]

из которого следует простое рекуррентное соотношение для [math]\displaystyle{ c_n }[/math], позволяющее быстро найти первые члены этой последовательности

[math]\displaystyle{ 1,\ 1,\ 4,\ 38,\ 728,\ 26704,\ 1866256,\ 251548592,\ 66296291072,\ \dots }[/math]

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

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

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

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

[math]\displaystyle{ P(s)=\sum_{k=0}^\infty\;p_k s^k, }[/math]

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

[math]\displaystyle{ P'(s)=\sum_{k=1}^\infty{k p_k s^{k-1}}. }[/math]

При подстановке [math]\displaystyle{ s=1 }[/math] получим величину [math]\displaystyle{ P'(1)=\sum_{k=1}^\infty{k p_k} }[/math], которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то [math]\displaystyle{ \lim_{s\to 1}P'(s)=\infty }[/math] — а [math]\displaystyle{ X }[/math] имеет бесконечное математическое ожидание, [math]\displaystyle{ P'(1)=M[X]=\infty }[/math]

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

[math]\displaystyle{ q_k=\mathbb{P}(X\gt k)=\sum_{j=k+1}^\infty{p_j};\quad Q(s)=\sum_{k=0}^\infty\;q_k s^k. }[/math]

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

[math]\displaystyle{ M[X]=P'(1)=Q(1) }[/math]

• Дифференцируя [math]\displaystyle{ P'(s)=\sum_{k=1}^\infty{k p_k s^{k-1}} }[/math] и используя соотношение [math]\displaystyle{ P'(s)=Q(s)-(1-s)Q'(s) }[/math], получим:

[math]\displaystyle{ M[X(X-1)]=\sum{k(k-1)p_k}=P''(1)=2Q'(1) }[/math]

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

[math]\displaystyle{ D[X]=P''(1)+P'(1)-P'^2(1)=2Q'(1)+Q(1)-Q^2(1) }[/math].

В случае бесконечной дисперсии [math]\displaystyle{ \lim_{s\to 1}P''(s)=\infty }[/math].

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

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

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

[math]\displaystyle{ \sum_{n=1}^\infty \frac{a_n}{n^s} }[/math].

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

  [math]\displaystyle{ \zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}. }[/math]

• Если [math]\displaystyle{ \alpha(s)=\sum_{n=1}^\infty \frac{a_n}{n^s} }[/math] и [math]\displaystyle{ \beta(s)=\sum_{n=1}^\infty \frac{b_n}{n^s} }[/math] — производящие функции Дирихле последовательностей [math]\displaystyle{ \{a_n\} }[/math] и [math]\displaystyle{ \{b_n\} }[/math], то их произведение [math]\displaystyle{ \alpha(s)\cdot \beta(s)=\sum_{n=0}^\infty \frac{c_n}{n^s} }[/math] является производящей функцией Дирихле свёртки Дирихле — последовательности [math]\displaystyle{ c_n = \sum_{d\mid n} a_d b_{n/d} }[/math].

История

Метод производящих функций был разработан Эйлером в 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.

Ссылки

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