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

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

(1)

где – формальная переменная. При этом будем писать .

Пусть, например, . Тогда

.

Аналогично

.

Экспоненциальной производящей функцией последовательности называется ряд

(2)

Для обычных производящих функций вводится алгебра формальных степенных рядов, или алгебра Коши, с операциями сложения, умножения, суперпозиции, подстановки, дифференцирования и интегрирования. Алгебра степенных рядов , определяющих экспоненциальные производящие функции, известна как символическое исчисление Блиссара. Далее под производящей функцией будем понимать обычную производящую функцию .

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