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

Материал из свободной русской энциклопедии «Традиция»
Перейти к навигации Перейти к поиску
Производящая функция
формальный степенной ряд вида G ( z ) = n = 0 a n z n G(z)=\sum\limits_{n=0}^\infty a_n z^n , порождающий (производящий) последовательность ( a 0 , a 1 , a 2 , ) (a_0, a_1, a_2, \ldots)
Введение:
Ввёл:
Леонард Эйлер
Когда введено:
1750-е
Отношения с другими понятиями:

Производящая функция (англ. generating function) — формальный степенной ряд вида G ( z ) = n = 0 a n z n G(z)=\sum\limits_{n=0}^\infty a_n z^n , порождающий (производящий) последовательность ( a 0 , a 1 , a 2 , ) (a_0, a_1, a_2, \ldots) .

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

Применение[править | править код]

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

  • Компактной записи информации о последовательности.
  • Нахождения зависимости a n ( n ) a_n(n) для последовательности a n a_n , заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
  • Нахождения рекуррентного соотношения для последовательности — вид производящей функции может помочь найти формулу.
  • Исследования асимптотического поведения последовательности.
  • Доказательства тождеств с последовательностями.
  • Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве пентагональной теоремы или в задаче нахождения количества расстановок m m ладей на доске n × n n \times n .
  • Вычисления бесконечных сумм.

Примеры производящих функций[править | править код]

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

  • n = 1 ( 1 x n ) \prod\limits_{ n = 1}^\infty(1-x^n) — производящая функция для разности количества разбиений числа n n в четное и нечетное число различных слагаемых. Например, коэффициент при x 5 x^5 равен + 1 +1 , потому что существует два разбиения на четное число различных слагаемых ( 4 + 1 ; 3 + 2 ) (4+1; 3+2) и одно на нечетное ( 5 5 ). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое — x k -x^k ) или не взять (первое — 1 1 ). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.
  • n = 1 1 1 x n \prod\limits_{n=1}^\infty \dfrac{1}{1-x^n} — производящая функция для последовательности p n p_n , где p i p_i — число разбиений числа i i на слагаемые.
  • n = 1 ( 1 + x n ) \prod\limits_{ n = 1}^\infty(1+x^n) — производящая функция для последовательности d n d_n , где d i d_i — число разбиений на различные слагаемые.
  • n = 1 ( 1 + x 2 n 1 ) 1 \prod\limits_{n=1}^\infty(1+x^{ 2n - 1})^{-1} — производящая функция для последовательности l n l_n , где l i l_i — число разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно d n = l n d_n = l_n : n = 1 ( 1 + x n ) = n = 1 1 x 2 n 1 x n = 1 x 2 1 x 1 x 4 1 x 2 1 x 6 1 x 3 = \prod\limits_{n=1}^\infty(1+x^{ n})=\prod\limits_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=


= 1 1 x 1 1 x 3 1 1 x 5 = n = 1 ( 1 + x 2 n 1 ) 1 =\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})^{-1}

Примеры решений задач методом производящих функций[править | править код]

=[править | править код]

Решение рекуррентных соотношений[править | править код]

Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, f n f_n — числа Фибоначчи или C n C_n числа Каталана. Метод производящих функций позволяет получить выражение для a n a_n через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что z z достаточно мало.

Пусть последовательность ( a 0 , a 1 , a 2 , ) (a_0, a_1, a_2, \ldots) удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для a n a_n (при n 0 n \geqslant 0 ) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел a n a_n , удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k k , то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n n , равно k k ):
    a 0 = , a_0=\ldots,
    a 1 = , a_1=\ldots,
    \ldots
    a k 1 = , a_{k-1}=\ldots,
    a n = , n k . a_{n}=\ldots, n \geqslant k.
  2. Домножить каждую строчку на z z в соответствующей степени и просуммировать строчки для всех n 0 n \geqslant 0 .
  3. В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
  4. Выразить G ( z ) G(z) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням z z .

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

a 0 = 1 , a_0= 1,

a 1 = 2 , a_1= 2,

a n = 6 a n 1 8 a n 2 + n , n 2 a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2

