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

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

Что это?

Одними из наиболее красивых инструментов для решения комбинаторных задач являются производящие функции (generating functions). Грубо говоря, производящая функция — это бесконечный ряд

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

коэффициенты которого порождают (производят, генерируют) последовательность чисел a0, a1, a2, … Тот факт, что коэффициент an является множителем при zn обозначают следующим образом:

Коэффициент при z в степени n

Замечательная особенность производящих функций заключается в том, что они часто могут быть записаны в компактном виде. Например, если a0=a1=…=1, то

1/(1-z)

Другой пример: если an=n, то

z/(1-z)^2

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

Рассмотрим абстрактный пример. Пусть в некоторой задаче удалось отыскать закономерность

То есть обнаружилась последовательность 1, 7, 19, 43, 91, 187,…, удовлетворяющая рекуррентному соотношению. Требуется вывести общую формулу для an, n≥0. В этом случае говорят «решить рекуррентное уравнение» или «решить рекуррентное соотношение».

Сначала будем искать производящую функцию в виде

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

Домножим левую и правую части рекуррентного соотношения на z в соответствующей степени:

Сложим все уравнения для всех значений n:

Слева в точности получается значение G(z), а справа — некоторое выражение, которое нужно свернуть (любым законным способом). Сначала рассмотрим первую сумму

Первое равенство получается, если изменить индекс суммирования (уменьшить на 1) и вынести 2 за знак суммы. Второе равенство получается путём вынесения z за знак суммы. Третье очевидно. Вторая сумма сворачивается почти аналогично:

Вторая сумма

Последнее равенство есть хорошо знакомая геометрическая прогрессия. Подробнее о функции 1/(1-z) можно узнать здесь.

Окончательно, подставив упрощённые выражения в полученное выше уравнение (*), имеем

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

Это называется уравнение для производящей функции. Разрешив его относительно G(z), получим

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

Производящую функцию нужно разложить в ряд по степеням z: (подробно о том, как разложить рациональную функцию в ряд написано здесь):

Разложение в ряд

Это означает, что

Ответ

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

Зачем это?

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

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

Обсуждение статьи на форуме в этой теме.