Производящая функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры производящих функций)
Строка 4: Строка 4:
 
'''Производя́щая фу́нкция (generating function)''' — это формальный степенной ряд:
 
'''Производя́щая фу́нкция (generating function)''' — это формальный степенной ряд:
 
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
 
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...)</tex>.
+
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...)</tex>.  
 
}}
 
}}
 
== Применение ==
 
== Применение ==
 
Производящая функция используется для:
 
Производящая функция используется для:
  
 +
* Компактной записи информации о последовательности;
 
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;
 
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;
 
* Исследования асимптотического поведения последовательности;
 
* Исследования асимптотического поведения последовательности;

Версия 02:20, 12 декабря 2011

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

Определение:
Производя́щая фу́нкция (generating function) — это формальный степенной ряд:

[math]G(z)=\sum_{n=0}^\infty a_n z^n[/math],

порождающий (производящий) последовательность [math](a_0, a_1, a_2, ...)[/math].

Применение

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

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

Примеры производящих функций

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

  • [math]\prod_{n=1}^\infty (1-x^n)[/math] — производящая функция для разности количества разбиений числа n в четное и нечетное число различных слагаемых. Например коэффициент при [math]x^5[/math] — +1, потому-что существует два разбиение на четное число различных слагаемых (4+1; 3+2) и одно на нечетное (5). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое — [math]-x^k[/math]) или не взять (первое — 1). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.
  • [math]\prod_{n=1}^\infty frac{1}{1-x^n}[/math] — производящая функция для последовательности [math]p_n[/math], где [math]p_i[/math] — количество разбиений числа i на слагаемые.

Решение рекуррентных соотношений

Пусть последовательность [math](a_0, a_1, a_2, ...)[/math] удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для [math]a_n[/math] (при [math]n \ge 0[/math]) в замкнутом виде (то есть выразив лишь через номер члена последовательности). Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

[math]a_0=1,[/math]

[math]a_1=2,[/math]

[math]a_n=6a_{n-1}-8a_{n-2}+n, n \ge 2[/math]

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


[math]G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n[/math]


[math]G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_{n-1}z^n - 8\sum_{n=2}^\infty a_{n-2}z^n+\sum_{n=2}^\infty n z^n[/math]


[math]G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_{n}z^n - 8z^2\sum_{n=0}^\infty a_{n}z^n+\sum_{n=2}^\infty n z^n[/math]


[math]G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n[/math]


[math]G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n[/math]


Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью [math]nb_n[/math](у нас последовательность [math]b_n[/math]-константная единица). Такая последовательность получается путём дифференцирования функции B(z) с последующим умножением результата на z:


[math]zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{n=1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n[/math]


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


[math]\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z (\sum_{n=2}^\infty z^n)'[/math]


[math]\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}[/math]


[math]z (\frac{z^2}{1-z})'=\frac{z^2(2-z)}{(1-z)^2}[/math]


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


[math]G(z)=1-4z+6zG(z) - 8z^2G(z)+\frac{z^2(2-z)}{(1-z)^2}[/math]


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


[math]G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}[/math]

Теперь формализуем алгоритм, который мы использовали:

1)Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k):

2)Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n≥0. 3)В полученном уравнении привести все суммы ∑ к замкнутому виду. Получить уравнение для производящей функции. 4)Выразить G(z) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням z.

Ссылки

Литература