7.2 ОСНОВНЫЕ МАНЕВРЫ

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

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

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

Сумма в (7.12) включает все но иногда удобнее распространить диапазон суммирования на все целые Мы можем сделать это, просто положив . В таких случаях можно по-прежнему говорить о последовательности как если бы не существовали для отрицательных

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

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

функция — просто формальный степенной ряд, в котором z стоит потому, что ведь что-то надо написать. В предыдущем разделе, например, мы использовали вторую точку зрения; несколько раз мы подставляли z в „сумму“ комбинаторных объектов вместо каких-либо качеств этих объектов. После этого коэффициент при отвечал числу комбинаторных объектов, имеющих это качество в количестве

Если мы рассматриваем как функцию комплексного переменного, то встает вопрос о сходимости ряда. Как мы определили в гл. 2, бесконечная сумма сходится (абсолютно) тогда и только тогда, когда существует константа , такая, что конечная сумма ни для каких не превосходит . Отсюда легко усмотреть, что если сумма сходится для некоторого значения то она сходится и для всех z при Кроме того, должно выполняться следовательно, в обозначениях гл. если имеется сходимость в точке Обратно, если то ряд сходится для всех Это — основные факты о сходимости степенных рядов.

Однако, как правило, сходимость не будет играть для нас существенной роли, если только мы не изучаем асимптотическое поведение коэффициентов. Почти всем операциям над производящими функциями, которые мы проделывали, можно дать строгое истолкование как операциям над формальными степенными рядами, и такие операции являются корректными, даже если ряд расходится. (Соответствующую теорию можно найти, например, в работах Белла [19], Найвена [228] и Хенричи [336, гл.

С другой стороны, даже если мы отбросим все предосторожности и выведем какую-либо формулу без строгого обоснования, то обычно оказывается возможным просто взять окончательную формулу и доказать ее по индукции. Например, производящая функция для чисел Фибоначчи сходится лишь при но нам совсем не нужно знать об этом при доказательстве формулы Однажды обнаружив эту формулу, мы можем доказать ее непосредственно, если не доверяем теории формальных степенных рядов. Таким образом, в этой главе мы будем пренебрегать вопросами сходимости; исследование сходимости было бы только помехой.

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

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

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

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

Когда мы в гл. 6 искали выражение в замкнутом виде для чисел Фибоначчи, то использовали (дважды) именно эту операцию, а также сложение, чтобы вывести уравнение

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

(Последнюю сумму нельзя распространить на все если только не окажется

Еще один из наших трюков — это умножение z на константу:

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

Часто оказывается нужным добавить к коэффициентам множитель Сделать это позволяет дифференцирование:

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

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

Обратная операция, интегрирование, дает способ поделить элементы последовательности на

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

И, наконец, продемонстрируем умножение производящих функций:

Как мы видели в гл. 5, полученная сумма есть производящая функция последовательности свертки Сумму можно записать и как поскольку при при Умножение/свертка немного сложнее других операций, однако очень полезна — настолько полезна, что мы посвятим весь разд. 7.5 разбору примеров ее использования.

Имеется ряд частных случаев умножения, которые заслуживают того, чтобы рассматривать их как отдельные операции. Один из таких случаев мы уже видели: если то получаем операцию сдвига (7.14). В этом случае сумма превращается в один член поскольку все коэффициенты равны 0, за исключением

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

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

В табл. 368 собраны все операции, которые мы рассмотрели. Для эффективного использования этих операций полезно иметь в запасе достаточно большой набор производящих функций. В табл. 369 перечислены простейшие из них; используя для начала их, мы уже сможем решить кое-какие задачи.

Таблица 368 Преобразования производящих функций. (см. скан)

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

Рассмотрим, например, последовательность производящая функция которой часто бывает нужна. Эта производящая функция находится примерно в середине табл. 369, но, кроме того, это — частный случай последовательности помещенной в таблице ниже; а также частный случай родственной последовательности можем вывести нужную формулу из производящей функции последовательности взяв ее частичные суммы как в (7.21); т. е. поделив на Или же можно вывести ее из дифференцированием, воспользовавшись (7.17).

(см. скан)

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

следовательно,

Аналогично можно извлечь члены с нечетными номерами:

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

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

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