7.3 РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

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

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

1 Запишите одно уравнение, выражающее через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых с учетом того, что

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

3 Решите полученное уравнение, получив для выражение в замкнутом виде.

4 Разложите в степенной ряд и прочитайте коэффициент при это и будет замкнутый вид для

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

Пример 1: снова числа Фибоначчи

Попробуем в качестве примера повторить вывод формулы для чисел Фибоначчи из гл. 6. Там мы нащупывали путь, изучая новый метод; теперь будем действовать более систематически. Вот перед нами заданное рекуррентное соотношение:

Найдем выражение для в замкнутом виде, выполнив приведенные выше четыре шага.

Шаг 1 требует записать рекуррентное соотношение в виде „одного уравнения" для Мы могли бы записать

но это самообман. В действительности на шаге 1 нужна формула, не содержащая конструкций с перечислением случаев. Одно

уравнение

имеет место для и, кроме того, оно справедливо при (поскольку ). Однако для имеем 1 в левой части и 0 — в правой. К счастью, это затруднение легко преодолеть, достаточно просто прибавить к правой части; это увеличивает правую часть на 1 при и не изменяет ее при Итак, мы имеем

это как раз то уравнение, которое требуется на шаге 1.

Теперь шаг 2 предлагает преобразовать уравнение для в уравнение для Это несложная задача:

Шаг 3 в нашем случае тоже прост; имеем

что, конечно, неудивительно.

Вся загвоздка в шаге 4. В гл. 6 выполнить этот шаг помогло внезапное озарение; теперь же будем двигаться медленнее, с тем чтобы позднее без затруднений справиться с этим шагом в более сложных задачах. Чему же равен

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

где — многочлены, определить коэффициент

Имеется один вид рациональных функций с особенно хорошими коэффициентами, а именно,

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

тоже неплохие:

Мы покажем, что любая рациональная функция такая, что может быть выражена в виде

где имеет вид (7.26), а — многочлен. Таким образом, для коэффициентов имеется выражение в замкнутом виде. Нахождение эквивалентно нахождению „разложения в элементарные дроби“ функции

