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

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

Мы предлагаем начинать знакомство с задач, в которых интересующая нас информация заключена в коэффициенте некоторого многочлена и для того, чтобы найти этот коэффициент, нужно проделать действия с другими многочленами (например, взять производную известного многочлена или перемножить два многочлена). Здесь можно рассмотреть задачу о числе счастливых билетов с четырехзначными номерами, задачи на доказательства свойств биномиальных коэффициентов (например, доказательство тождества Вандермонда). Далее можно ввести определение производящей функции, пояснить, что действия с ними - это фактически действия с многочленами (бесконечными). Но нас интересует не поведение этого «многочлена» в определенных точках, нас интересуют его коэффициенты. При этом для удобства работы важно найти компактную запись производящей функции, которую в любой момент снова можно разложить в ряд. Для иллюстрации можно найти производящую функцию последовательности из единиц с помощью рассуждений, аналогичных выводу суммы геометрической прогрессии. Взятие производной позволяет отыскать производящую функцию для последовательности натуральных чисел. Полезно ввести обобщенные биномиальные коэффициенты и с помощью их производящей функции решить, например, задачу о размене, задачу о числе счастливых билетов с шестизначными номерами.

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

И. Н. Арсентьева