Запишем производящую функцию для этой последовательности и преобразуем правую часть:


G ( z ) = a 0 + a 1 z + n = 2 ( 6 a n 1 8 a n 2 + n ) z n G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n


G ( z ) = a 0 + a 1 z + 6 n = 2 a n 1 z n 8 n = 2 a n 2 z n + n = 2 n z n G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1} z^n - 8\sum\limits_{n=2}^\infty a_ { n-2} z^n+\sum\limits_{n=2}^\infty n z^n


G ( z ) = a 0 + a 1 z + 6 z n = 1 a n z n 8 z 2 n = 0 a n z n + n = 2 n z n G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n } z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n } z^n+\sum\limits_{n=2}^\infty n z^n


G ( z ) = a 0 + a 1 z + 6 z ( G ( z ) a 0 ) 8 z 2 G ( z ) + n = 2 n z n G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n


G ( z ) = 1 4 z + 6 z G ( z ) 8 z 2 G ( z ) + n = 2 n z n G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n


Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью n b n nb_n (в нашем случае последовательность b n = ( 1 , 1 , 1 , ) b_n= (1, 1, 1, \ldots) ). Такая последовательность получается путём дифференцирования функции B ( z ) B(z) , производящей для b n b_n , с последующим умножением результата на z z :


z B ( z ) = z ( n = 0 b n z n ) = z n = 1 n b n z n 1 = n = 0 n b n z n zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n


Тогда замкнем последнее слагаемое следующим образом:


n = 2 n z n = z n = 2 n z n 1 = z ( n = 2 z n ) \sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'


n = 2 z n = n = 0 z n 1 z = 1 1 z 1 z = z 2 1 z \sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}


z ( z 2 1 z ) = z 2 ( 2 z ) ( 1 z ) 2 z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}


Таким образом, наше последнее слагаемое примет вид:


G ( z ) = 1 4 z + 6 z G ( z ) 8 z 2 G ( z ) + z 2 ( 2 z ) ( 1 z ) 2 G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}


Это уравнение для производящей функции. Из него выражаем G ( z ) G(z) :


G ( z ) = 1 6 z + 11 z 2 5 z 3 ( 1 6 z + 8 z 2 ) ( 1 z ) 2 G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}


Разложим знаменатель на множители и разобьём дробь на сумму простых дробей [1]:

G ( z ) = 1 6 z + 11 z 2 5 z 3 ( 1 6 z + 8 z 2 ) ( 1 z ) 2 = 1 6 z + 11 z 2 5 z 3 ( 1 2 z ) ( 1 4 z ) ( 1 z ) 2 = 1 / 3 ( 1 z ) 2 + 7 / 9 1 z 1 / 2 1 2 z + 7 / 18 1 4 z G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты [2]:


1 ( 1 z ) 2 = ( 1 z ) 2 = n = 0 ( 2 n ) ( z ) n = n = 0 ( 1 ) n ( n + 1 1 ) ( z ) n = n = 0 ( n + 1 ) z n \dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n


G ( z ) = 1 / 3 ( 1 z ) 2 + 7 / 9 1 z 1 / 2 1 2 z + 7 / 18 1 4 z = 1 3 n = 0 ( n + 1 ) z n + 7 9 n = 0 z n 1 2 n = 0 2 n z n + 7 18 n = 0 4 n z n G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n


a n = n + 1 3 + 7 9 2 n 2 + 7 4 n 18 = 7 4 n + 6 n + 20 18 2 n 1 a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}

Расчет дисперсии геометрического распределения[править | править код]

Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятностей. Например, в геометрическом распределении [3] для нахождения дисперсии D ( ξ ) = E ( ξ 2 ) ( E ( ξ ) ) 2 \operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2 нужно найти два мат. ожидания:


  • E ( ξ ) = n = 1 n p ( 1 p ) n 1 \operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1}


  • E ( ξ 2 ) = n = 1 n 2 p ( 1 p ) n 1 \operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}


которые фактически являются производящими функциями последовательностей 1 , 2 , 3 1, 2, 3\ldots и 1 , 4 , 9 1, 4, 9\ldots :


  • E ( ξ ) = n = 1 n p ( 1 p ) n 1 = \operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} =

