Метод производящих функций

Рассмотрим произведение конечного числа линейных биномов . В правой части равенства коэффициенты имеют вид .

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

Идея метода производящих функций такова: необходимо вычислить все члены некоторой последовательности . С помощью рекуррентного соотношения для из некоторых комбинаторных соображений вычисляют производящую функцию . Раскладывая затем в ряд и находя коэффициенты при t^k, тем самым находят .

Пример 1. Из формулы бинома Ньютона , последовательность биноминальных коэффициентов имеет производящую функцию (1)

Пример 2. Пусть , к=0;1;2;… Тогда , это бесконечно убывающая геометрическая прогрессия со знаменателем . В этом случае производящая функция имеет вид при . (2)

- класс обычных производящих функций

Операции в классе производящих функций:

1. Суммой последовательностей называется последовательность , а суммой производящих функций и - производящая функция . (3)

2. Произведением (сверткой) последовательностей называется последовательность , у которой (4)

а произведением производящих функций и - производящая функция . (5)

Нуль в классе производящих функций - это ; ей соответствует нулевая последовательность {0;0;…;0;…}. Единица в классе производящих функций - это ; ей соответствует единичная последовательность {1;0;0;…;0;…}=e. Обратный относительно сложения (противоположный) элемент в классе производящих функций есть следующая функция: , которой соответствует последовательность {-a₀;-a₁;…;-a_k;…}. Обратный элемент относительно умножения в классе производящих функций есть функция , причем . Т.к. ,