Что такое производящие функции?

Сколькими способами можно выполнить некоторое действие в ситуации, которая зависит от некоторого целого неотрицательного параметра n (им может быть, например, число каких-то объектов) ?

К такому вопросу сводится большое число комбинаторных задач, ответ во всех таких задачах определяется этим параметром n, так что можно считать, что решением является последовательность a₀, a₁, a₂, ..., a_n, ...

Решение комбинаторной задачи часто начинают с нахождения рекуррентного соотношения, которое выражает общий член этой последовательности через предыдущие. Рекурентное соотношение, если задано несколько первых членов последовательности (сколько - зависит от задачи), полностью определяет последовательность. Интересно понять, какая формула говорит о зависимости общего члена a_n нашей последовательности от n. Мощным методом решения вопросов подобного рода является метод производящих функций.

Производящей функцией последовательности {a_n}, n>=0 называется формальный степенной ряд
F(z) = a₀ + a₁z + a₂z² + ... = \(\sum_{n=0}^i\)a_nzⁿ

Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями.
Можно использовать то, что сумме двух последовательностей соответствует сумма их производящих функций, произведению последовательности на число - произведение ее производящей функции на это же число, и, что особенно замечательно, свертке двух последовательностей соответствует произведение производящих функций этих последовательностей. Напомним, что сверткой двух последовательностей {a_n} и {b_n} называется последовательность {c_n}, общий член которой равен: c_n = a₀b_n + a₁b_n-1 + ... + a_kb_n-k + ... + a_nb₀.

Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {a_n}, переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {a_n} от n.

« назад в меню