7.5 СВЕРТКИ

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

Пример 1: фибоначчиевы свертки

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

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

Вместо того чтобы записывать ответ через попробуем найти замкнутое выражение через числа Фибоначчи. Вспоминая, что получим

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

и мы получаем желаемый ответ

Например, для формула дает левой части и — в правой.

Пример 2: гармонические свертки

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

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

Следовательно, по (7.43),

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

Приравнивая коэффициенты при получаем общее тождество

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

Частные случаи, например, столь же замечательны, как и общее тождество.

Но это еще не все. Мы можем, воспользовавшись тождеством для свертки

перенести в другую часть, поскольку не зависит от к:

Но и это не все! Если — неотрицательные целые I и то можно заменить на на затем, заменив к на получим

Даже частный случай этого тождества вызвал затруднения в гл. 2! (См. (2.36).) Мы прошли немалый путь.

Пример 3: свертки сверток

Если мы образуем свертку последовательностей а затем свернем результат с какой-то третьей последовательностью то член полученной последовательности будет равен

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

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

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

мы могли бы соединить вершины

Сколько же можно получить остовных деревьев, добавляя ребра в вершину 0? Нам нужно соединить вершину 0 с каждым из четырех блоков; существует два способа соединения 0 с один способ соединения с четыре способа — с (4,5,6,7) и три способа — с (8,9,10), что дает в итоге способа. Суммирование по всем способам разбиения на блоки дает следующее выражение для общего числа остовных деревьев:

Например, Это — сумма -кратных сверток последовательности для следовательно, производящей функцией для будет

где - производящая функция последовательности а именно Таким образом, имеем

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

Пример 4: рекуррентное соотношение со сверткой

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

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

так, чтобы порядок умножений был полностью определен? Например, для существует два способа: Для имеется уже пять способов:

Таким образом, имеем также

Попробуем применить четырехшаговую процедуру из разд. 7.3. Какому же рекуррентному соотношению удовлетворяет последовательность Ключевым моментом здесь является то наблюдение, что для ровно одна операция лежит вне всех скобок; это последнее умножение, связывающее все в единое целое. Если эта операция располагается между то имеется способов расстановки скобок в произведении способов —в следовательно,

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

Шаг 1 завершен. Шаг 2 предписывает умножить на и просуммировать:

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

Шаг 3 тоже прост. Функцию мы находим по формуле корней квадратного уравнения:

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

