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

Производящей функцией f( х) произвольной бесконечной

последовательности

называется выражение

Ландо С.К. Лекции о производящих функциях. - М.: МЦНМО, 2007. Wilf H.S.Generatingfunctionology. - Асасіетіс Ргевв, 1994.

при этом переменная х является формальной и сама сумма ряда смысла не имеет.

Такое утверждение весьма неожиданно (может поставить в тупик - что же это за функция, переменная, которой не имеет смысла). Ряд может расходиться и единственное, что определено - это значение в точке х = 0 , т. е. f(0) = ао.

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

Производящая функция превращает дискретный набор - последовательность ак (к = 0, 1, ...) в непрерывную функцию, что позволяет "включить" математический аппарат, работающий с непрерывными объектами - анализ непрерывных функций (решение уравнений, дифференцирования, интегририрования и т. д.), после чего можно опять вернуться в "дискретный" мир.

Постановка задачи о рекуррентных соотношениях выглядит так: пусть есть соотношение

необходимо найти явную зависимость

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

Рассмотрим несколько примеров.

Первый пример, тривиальный, для простой демонстрации метода. Пусть дано итерационное соотношение

и необходимо найти зависимость

Вводим производящую функцию:

умножаем ее на х и проводим ряд элементарных преобразований:

Первое слагаемое в скобках это С(х), второе

и, учитывая, что

находим:

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

Разлагая полученное выражение С(х) в ряд Тейлора находим:

Поскольку

для

получим:

и, таким образом, искомая зависимость найдена.

Конечно, в рассмотренном простом примере, из рекуррентного соотношения ак+1 = ак +1 можно сразу догадаться, что при а1 = 1 речь идет о последовательности 1, 2, 3, т. е., что ак = к.

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

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

Процесс описывается итерационным соотношением

где

число новорожденных пар в п -й месяц.

Вводим производящую функцию:

Умножим итерационное соотношение на X и просуммируем:

заметим, что суммирование возможно начинать только с п = 1, т. к. при п = 0 в каждой сумме справа появляется неопределенное слагаемое ¥_1.

Для левой части выражения (3.6.12) имеем:

где было учтено, что ¥1 =1 .

Для суммы

легко получить:

И, наконец, для последней суммы имеем:

Таким образом, итерационное соотношение может быть записано как:

что дает следующее выражение для производящей функции:

Раскладывая Є (х) на простые дроби, находим:

где

золотое сечение.

Таким образом, для Є( х) находим:

что для искомого ¥п дает:

Последний пример относится к исследованию детерминированных БР-сетей, а именно (и, у) -цветам. Ранее было без вывода указано, что из итерационного соотношения

следует:

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

методом

Проделывая очевидные преобразования

для С( х) получаем следующее выражение:

Поскольку

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

каждая из которых может быть, в свою очередь, записана в виде суммы:

подставляя которые в выражение для С(х) (свободные "х" появляющиеся на месте второго и четвертого слагаемого сокращаются) находим:

откуда и следует выражение для Ып .

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

очень просто убедится, что оно удовлетворяет итерационному соотношению

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

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

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

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

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