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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
* Решение задачи подсчета объектов в комбинаторике. Например в доказательстве [[Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера|пентагональной теоремы]] или в задаче нахождения количества расстановок m ладей на доске n × n.
 
* Решение задачи подсчета объектов в комбинаторике. Например в доказательстве [[Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера|пентагональной теоремы]] или в задаче нахождения количества расстановок m ладей на доске n × n.
 
* Вычисление бесконечных сумм.
 
* Вычисление бесконечных сумм.
 +
== Решение рекуррентных соотношений ==
 +
Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \ge 0</tex>) в замкнутом виде (то есть выразив лишь через номер члена последовательности).
 +
Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:
 +
 +
<tex>a_0=1,</tex>
 +
 +
<tex>a_1=2,</tex>
 +
 +
<tex>a_n=6a_{n-1}-8a_{n-2}+n, n \ge 2</tex>
 +
 +
Запишем производящую функцию для этой последовательности и преобразуем правую часть:
 +
 +
<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n</tex>
 +
 +
<tex>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</tex>
 +
 +
<tex>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</tex>
 +
 +
<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)z^n+\sum_{n=2}^\infty n z^n</tex>
 +
 +
<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)z^n+\sum_{n=2}^\infty n z^n</tex>
 +
 +
Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex>(у нас последовательность <tex>b_n</tex>-константная единица). Такая последовательность получается путём дифференцирования функции B(z) с последующим умножением результата на z:
 +
 +
<tex>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</tex>
 +
 +
Тогда замкнем последнее слагаемое следующим образом:
 +
 +
<tex>\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z  \frac{d}{dz} \sum_{n=2}^\infty z^n</tex>
 +
 +
<tex>\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}</tex>
 +
 +
<tex>z  \frac{d}{dz} \frac{z^2}{1-z}=\frac{z^2(2-z}{(1-z)^2}</tex>
 
== Ссылки ==  
 
== Ссылки ==  
  

Версия 23:26, 11 декабря 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](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)z^n+\sum_{n=2}^\infty n z^n[/math]

[math]G(z)=1-4z+6zG(z) - 8z^2G(z)z^n+\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 \frac{d}{dz} \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{d}{dz} \frac{z^2}{1-z}=\frac{z^2(2-z}{(1-z)^2}[/math]

Ссылки

Литература