Заметьте, что для значений равных Следовательно, числа которые нам надо найти, если мы хотим представить в виде должны представлять собой обратные величины к числам для которых (Напомним, что где Р и многочлены; поэтому только если

Допустим, что имеет вид

„Обращенный многочлен

имеет важную взаимосвязь с

Таким образом, корни обратны к корням и наоборот. Следовательно, для нахождения нужных нам чисел достаточно разложить обращенный многочлен на множители.

Например, в случае последовательности Фибоначчи имеем

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

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

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

Теорема о разложении рациональных функций в случае различных корней

Если , где и числа различны, — многочлен степени меньше I,

Доказательство: Пусть — константы с указанными выше значениями. Формула (7.29) будет справедлива, если равняется

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

Пусть Нам нужно доказать, что а для этого достаточно установить, что поскольку — рациональная функция Таким образом, мы хотим показать, что

Предел в правой части равен поскольку для Предел в левой части равен

по правилу Лопиталя. Таким образом, теорема доказана.

Вернемся к примеру с числами Фибоначчи. Здесь следовательно и

Значит, в соответствии с (7.29), коэффициент, с которым входит в равняется коэффициент при равен Таким образом, теорема утверждает, что как в (6.123).

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

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

Если где и числа различны, — многочлен степени меньше, чем , то

где все являются многочленами степени со старшим коэффициентом

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

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

Пример 2: довольно произвольное рекуррентное соотношение

Сейчас, познакомившись с более общими методами, мы готовы взяться за новые задачи. Попробуем решить в замкнутом виде рекуррентное соотношение

Всегда неплохо составить таблицу нескольких начальных значений, и рекуррентное соотношение позволяет легко сделать это:

Простой формулы не просматривается, и, более того, эта последовательность отсутствует в справочнике по целочисленным последовательностям Слоана [276]; так что нам никуда не деться от четырехшагового процесса, если только мы действительно хотим найти решение.

Шаг 1 прост; здесь требуется просто состряпать какие-то поправочные члены, чтобы учесть случаи Уравнение

выполняется для всех целых . Теперь можно выполнить шаг 2:

(В данном случае мы могли бы записать вместо что дает по биномиальной теореме.) Шаг 3 требует лишь элементарной алгебры и дает

Теперь нам остался только шаг 4.

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

с некоторой константой с, причем

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

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

Не составит большого труда проверить случаи и 2, просто для того чтобы быть уверенными, что мы нигде не ошиблись. Может быть стоит попробовать и поскольку формула выглядит несколько странно. Но она правильна: все так и должно быть.

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

Пример 3: взаимно рекуррентные последовательности

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

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

Здесь — число покрытий -прямоугольника без угла с использованием костяшек домино. Эти соотношения легко вывести, если рассмотреть возможные расположения домино на левой стороне прямоугольника, как мы делали раньше. Здесь выписаны значения для малых

Найдем, в четыре шага, выражения в замкнутом виде. Сначала (шаг 1) запишем

при любых Следовательно (шаг 2),

Теперь (шаг 3) нам требуется решить два уравнения с двумя неизвестными; это легко сделать, получив из второго уравнения далее находим

(Мы уже видели эту формулу для в (7.10), но там вместо стояло . В тот раз было числом костяшек, а здесь — ширина прямоугольника.)

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

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

Многочлен разлагается на множители их можно также записать в виде поскольку этот многочлен обратен сам себе. Таким образом, получаем

Это и есть искомое выражение для числа -покрытий.

В данном случае мы можем упростить формулу для если заметим, что второе слагаемое всегда лежит между 0 и 1. Число — целое, поэтому

На самом деле, второе слагаемое исчезающе мало при больших поскольку Это следует иметь в виду при использовании формулы (7.38) для расчетов. Например, довольно дорогой карманный калькулятор, выпускаемый фирмой с хорошей репутацией, при вычислении дал в ответе 413403.0005. Этот ответ точен до девятой значащей цифры; однако точное значение чуть меньше 413403, а не чуть больше. Следовательно, было бы ошибкой вычислять потолок от 413403.0005; точный ответ, получается округлением до ближайшего целого. Потолок может быть опасен.

Пример 4: замкнутое выражение для задачи размена

Мы оставили задачу размена, только лишь подсчитав число способов выплаты 50 центов. А как вычислить то же число для суммы в 1 доллар или в миллион долларов — размен производится по-прежнему пенни, никелями, даймами, четвертями и полу-долларами?

Ранее мы вывели производящую функцию

это рациональная функция от знаменатель которой имеет степень 91. Таким образом, мы можем разложить знаменатель на 91 множитель и выразить — число способов дать центов сдачи — в „замкнутом виде“, состоящем из 91 слагаемого. Но такое ужасное выражение не лезет ни в какие ворота. Нельзя ли в этом частном случае найти что-либо лучшее, а не применять общий метод?

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

Степень знаменателя этой „сжатой (функции уже только 19, так что эта функция гораздо лучше исходной. Новое выражение для показывает, в частности, что и действительно, это соотношение легко объяснить: чаевые в 53 цента можно дать ровно столькими же способами, как и чаевые в 50 центов, поскольку количество пенни по модулю 5 заранее известно.

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

Вот, для полноты картины, развернутое выражение для

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

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

Используя это выражение, можем узнать, например, значение Здесь и мы имеем

Число способов заплатить 50 центов составляет для суммы в 1 доллар будет способа; а для миллиона долларов это число составит

Пример 5: расходящийся ряд

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

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

Уравнение

справедливо для всех оно дает

Для завершения шага 2 надо выразить через таблица основных маневров (табл. 368) подсказывает, что здесь надо как-то использовать Поэтому подгоним наше выражение к сумме требуемого вида:

Проверим это уравнение, подставив значения для малых Таким образом,

поэтому

Сложив эти три строки, получим так что пока все в порядке. Кстати, часто будет удобнее писать вместо дополнительное просто загромождает формулу, если мы не меняем z на что-нибудь еще.

Теперь предстоит сделать шаг 3, и он отличается от того, что мы делали раньше, поскольку здесь требуется решить дифференциальное уравнение. Однако с этим дифференциальным уравнением мы можем справиться при помощи гипергеометрических рядов из разд. 5.6; так что наши методы не так уж плохи. (Если

вы не знакомы с гипергеометрическими функциями, не беспокойтесь — мы все сделаем очень быстро.)

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

По развитой в гл. 5 теории следует переписать это с использованием оператора , а из упр. 6.13 мы знаем, что

Следовательно, дифференциальное уравнение запишется так:

В соответствии с (5.109), решением при будет гипергеометрический ряд

Шаг 3 оказался сложнее, чем мы ожидали; но теперь, когда мы знаем функцию шаг 4 очень прост — определение гипергеометрического ряда (5.76) дает требуемое разложение:

Мы подтвердили выражение, которое знали все время,

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

Пример 6: рекуррентное соотношение с возвратом к самому началу

В завершение этого раздела рассмотрим применение производящих функций к задаче из теории графов. порядка — это граф с вершинами ребрами, определяемыми следующим образом: вершина 0 соединяется ребрами с каждой из остальных вершин, а вершина к соединяется с вершиной к для Ниже, для примера, нарисован порядка 4, имеющий 5 вершин и 7 ребер.

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

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

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

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

Рассмотрим несколько начальных случаев. Можно легко перечислить все остовные деревья при и 3:

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

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

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

Общее уравнение, справедливое для имеет вид

(Выглядит все так, как будто Т в конце есть и нам следовало бы взять но мы будем тверды в своем выборе.) Небольшое изменение — и уравнение будет справедливо при всех целых

Это рекуррентное соотношение как раз и содержит „возврат к самому началу“ от через все предыдущие значения, и в этом отличие от других рекуррентных соотношений, которые мы видели в этой главе. Чтобы избавиться от аналогичной суммы в правой части рекуррентного соотношения (2.12) для анализа метода быстрой сортировки, мы использовали в гл. 2 специальный метод, а именно вычли один экземпляр соотношения из другого Здесь этот прием тоже годится; но, как мы увидим, метод производящих функций позволяет непосредственно работать с такими суммами. (И это очень хорошо, поскольку вскоре нам встретятся гораздо более сложные рекуррентные соотношения.)

Шаг 1 завершен; теперь, на шаге 2, нам придется применить новый прием:

Ключевой трюк здесь — замена на это позволяет выразить двойную сумму через как того требует шаг 2.

Шаг 3 теперь сводится к простой алгебре и получаем

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