= n = 0 ( n + 1 ) p ( 1 p ) n = = \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} =

= n = 0 n p ( 1 p ) n + n = 1 p ( 1 p ) n 1 = = \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} =

= ( 1 p ) E ( ξ ) + 1 E ( ξ ) = 1 p = (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}


  • E ( ξ 2 ) = p n = 1 n 2 ( 1 p ) n 1 = \operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =

= p n = 1 n ( n + 1 ) ( 1 p ) n 1 p n = 1 n ( 1 p ) n 1 = =p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =

= p d 2 d p 2 n = 1 ( 1 p ) n + 1 + p d d p n = 1 ( 1 p ) n = = p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =

= p d 2 d p 2 ( n = 0 ( 1 p ) n ( 1 p ) 2 ) + p d d p ( n = 0 ( 1 p ) n ( 1 p ) ) = = p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =

= p d 2 d p 2 ( 1 1 ( 1 p ) ( 1 p ) 2 ) + p d d p ( 1 1 ( 1 p ) ( 1 p ) ) = = p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =

= p d 2 d p 2 ( ( 1 p ) 2 p ) + p d d p ( 1 p p ) = = p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =

= p 2 p 3 p 1 p 2 = 2 p 2 1 p = 2 p p 2 = p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}} .

Тогда:

D ( ξ ) = E ( ξ 2 ) ( E ( ξ ) ) 2 = 2 p p 2 1 p 2 = 1 p p 2 \operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}

Пример задачи на нахождение производящей функции[править | править код]

Шаблон:Задача Заметим, что для того, чтобы закончить путь в 0 0 , необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать n 2 \dfrac{n}{2} позиций для, например, шагов вправо из всего n n шагов. Тогда ответом будет сумма от нуля до бесконечности по n n всех C 2 n n C^{n}_{2n} . То есть: g ( x ) = 0 C 2 n n x n g(x) = \sum\limits_{0}^{\infty} C^{n}_{2n} x^n Рассмотрим f ( x ) = 0 C n x n f(x) = \sum\limits_{0}^{\infty} C_n x^n , где C n C_n число Каталана. Тогда, заметим что f ( x ) = 0 n C n x n 1 f'(x) = \sum\limits_{0}^{\infty} n C_n x^{n-1} . Так как C n = 1 n + 1 C 2 n n C_n = \dfrac{1}{n+1} C_{2n}^n , то справедливо равенство: g ( x ) = ( n + 1 ) f ( x ) = x f ( x ) + f ( x ) g(x) = (n+1)f(x) = xf'(x) + f(x)

Мы знаем, что производящая функция для чисел Каталана равна f ( x ) = 1 1 4 x 2 x f(x) = \dfrac{1-\sqrt{1-4x}}{2x} . Найдем f ( x ) f'(x) .

f ( x ) = 4 x 1 4 x 2 + 2 1 4 x 4 x 2 = 1 2 x 1 4 x 2 x 2 1 4 x f'(x) = \dfrac{\dfrac{4x}{\sqrt{1-4x}} - 2 + 2\sqrt{1-4x}}{4x^2} = \dfrac{1 - 2x - \sqrt{1-4x}}{2x^2 \sqrt{1-4x}}

Соответственно, ответом будет производящая функция вида:

g ( x ) = 1 2 x 1 4 x 2 x 1 4 x + 1 1 4 x 2 x = 1 1 4 x g(x) = \dfrac{1 - 2x - \sqrt{1-4x}}{2x \sqrt{1-4x}} + \dfrac{1-\sqrt{1-4x}}{2x} = \dfrac{1}{\sqrt{1 - 4x}}

Шаблон:Задача

Заметим, что задача аналогична Правильной скобочной последовательности. Тогда производящей функцией для нашей задачи будет производящая функция для правильной скобочной последовательности, а именно:

g ( x ) = 1 1 4 x 2 x g(x) = \dfrac{1-\sqrt{1-4x}}{2x}

Приложения[править | править код]

Примеры простых производящих функций[править | править код]

На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций [4].

