5.7. Производящие функции

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

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

К такому вопросу сводится большое число комбинаторных задач, ответ во всех таких задачах определяется этим параметром n, так что можно считать, что решением является последовательность a0 ,a1 ,a3 ,..., an .

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

Производящей функцией последовательности {an}, n ≥ 0 на-

зывается формальный степенной ряд

F(z) = a0 + a1z + a2 Z 2 +... = an Z n .

Переход от последовательностей к их производящим функциям позволяет операции над последовательностями заменить операциями над их производящими функциями. Можно использовать то, что сумме двух последовательностей соответствует сумма их производящих функций, произведению последовательности на число - произведение ее производящей функции на это же число, и, что особенно замечательно, свертке двух последовательностей соответствует произведение производящих функций этих последовательностей.

Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an},