может нам поэтому выбрать Однако мы быстро обнаружим, что в этом случае будет равно что противоречит фактам. (Для истинной функции должно быть Итак, мы приходим к выводу, что

Наконец, шаг 4. Чему равен коэффициент Биномиальная теорема говорит, что

следовательно, используя (5.37), получаем

Число способов расстановки скобок равно

В гл. 5 мы предвосхитили этот результат, введя последовательность чисел Каталано. Эта последовательность встречается в десятках задач, которые, на первый взгляд, не связаны друг с другом [37], поскольку во многих ситуациях рекурсивная природа задачи отвечает рекуррентному соотношению со сверткой (7.66).

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

а все их частичные суммы

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

Это „горные хребты" ширины которые можно изобразить при помощи отрезков двух видов: Оказывается, что имеется ровно вариантов; при этом каждую из полученных последовательностей можно соотнести с некоторой расстановкой скобок: добавьте к формуле внешнюю пару скобок, так чтобы получилось пар скобок, соответствующих умножениям. Затем замените каждый знак на и каждую на все остальное удалите. Например, по этому правилу формуле соответствует последовательность . Пять способов расстановки скобок в выражении соответствуют пяти показанным выше горным хребтам для

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

при этом все частичные суммы

должны быть положительны. Очевидно, что это есть в точности последовательности из предыдущей задачи, к которым спереди приписали элемент Однако последовательности в новой задаче можно просто сосчитать, если воспользоваться замечательным фактом, открытым Джорджем Рени [265] в Если — любая последовательность целых чисел, сумма которых равна то ровно у одного из ее циклических сдвигов

частичные суммы все положительные. Рассмотрим, например, последовательность (3, —5,2, —2,3,0). Ее циклическими сдвигами являются

и только отмеченная последовательность имеет сплошь положительные частичные суммы.

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

таким образом, мы полагаем для всех к 0. Если теперь нарисовать график частичных сумм как функции от то этот график будет иметь „средний наклон"

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

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

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

Пример 5: рекуррентное соотношение с -кратной сверткой

Задачу, которой мы только что занимались, можно обобщить, рассмотрев последовательности из чисел частичные суммы которых все положительны, а общая сумма равна Такие последовательности можно назвать -последовательностями Рени. Если в последовательности элемент встречается к раз, а встречается

раз, то

и, следовательно, Всего имеется последовательностей с вхождениями — и вхождениями и лемма Рени говорит нам, что количество таких последовательностей со сплошь положительными частичными суммами составляет ровно

Это и есть число -последовательностей Рени. Назовем его числом Фусса—Каталана поскольку последовательность была впервые исследована (за много лет до того, как сам Каталан вступил в игру). Обычные числа

Каталана суть

Теперь, зная ответ (7.67), попробуем сформулировать вопрос, ведущий к этому ответу. В случае вопрос был такой: числа удовлетворяют рекуррентному соотношению Мы попробуем найти аналогичный вопрос (аналогичное соотношение) в общем случае.

Тривиальная последовательность длины 1, очевидно, является -последовательностью Рени. Если поместить число справа от любых последовательностей, каждая из которых является -последовательностью Рени, то мы получим снова -последовательность Рени; частичные суммы остаются положительными — сначала они возрастают до а окончательная сумма равна . И обратно, можно показать, что все -последовательности Рени при получаются этим способом: последний член должен быть равен Частичные суммы положительны для поскольку Пусть означает наибольший индекс такой, что пусть — наибольший индекс, такой, что и т.д. Таким образом, для Отсюда следует, что и мы можем легко проверить, что каждая из подпоследовательностей является -последовательностью Рени. При этом должно выполняться для некоторых неотрицательных целых

Следовательно, является ответом на следующие два интересных вопроса: равны числа С, определяемые рекуррентным соотношением

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

то какие коэффициенты он имеет?“

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

Сейчас, однако, мы знаем уже достаточно для того, чтобы поставить еще более сложные вопросы и получить ответы на них. Вот такой, например, вопрос: равен коэффициент где I — положительное целое, — степенной ряд, определяемый (7.69)?“ Рассуждая подобно тому, как мы делали ранее, получим, что есть число последовательностей длины со следующими тремя свойствами:

• Каждый элемент равен либо либо .

• Все частичные суммы положительны.

Общая сумма равна I.

Действительно, все такие последовательности мы можем единственным образом получить, приписав друг за другом I последовательностей, имеющих свойство -последовательности Рени. Число способов выполнить это равно

Доказанное Рени обобщение его леммы говорит нам, как подсчитать эти последовательности: если — любая последовательность целых чисел, такая, что для любых то ровно I из циклических сдвигов

имеют сплошь положительные частичные суммы.

Например, можно проверить это утверждение на последовательности . Ее циклические сдвиги суть

и только две последовательности, помеченные имеют все положительные частичные суммы. Эта обобщенная лемма доказывается в упр. 13.

Последовательность из элементов длины с общей суммой I должна содержать ровно элементов Обобщенная лемма говорит нам, что из этих последовательностей имеют только положительные частичные суммы; следовательно, наш трудный вопрос имеет удивительно простой ответ:

для любых целых

Читатели, не забывшие гл. 5, вполне могут подумать что-нибудь вроде: „Эта формула выглядит знакомой, не встречалась ли она раньше?“ Да, действительно, встречалась; вот что записано в уравнении (5.60):

Следовательно, производящая функция из (7.69) должна совпадать с обобщенным биномиальным рядом . И действительно, из уравнения (5.59) имеем

а это эквивалентно

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

обладает следующим замечательным свойством:

если только — положительные целые.

Можно ли распространить эти результаты на произвольные значения ? Да, можно, поскольку коэффициенты

являются многочленами от Общая степень, определяемая как

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

В гл. 5 упоминается также обобщенный экспоненциальный ряд

относительно которого формула (5.60) утверждает не менее замечательное свойство:

Мы можем доказать это как предельный случай формулы для поскольку, как нетрудно показать,