Все суммы выполняются по переменной n n от 0 0 до \infty . Элементы последовательности нумеруются от 0 0 .

Последовательность Производящая функция в виде ряда Производящая функция в замкнутом виде
( 1 , 0 , 0 , ) (1, 0, 0,\ldots) 1 1 1 1
( 0 , 0 , , 0 , 1 , 0 , 0 ) (0, 0, \ldots, 0, 1, 0, 0\ldots) ( m m нулей в начале) z m z^m z m z^m
( 1 , 1 , 1 , ) (1, 1, 1,\ldots) z n \sum\limits z^n 1 1 z \dfrac{1}{1-z}
( 1 , 0 , 0 , , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 ) (1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots) (повторяется через m m ) z n m \sum\limits z^{nm} 1 1 z m \dfrac{1}{1-z^m}
( 1 , 1 , 1 , 1 , ) (1, -1, 1, -1,\ldots) ( 1 ) n z n \sum\limits (-1)^nz^n 1 1 + z \dfrac{1}{1+z}
( 1 , 2 , 3 , 4 , ) (1, 2, 3, 4,\ldots) ( n + 1 ) z n \sum\limits (n+1)z^n 1 ( 1 z ) 2 \dfrac{1}{(1-z)^2}
( 1 , 2 , 4 , 8 , 16 , ) (1, 2, 4, 8, 16,\ldots) 2 n z n \sum\limits 2^nz^n 1 ( 1 2 z ) \dfrac{1}{(1-2z)}
( 1 , r , r 2 , r 3 , ) (1, r, r^2, r^3,\ldots) r n z n \sum\limits r^nz^n 1 ( 1 r z ) \dfrac{1}{(1-rz)}
( ( ( m 0 ) , ( m 1 ) , ( m 2 ) , ( m 3 ) , {m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots ) ) ( m n ) \sum\limits {m\choose n} z n z^n ( 1 + z ) m (1+z)^m
( ( 1 , ( m m ) , ( m + 1 m ) , ( m + 2 m ) , 1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots ) ) ( m + n 1 n ) \sum\limits {{m+n-1}\choose n} z n z^n 1 ( 1 z ) m \dfrac{1}{(1-z)^m}
( ( 1 , ( m + 1 m ) , ( m + 2 m ) , ( m + 3 m ) , 1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots ) ) ( m + n n ) \sum\limits {{m+n}\choose n} z n z^n 1 ( 1 z ) m + 1 \dfrac{1}{(1-z)^{m+1}}
( 0 , 1 , 1 2 , 1 3 , 1 4 , ) (0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots) ( 1 ) n + 1 n \sum\limits \dfrac{(-1)^{n+1}}{n} z n z^n ln  Натуральный логарифм  ( 1 + z ) \ln(1+z)
( 1 , 1 , 1 2 , 1 6 , 1 24 , ) (1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots) 1 n ! \sum\limits \dfrac{1}{n!} z n z^n e z e^z
( 1 , 1 2 ! m 2 , 1 4 ! m 4 , 1 6 ! m 6 , 1 8 ! m 8 , ) (1, -\dfrac{1}{2!}m^2, \dfrac{1}{4!}m^4, -\dfrac{1}{6!}m^6, \dfrac{1}{8!}m^8,\ldots) 1 ( 2 n ) ! \sum\limits \dfrac{1}{(2n)!} m ( 2 n ) m^{(2n)} cos  Косинус  m \cos m
( m , 1 3 ! m 3 , 1 5 ! m 5 , 1 7 ! m 7 , 1 9 ! m 9 , ) (m, -\dfrac{1}{3!}m^3, \dfrac{1}{5!}m^5, -\dfrac{1}{7!}m^7, \dfrac{1}{9!}m^9,\ldots) 1 ( 2 n 1 ) ! \sum\limits \dfrac{1}{(2n-1)!} m ( 2 n 1 ) m^{(2n-1)} sin  Синус  m \sin m

См. также[править | править код]

Примечания[править | править код]

Источники информации[править | править код]

Примечания[править | править код]

АРыбников ARybnikov (обсуждение) 20:33, 23 декабря 2021 (UTC)