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

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

Определение:

Производя́щая фу́нкция (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.
• Вычисление бесконечных сумм.