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

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

Путь задана последовательность а₁, а₂, ... , а_n, ... (неважно, конечная или бесконечная). Производящей функцией последовательности а₁, а₂, ... , а_n, ... называется функция . При этом все рассматриваемые ряды в случае бесконечной последовательности считаются формально сходящимися (если эти ряды сходятся в какой-то области к функции f(x)), поскольку мы интересуемся не областью сходимости соответствующих рядов, а лишь соотношениями между коэффициентами таких рядов.

Например, из формулы

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

Возводя обе части последнего разложения в квадрат, получаем

,

откуда следует, что для последовательности 1, 2, 3, ... , n, ... производящей функцией является функция .

Нас будут интересовать производящие функции для последовательностей a₀, a₁, ... , a_n, ..., так или иначе связанных с комбинаторными задачами. С помощью производящих функций удается получать и исследовать самые разные свойства этих последовательностей.

Пусть - производящая функция последовательности b₁, b₂, ... , b_n, ... и - производящая функция последовательности c₁, c₂, ... , c_n, ... . Тогда из равенства

имеем

или в общем виде

.

В таком случае говорят, что последовательность коэффициентов c_n есть свертка (произведение Коши) последовательностей a_n и b_n.