/
Автор: Ландо С.К.
Теги: комбинаторный анализ теория графов теория вероятностей математическая статистика математика комбинаторика
ISBN: 5-94057-042-9
Год: 2004
Текст
Современные
ЛЕКЦИОННЫЕ КУРСЫ
С. К. ЛАНДО
Лекции
о производящих
функциях
мцнмо
Москва
2004
УДК 519.1
ББК 22.176
Л 22
Лаядо С. К.
Л 22 Лекции о производящих функциях. — 2-е изд., испр. — М.:
МЦНМО, 2004. — 144 с.
ISBN 5-94057-042-9
Настоящая книга посвящена производящим функциям — языку, на кото-
котором говорит современная перечислительная комбинаторика. Этот язык ис-
используется и во многих других областях математики и математической фи-
зики. Книга предназначена, в первую очередь, для студентов младших кур-
курсов физико-математических специальностей. В ней разобрано много приме-
примеров и содержится большое количество задач для самостоятельного решения.
ББК 22.176
Учебное издание
Ландо Сергей Константинович
Лекции о производящих функциях
Технический редактор И. В. Вялая
Иллюстрации М. Н. Вялый
Издательство Московского Центра
непрерывного математического образования
Лицензия ИД № 01335 от 24.03.2000 г.
Подписано в печать 10.12.2003 г. Формат 60 х 90/16. Усл. печ. л. 9.
Бумага офсетная W» 1. Печать офсетная. Тираж 1000. Заказ №4818.
МЦНМО
121002, Москва, Большой Власьевский пер., д. 11.
Отпечатано с готовых диапозитивов
в ФГУП «Производственно-издательский комбинат ВИНИТИ».
140010, г.Люберцы Московской обл.,
Октябрьский пр-т, д. 403. Тел. 554 21 86.
© Ландо С. К., 2002, 2004
ISBN 5-94057-042-9 © МЦНМО, 2002, 2004
Оглавление
Предисловие 7
Глава 1. Формальные степенные ряды и производящие функции.
Действия над формальными степенными рядами. Эле-
Элементарные производящие функции 9
1.1. Задача о числе счастливых билетов 9
1.2. Выводы 14
1.3. Производящие функции и действия над ними 14
1.4. Элементарные производящие функции 18
1.5. Дифференцирование и интегрирование производящих
функций 19
1.6. Алгебра и топология формальных степенных рядов .. 20
1.7. Задачи 21
Глава 2. Производящие функции для известных последователь-
последовательностей 23
2.1. Геометрическая прогрессия 23
2.2. Последовательность Фибоначчи 24
2.3. Рекуррентные соотношения и рациональные произво-
производящие функции 26
2.4. Произведение Адамара рациональных производящих
функций 29
2.5. Числа Каталана 31
2.6. Задачи 36
Глава 3. Формальные грамматики с однозначным выводом. Тео-
Теорема Лагранжа 40
3.1. Язык Дика 40
3.2. Правила вывода в языке Дика 41
3.3. Формальные грамматики с однозначным выводом ... 43
3.4. Уравнение Лагранжа и теорема Лагранжа 46
3.5. Задачи 47
Глава 4. Аналитические свойства функций, представляемых сте-
степенными рядами, ¦ асимптотика их коэффициентов 49
4.1. Степенные оценки для асимптотики 49
4.2. Асимптотика гипергеометрических последовательно-
последовательностей 51
4 Оглавление
4.3. Асимптотика коэффициентов функций, связанных
между собой уравнением Лагранжа 55
4.4. Асимптотика коэффициентов производящего ряда и
характер особенности на границе круга сходимости . 57
4.5. Задачи 58
Глава 5. Производящие функции нескольких переменных 60
5-1. Треугольник Паскаля 60
5.2. Экспоненциальные производящие функции 62
5-3. Треугольник Дика 63
5.4. Треугольник Бернулли - Эйлера и перечисление змеи . 64
5.5. Представления производящих функций в виде непре-
непрерывных дробей 72
5.6. Числа Эйлера в треугольнике с кратностями 78
5-7. Сравнения в последовательностях 79
5.8. Решение обыкновенных дифференциальных уравнений
на производящие функции 82
5.9. Задачи 83
Глава 6. Разбиения и разложения 87
6.1. Разбиения и разложения 87
6.2. Тождество Эйлера 91
6.3. Разбиения множеств и непрерывные дроби 94
6.4. Задачи 97
Глава 7. Производящие функции Дирихле и формулы включе-
включения-исключения 100
7.1. Принцип включения-исключения 100
7.2. Производящие функции Дирихле и действия над ними 102
7.3. Обращение Мёбиуса 105
7.4. Мультипликативные последовательности 107
7.5. Задачи 108
Глава 8. Перечисление вложенных графов 111
8.1. Перечисление помеченных деревьев 111
8.2. Производящие функции для непомеченных, помечен-
помеченных, упорядоченных и циклически упорядоченных
объектов 117
8.3. Перечисление плоских и бинарных деревьев 117
8.4. Вложение графа в поверхность 120
Оглавление 5
8.5. О числе «"клеек многоугольника 129
8.6. Доказательство теоремы Харера-Загира 133
8.7. Задачи 137
Заключительные замечания и указания к библиографии 139
Список литературы 140
Предметный указатель 142
А. А. Кириллову,
от которого я впервые услышал слова
«производящая функция»
Предисловие
После умножения на Bп — 1)! коэффициент при х2п 1 разложения
функции tga: по степеням х становится положительным целым числом.
Что более удивительно, это число оказывается равным числу пило-
пилообразных перестановок на множестве {1, ..., 2п — 1}. Функция tga; тем
самым является «экспоненциальной производящей функцией» для по-
последовательности, образованной числами пилообразных перестановок.
Этот факт можно доказать, однако нельзя сказать, чтобы мы вполне
понимали природу стоящего за ним явления. Функция tga: не одино-
одинока — коэффициенты разложения в ряд многих «классических» функ-
функций имеют комбинаторную интерпретацию. Сюда относятся тригоно-
тригонометрические, гипергеометрические, эллиптические функции, эллипти-
эллиптические интегралы и т. п. Можно даже утверждать, что если функция
представляет интерес «сама по себе», а не как элемент некоторой сово-
совокупности функций, то ее коэффициенты имеют комбинаторный смысл.
Математики XVIII-XIX веков знали функции «в лицо». Вряд ли чи-
число специалистов, владеющих этим искусством сейчас, намного превы-
превышает их число столетие назад. А ведь корни производящей функции, ее
асимптотическое поведение, круг сходимости, тип особенностей, топо-
топология соответствующей римановой поверхности могут многое сказать
о характере описываемых ею объектов.
Производящие функции естественным образом разбиваются на
классы. Простейший из них — класс рациональных функций — хо-
хорошо изучен, и известны многочисленные примеры задач, приводящих
к рациональным производящим функциям. Алгебраические произво-
производящие функции также встречаются очень часто. В начале 60-х годов
Шютценберже показал, что их некоммутативные аналоги естественно
возникают в языках, порождаемых формальными грамматиками с од-
однозначным вьгеодом. Однако класс алгебраических функций (в отличие
от рациональных) незамкнут относительно естественной операции —
произведения Адамара. Произведение Адамара двух алгебраических
функций может оказаться алгебро-логарифмической функцией. Класс
алгебро-логарифмических функций уже выглядит очень естественным.
Связь алгебраических функций с формальными грамматиками ука-
указывает на существенную одномерность перечисляемых объектов — сло-
слова в языках записываются линейно. Объекты, перечисление которых
оказывается необходимым в современных моделях квантовой теории
поля, носят существенно двумерный характер. Природа возникающих
8 Предисловии
здесь производящих Функций не понята до сих пор. Придуманный фи-
физиками изящный метод представления таких функций в виде матрич-
матричных интегралов позволяет получить окончательные результаты лишь
в отдельных слу^1аях-
Мне хотелось/ написать простую и доступную книгу, уделив вни-
внимание в первую рчередь ярким примерам, а не общим теориям (кото-
(которые, к тому же, зачастую отсутствуют). В результате за ее бортом
оказались многий важные приложения метода производящих функций,
среди которых теория перечисления Полна и g-аналоги, производящие
многочлены Пуа#1каРе топологических многообразий и производящие
семейства, теорий разветвленных накрытий и многое другое.
Мой интерес * комбинаторике обязан своему происхождению ряду
задач, которые 6bulvl поставлены В. И. Арнольдом в связи с некоторы-
некоторыми проблемами т?°Рии особенностей, а также его собственным работам
в этой области. Значительное влияние на меня оказали работы француз-
французской комбинаторной школы, в первую очередь Лаборатории по иссле-
исследованиям в облас/ти информатики Университета г. Бордо (Ж. Вьенно,
Р. Кори, М. Деле?т' а также Ф. Флажоле). Предлагаемая вниманию чи-
читателей книга н^писан& на основе специального курса, читавшегося
студентам Независимого Московского университета в 1992-99 гг. Боль-
Большую помощь в пЯовеДении занятий оказал мне М. Н. Вялый, который
также подготовь материалы этих лекций к предварительному изда-
изданию. Для настоя1**его издания книга существенно переработана. Основ-
Основным источником моих знаний по комбинаторике послужил мой друг
и соавтор А. К. Зронкин> чье искусство создания текстов остается для
меня недостижи\*ым> Увы, образцом.
С. К. Ландо
Глава 1
Формальные степенные ряды
и производящие функции.
Действия
над формальными степенными рядами.
Элементарные производящие функции
1.1. Задача о числе счастливых билетов
Начнем с задачи, которой А. А. Кириллов открывал свой семинар
в начале 70-х годов. В те времена человек, едущий в общественном
транспорте, должен был купить билет в автоматической кассе или у
кондуктора. Билеты были перенумерованы шестизначными номерами.
Билет называется счастливым, если сумма первых трех цифр его
номера равняется сумме последних трех цифр.
Так, билеты с номерами 000000 и 123060 — счастливые, а билет
с номером 123456 — несчастливый. Счастливый билет полагалось на
счастье съесть.
Итак, сколько всего существует счастливых билетов9.
Человеку, владеющему элементарными навыками программирова-
программирования, нетрудно написать программу для подсчета числа счастливых би-
билетов. Простейшая такая программа перебирает все номера от 000000
до 999999, отбирая среди них счастливые. Давайте, однако, приглядим-
приглядимся к задаче повнимательнее.
Разобьем все счастливые билеты на классы, в каждом из которых
сумма первых трех цифр одинакова. Эта сумма может принимать зна-
значения от 0 (для тройки цифр 000) до 27 (для тройки 999). Поэтому чи-
число классов равно 28. Обозначим через а„ число различных троек цифр
с суммой цифр п. Первые несколько значений ап нетрудно вычислить:
> ао = 1 (есть всего одна тройка цифр 000 с суммой 0);
> ai = 3 (есть три тройки 001, 010, 001 с суммой цифр 1);
> а2 = 6 (тройки 002, 020, 200, 011, 101, ПО).
Легко видеть, что число счастливых билетов, сумма первых трех
цифр которых равна п, есть с?п. Действительно, как в начале, так и в
конце номера счастливого билета можно поставить любую тройку цифр
с суммой п. Таким образом, для подсчета числа счастливых билетов нам
10 Глава 1. Элементарные производящие функции
достаточно вычислить числа ап, а затем найти сумму квадратов этих
28 чисел.
Для вычисления значений ап попробуем подсчитать сначала число
одно- и двузначных чисел с суммой цифр п. Для каждого п — 0,1,
2, ..., 9 существует ровно одно однозначное число с суммой цифр п
(запись этого числа совпадает с записью числа п). Будем описывать
однозначные числа многочленом
Ai{s) = l + s + s2 + ... + s°.
Смысл у этого многочлена следующий:
коэффициент при sn в многочлене А\ равен числу однозначных чи-
чисел, сумма цифр которых равна п.
Другими словами, коэффициент при s" в многочлене А\ равен 1,
если 0 ^ п ^ 9, и равен 0, если п > 9.
Выпишем теперь многочлен A-2(s), описывающий двузначные числа.
Коэффициент при sn в многочлене A-^s) равен числу двузначных чи-
чисел с суммой цифр п. (Мы рассматриваем и такие двузначные числа,
в которых первая цифра или даже обе цифры .могут равняться нулю.)
Нетрудно видеть, что степень многочлена A-z равна 18. Действи-
Действительно, 18 — наибольшая возможная сумма цифр двузначного числа.
Несложно сосчитать и первые несколько коэффициентов этого много-
многочлена:
A2{s) = l+2s + 3s2 +4s3 + ...
Оказывается, многочлен At легко строится по многочлену А\.
Предложение 1.1. ^(s) — {A\{s)J.
Доказательство. Произведение мономов sk и sm дает вклад в ко-
коэффициент при мономе sn многочлена (Ai(s)J в том и только в том
случае, если п = к + т. Поэтому коэффициент при мономе sn в мно-
многочлене (Ai(s)J есть в точности число способов представить число п
в виде суммы п = к + т, к, т — 0, 1, ..., 9. Таким образом, много-
многочлен в правой части равенства совпадает с многочленом А^-
Теперь нетрудно выписать и многочлен Аз{з) — ao + ais + .. .+аг7«27-
Предложение 1.2. A3(s) = (Ai(s)K.
Доказательство. Доказательство практически дословно совпада-
совпадает с доказательством предыдущего утверждения: коэффициент при .s"
1.1. Счастливые билеты 11
в многочлене (Л^)K равен числу представлений числа п в виде суммы
трех цифр, п = т + к + I, т, к, I = 0, 1, ..., 9.
Итак, задача о числе счастливых билетов практически решена: оста-
осталось вычислить многочлен (Ai(s)K и подсчитать сумму квадратов его
коэффициентов. Обратите внимание на то, что умножение на много-
многочлен Ai(s) — очень простая операция. Вычисления можно провести
вручную, затратив на них около десяти минут. Надобность в написа-
написании программы отпадает.
Однако можно не останавливаться на достигнутом и пойти даль-
дальше 1'. Излагаемый ниже подход к решению задачи о счастливых биле-
билетах, принадлежит — тогда десятикласснику — В. Дринфельду.
Рассмотрим наряду с многочленом Аз(з) «многочлен Лорана»
A3(l/s) от переменной s:
«27
Произведение Аз(в)Аз (-) также является многочленом Лорана (т.е.
оно содержит мономы вида sk, где к может быть как положительным,
так и отрицательным, но при этом его значения ограничены сверху
и снизу). Свободный член (коэффициент при s°) в этом произведении
имеет вид Од + а\ + ... + а?27, и мы заключаем, что
число счастливых билетов равно свободному члену многочлена Ло-
Лорана A3(s)A3(l/s).
Для вычисления этого свободного члена мы можем теперь восполь-
воспользоваться базисным фактом теории функций комплексного переменно-
переменного -— теоремой Коши.
Теорема 1.3 (Коши). Для любого многочлена Лорана p(s) его сво-
свободный член ро равен
' p(s)ds
Ро
2т J
s
где интеграл берется по любой окружности на комплексной прямой,
ориентированной против часовой стрелки и содержащей внутри себя
начало координат.
Другими словами, интеграл от skds по такой окружности равен 2тгг
при к = —1, и он равен 0 при всех остальных целых значениях к. Этот
факт легко проверить.
')Последующий текст (до конца раздела) требует владения элементами матема-
математического анализа и может быть пропущен без ущерба для понимания дальнейшего.
12 Глава 1. Элементарные производящие функции
Для наших целей наиболее удобной оказывается окружность еди-
единичного радиуса с центром в начале координат. Воспользовавшись тем,
что
1 — s °
Ai(s) = l + s + ...+sg = - ,
1 — s
представим требуемый многочлен Лорана в виде
Вводя на единичной окружности стандартный параметр <р и огра-
ограничивая на нее многочлен Лорана P(s), получаем выражение для его
свободного члена:
м \ I ^г — I 1 I
О _Е
Попробуем оценить значение последнего интеграла. График функ-
,, . sinA0v?) Г тг 7г1
ции f{(p) = —: на отрезке —, - выглядит так, как показано
на рис. 1.1. В нуле функция достигает своего максимума, равного 10.
Вне отрезка ——, — величина функции / не превосходит -—=- » 3.
Slnio
Поэтому вклад дополнения к отрезку ~тр>) трг в интеграл A.1) не пре-
превосходит 7г • З6 « 2100 (на самом деле он значительно меньше).
Основная же составляющая интеграла A.1) сосредоточена на отрез-
отрезке — тт, тт7 • Для оценки вклада этого отрезка воспользуемся методом
стационарной фазы. Этот метод позволяет оценить значение интеграла
10
1
ж
10
7Г
1С
-/
ж
~10
1.1. Счастливые билеты
13
Рис. 1.1. Вид графика функции fUfi) = —г
siny>
при t -» оо. При больших значениях t величина интеграла определяется
поведением функции In/ («фазы») в окрестности своей стационарной
точки 0 (точки, в которой (In/)' = 0, или, что то же самое, /' = 0).
(оо ч ОО
1 —^"V2)> а In/Cy) ~
При больших t имеем
ОО
я
10
/ <т
dv? = e"nl°
10
я
10
10
„tin 10
^/ЗЗi'
Полагая ( = 6и вспоминая формулу A.1), получаем приближенное
равенство
Ро
10°
и 56700.
Полученный результат с хорошей точностью (отклонение составляет
не более 3%) приближает искомое значение.
Еще один подсчет числа счастливых билетов, основанный на совер-
совершенно других принципах, приведен в разделе 7.1.
14 Глава 1. Элементарные производящие функции
1.2. Выводы
На основании рассмотренного примера можно сделать некоторые
выводы о задачах, которыми мы будем заниматься, и методах, кото-
которыми мы при этом будем пользоваться.
Предметом нашего исследования будут задачи перечислительной
комбинаторики. Они заключаются в подсчете числа объектов, при-
принадлежащих некоторому семейству конечных множеств. У каждого
множества семейства имеется свой номер (в задаче о числе счаст-
счастливых билетов таким номером была сумма цифр трехзначного чи-
числа).
Как правило, задача перечислительной комбинаторики «в принци-
принципе» разрешима: для каждого множества из семейства можно выписать
все его элементы и таким образом узнать их число. Проблема, однако,
состоит в том, чтобы найти «хорошее» решение, не требующее выпи-
выписывания всех элементов изучаемых множеств.
Определить, что такое хорошее решение, довольно трудно. Зача-
Зачастую можно лишь сравнить два решения и сказать, какое из них луч-
лучше.
При решении задач перечислительной комбинаторики очень полез-
полезно рассматривать производящие многочлены (или, более общо, про-
производящие ряды). В нашем случае пользу принес производящий мно-
многочлен A3. Операции с комбинаторными объектами очень естест-
естественно выражаются в терминах производящих функций. Так, пере-
переход от однозначных чисел с заданной суммой цифр к трехзначным
числам состоял просто в возведении производящего многочлена А\
в куб.
Привлечение методов из смежных областей математики (например,
из анализа) дает новый взгляд на перечислитечьные задачи и позволяет
находить неожиданные подходы к их решению.
1.3. Производящие функции и действия над ними
Перейдем к строгим определениям.
Определение 1.4. Пусть а0, ai, аг, ... — произвольная (бесконеч-
(бесконечная) последовательность чисел. Производящей функцией (производя-
(производящим рядом) для этой последовательности будем называть выражение
вида
а0 + ais + 2 +
1.3. Производящие функции 15
или, в сокращенной записи,
п=0
Если все члены последовательности, начиная с некоторого, равны нулю,
то производящая функция является производящим многочленом.
Числа, входящие в последовательность, могут иметь различную при-
природу. Мы будем рассматривать последовательности натуральных, це-
целых, рациональных, вещественных и комплексных чисел. Производя-
Производящую функцию, как и обычную функцию, мы будем часто обозначать
одной буквой, указывая в скобках ее аргумент:
A(s) = а0 + ats + a2s2 +...
Замечание 1.5. Употребляя слово «функция», мы вовсе не имеем
в виду, что написанное выражение действительно является функцией.
Так, не следует думать, будто мы можем сказать, чему равно «значе-
«значение A(so) производящей функции А в точке so». Переменная s является
формальной, и сумма ряда ао + a\So + a2sl + • • • смысла не имеет. Одна-
Однако верно утверждение А@) = а0, т. е. мы знаем значение производящей
функции в нуле.
Производящая функция представляет последовательность чисел в
виде ряда по степеням формальной переменной. Поэтому наряду с тер-
термином «производящая функция» мы будем также пользоваться терми-
термином «формальный степенной ряд».
Определение 1.6. Суммой двух производящих функций
A(s) = а0 + a.\s + a2s2 + ...
и
B(s) =6o +bis + b2s2 + ...
называется производящая функция
A(s) + B{s) = (a0 + b0) + {а\ + bi)s + (a2 + b-2)s2 +...
Произведением производящих функций А и В называется производя-
производящая функция
A(s)B(s) = n0b0
16 Глава 1. Элементарные производящие функции
Операции сложения и умножения производящих функций, очевидно,
коммутативны и ассоциативны.
Определение 1.7. Пусть
A(s) = ао + ais + CL2S2 + ...
B(t) = bo + bxt + b2t2 + b3t3 + ...
— две производящие функции, причем В@) = Ьо = 0.
Подстановкой производящей функции В в производящую функцию
А называется производящая функция
A(B{t)) = ао + o1bi* + (aih + огЬ?)<2 + (aib3 + 2a2bib2 + a3bl)t3 + ...
Если, например, B(t) = —t, то
A(B(t)) = A(-t) = ao-ait + a2t2 - a3t3 + ...
Обратите внимание на то, что операция подстановки функции, от-
отличной от нуля в нуле, не определена. При попытке подставить такую
функцию мы столкнулись бы с необходимостью суммировать бесконеч-
бесконечные числовые ряды.
Конечно же, если обе производящие функции А и В являются мно-
многочленами, то определения суммы, произведения и подстановки для них
совпадают с обычными определениями этих операций для многочленов.
Чтобы познакомиться с производящими функциями поближе, да-
давайте докажем важную теорему.
Теорема 1.8 (об обратной функции). Пусть функция
b1t + b2t2 + b3t3 + ...
такова, что В@) = Ьо = 0, a b\ ф 0. Тогда существуют такие функ-
функции
A(s) = ais + a2s2 +a3s3 + ..., A(Q) = 0,
и
С (и) = cj« + с2и2 + с3и3 + ..., С@) = 0,
что
A{B(t)) = t и В{С{и)) = и.
Функции А и С единственны.
Функция А называется левой обратной, а функция С — правой
обратной к функции В.
1.3. Производящие функции 17
Доказательство. Докажем существование и единственность левой
обратной функции. Доказательство для правой обратной аналогично.
Будем определять коэффициенты функции А последовательно. Коэф-
Коэффициент а,\ определяется из условия aifti = 1, откуда
1
01 = Г-
Предположим теперь, что коэффициенты cii, а2, ..., ап уже определе-
определены. Коэффициент an+i определяется иэ условия
где точками обозначен некоторый многочлен от oi, ..., ап и bi, ..., Ьп-
Тем самым, условие представляет собой линейное уравнение на ап+ь
причем коэффициент Ь"+1 при an+i отличен от нуля. Такое уравнение
имеет единственное решение, и теорема доказана.
Итак, мы научились складывать и умножать степенные ряды и под-
подставлять их друг в друга. Хотелось бы также научиться делить их
друг на друга. Последняя операция не всегда корректно определена.
В этом отношении степенные ряды похожи на целые числа: не всегда
целое число при делении на другое целое число дает в ответе целое
число. Однако, во всяком случае, возможно деление на степенной ряд,
значение которого в нуле отлично от нуля.
Предложение 1.9. Пусть
А(з) = ao+aiS + a2s2 + a3s3 +...
— формальный степенной ряд, причем А@) ф 0. Тогда существует
единственный формальный степенной ряд
B(s) = fo + М + hs2 + b3s3 + ...,
такой что A(s)B(s) = 1.
Доказательство. Снова проведем доказательство по индукции.
6о = --¦ Пусть теперь все коэффициенты ряда В вплоть до степени
п — 1 однозначно определены. Коэффициент при $п определяется из
условия
ооЬп + Oi6n_i + ... + anbo = 0.
Это линейное уравнение на Ь„, причем коэффициент а0 при Ьп отличен
от нуля. Поэтому уравнение имеет единственное решение.
18 Глава 1. Элементарные производящие функции
1.4. Элементарные производящие функции
Всякий раз записывать производящие функции в виде ряда неудоб-
неудобно. Поэтому для некоторых часто встречающихся функций использу-
используется сокращенная запись.
Определение 1.10.
!) (, + .)• = г + «, + ffc^ + ^-^-^.з + .... где
п! = 1-2-3-...пиа — произвольное комплексное число.
Коэффициент при sn в этой производящей функции называется чи-
числом сочетаний из а элементов по п и обозначается через
я!
If 2!
/ i \
3I
s--s3 + -s5-...;
l--s2 + -a4-...
Разложение 1) в определений 1-10 было введено Ньютоном и назы-
называется биномом Ньютона. При целом положительном значении а оно
совпадает с обычным определением степени бинома. Пользуясь этим,
мы можем получить простейшие комбинаторные тождества. Подста-
Подставляя, например, значения » = 1йв = -1, получаем
для любого целого положительного а.
Кроме того, между введенными элементарными функциями имеют-
имеются естественные соотношения, которые также связаны с комбинатор-
комбинаторными тождествами. Докажем, например, что
1.5. Дифференцирование и интегрирование 19
Действительно, свободный член произведения равен 1, а при п > О
коэффициент при а" в произведении равен
1 11 (-1)"
п!01 <п-1)!1! (п-2)!2! ' 0!п! '
Умножая последнее выражение на п!, получаем левую часть равен-
равенства A.3) при а = п, что и доказывает наше утверждение.
1.5. Дифференцирование и интегрирование производящих
функции
Определение 1.11. Пусть A(s) = ao+ais+a,2S2+... — производящая
функция. Производной этой функции называется функция
A'(s) = ах + 2a2s + 3a3s2 + ... + nansn~l + ...
Интегралом называется функция
л(\ л. «2 ¦ »3 °"+1
Операция дифференцирования обратна операции интегрирования:
= A(s).
Операция же интегрирования производной приводит к функции с ну-
нулевым свободным членом, и поэтому результат, вообще говоря, отли-
отличается от исходной функции.
Замечание 1.12. Нетрудно видеть, что для функций, представимых
в виде степенных рядов, формула для производной соответствует обыч-
обычной. Формула для интеграла соответствует значению интеграла с пе-
переменным верхним пределом
А(з) =
Последнее замечание позволяет подсчитывать (т. е. выражать в тер-
терминах элементарных) производящие функции для большого числа раз-
разнообразных последовательностей. Вычислим, например, производящую
функцию
/(.) = -L + 1 + 1 2. . 1 .....
w \ i л О О Q Q ^4
20 Глава 1. Элементарные производящие функции
Умножая функцию / на з2 и дифференцируя, получаем
откуда
1.6. Алгебра и топология формальных степенных рядов
Ниже приводятся некоторые сведения из теории формальных степенных
рядов. Они не используются в книге, но могут помочь обозначить место этой
теории в ряду других математических дисциплин.
С алгебраической точки зрения множество формальных степенных ря-
рядов (с коэффициентами в поле комплексных, вещественных или рациональ-
рациональных чисел) образует (бесконечномерное) векторное пространство над этим
полем. Операция умножения рядов превращает это векторное пространст-
пространство в алгебру, которая обозначается C[[s]] (соотв., R[[e]] или Q[[s]]). Важную
роль в этой алгебре играют идеалы, т.е. такие подмножества / С C[[s]], что
// С / для любого элемента / € C[[s]]. В алгебре формальных степенных
рядов все идеалы — главные, т. е. все они имеют вид /C[[s]] для некоторой
функции / € C[[s]]. Более того, все идеалы легко описать: они имеют вид
Ik — s*C[[s]], k = 0, 1, 2, (т.е. идеал /* состоит из всех формальных
степенных рядов, делящихся на sk). Один из идеалов Ik, а именно /i, макси-
максимален: он не содержится ни в каком другом идеале, отличном от всей алге-
алгебры. Алгебра с одним максимальным идеалом называется локальной. Свой-
Свойство локальности сближает алгебру формальных степенных рядов с коор-
координатными алгебрами в окрестности начала координат (алгебрами ростков
бесконечно дифференцируемых или аналитических функций). Факторалге-
бры C[[s]]//fc называются алгебрами срезанных многочленов и тоже очень
важны.
В алгебре формальных степенных рядов определена топология. От-
Открытыми в этой топологии являются идеалы Ik, к — 0, 1, 2, ... и пу-
пустое множество. Введенная топология определяет понятие сходимости:
последовательность Fi(s), F2(s), ... сходится к формальному степенному
ряду F(s), если для любого числа п существует такой номер N, что все
коэффициенты при степенях s°, sl, ..., sn у рядов Fk(s) при к> N со-
совпадают с коэффициентами при соответствующих степенях у ряда F(s).
В частности, последовательность частичных! сумм ряда F(s) сходится
к F(e).
1.7. Задачи 21
1.7. Задачи
1.1. Выпишите явно многочлены А?, и Аз и подсчитайте точно число
счастливых билетов.
1.2. Найдите выражение для числа счастливых билетов из 2г цифр
в системе счисления с основанием q.
1.3. Докажите следующие равенства:
a) sin2 s + cos2 s = 1;
i
r) ln(l + s) = s - ^
)(()) ()
1.4. Пусть функция В = B(s) = M + M2 + hs3 + ... такова, что
bi Ф 0. Докажите, что правая обратная функция A(s) и левая обратная
функция C(s) совпадают. Эта общая обратная функция обозначается
через В'1^).
1.5. Докажите, что степенные ряды вида
ais + a2s2 + ..., ai ф 0,
образуют группу относительно операции композиции.
1.6. Докажите, что не существует такого формального степенного
ряда A(s), что sA(s) = 1.
1.7. Докажите, что если каждый из степенных рядов A(s) и B(s)
отличен от нуля, то и их произведение A(s)B(s) отлично от нуля.
1.8. Пусть ряды A(s) = ао + a\s + a.2S2 + ..., ао Ф 0, и B(s) =
= b\s + Ьгв2 + ¦ ¦ •, Ь\ ф 0, имеют целые коэффициенты. При каких
условиях на коэффициенты этих рядов ряды . . , B~l(s) имеют целые
A(s)
коэффициенты?
1.9. Найдите производящие функции для последовательностей:
а) 1, 2,3,4,5,6, ...;
б) 1-2, 2-3, 3-4, ...
вI2,22,32,42,...
1.10. Докажите, что для ряда В = B(t) с нулевым свободным членом,
В@) = 0, и произвольного ряда А = A(s)
(формула замены переменных в интеграле).
22 Глава 1. Элементарные производящие функции
1.11. Докажите формулу Ньютона-Лейбница
(A(s)B{s))' = A'{a)B{s) + A{s)B'(s).
1.12. Докажите формулу интегрирования по частям:
\a(s)B'(s) + A'(s)B(s)) = A{s)B{s) - А@)В@).
1.13 (биномиальная система счисления). Докажите, что при задан-
заданном натуральном значении к любое натуральное число п единственным
образом представимо в виде
»(*)¦(»¦¦-(*)•
где 0 ^ bi < Ьг < • • • < bfc- Например, при к = 1 это верно, так как
всякое число п допускает единственное представление в виде п — ("),
а при к — 2 имеют место следующие представления
-СЮ
¦0*0
-сю
-СЮ)
(Напомним, что, по определению, (?) = 0 при целых р и q, таких что
О ^ р < <?.)
Глава 2
Производящие функции для известных
последовательностей
2.1. Геометрическая прогрессия
Простейшая последовательность — это постоянная последователь-
последовательность 1, 1, 1, ... Производящая функция для нее имеет вид
G(s) = l + s + s2 + s3 + ..., B.1)
и ее несложно выразить через элементарные производящие функции.
Действительно, умножив обе части равенства B.1) на а, получим
8G(s) = 8 + 82 + 83 + 8* + ...=
= G(s) - 1,
откуда
G(8) = ^-s. B.2)
Тот же вывод с незначительными изменениями проходит для про-
произвольной последовательности вида a, ar, ar2, ar3, ... :
Ga,r{8) = a + are + ar2s2 + ar3s* + ...=
= a {1 + (rs) + {rsf + (rsK + ...),
откуда
rsGa>r{8) = Gatr{8) - a
B-3)
Приведенные выше выкладки представляют собой не что иное, как
известный вывод формулы для суммы геометрической прогрессии. Ре-
Результат этих выкладок согласуется, как нетрудно видеть, с определе-
определением производящей функции A — в).
24 Глава 2. Известные последовательности
2.2. Последовательность Фибоначчи
Знаменитая последовательность Фибоначчи определяется своими
начальными членами /о = /i = 1 и соотношением
/„+2 = /п+1 + /п- B-4)
Из этого соотношения легко получить начало последовательности Фи-
Фибоначчи
1,1,2,3,5,8,13,21,34,...,
в которой каждый член, начиная с /г, равен сумме двух предыдущих.
Чтобы вывести формулу производящей функции
Fib(s) = 1 + s + 2s2 + 3s3 + 5s4 + ..., B.5)
умножим обе части равенства B.5) на s + s2. Получим
(s + s2)Fib(s) = s + s2 + 2s3 + 3s4 + 5s5 + ... +
+ s2 + s3 + 2s4 + 3s5 + ... =
= s + 2s2 + 3s3 + 5s4 + 8s5 + ...,
или
s2
(s + s2)Fib(s) = Fi
откуда
Fib(s) = * a. B.6)
1 — s — s
Полученную формулу можно понимать как композицию двух про-
производящих функций — A — s) и s + s2, т. е.
Fib(e) = 1 + (a + s2) + (s + s2J + (s + s2K + ...
Такое разложение, однако, не очень удобно, так как в его членах пере-
перемешаны различные степени переменных и оно не дает явной формулы
для коэффициентов. Полезнее представить дробь в виде суммы двух
элементарных дробей:
2.2. Последовательность Фибоначчи 25
гдев! = (-1+\/5)/2, s2 = (-1-\/5)/2— корни уравнения 1-s-s2 = 0.
Из последнего разложения немедленно получаем
Поэтому
Здесь мы воспользовались тем, что Sis2 = — 1.
Другой способ вывода производящей функции для чисел Фибоначчи
использует элементарные понятия линейной алгебры. Рассмотрим пару
последовательных чисел Фибоначчи /n, fn+i как координаты вектора
в двумерном вещественном пространстве R2:
Тогда соотношение B.4) можно интерпретировать как правило перехо-
перехода от вектора (/" ) к вектору ({п+12)'
Последнее преобразование линейно, и его можно записать в матричном
виде:
Переход от вектора (/"+^) к вектору (у"+2) осуществляется пу-
путем повторного применения преобразования Ф, и т. д. Таким образом,
производящая функция для векторной последовательности Фибоначчи
26 Глава 2. Извкстные последовательности
принимает вид
Здесь через / обозначена единичная матрица, / = I . 1 I, и мы приме-
применили к векторной производящей функции вывод производящей функ-
функции для геометрической прогрессии. Единственное отличие в результа-
результате: выражение (/-зФ) понимается как обратная матрица к матрице
I - яФ.
Явное выражение для чисел Фибоначчи можно получить, вычислив
явно матрицу Ф" для произвольного п. Для этого матрицу Ф нужно
диагонализировать, представив ее в виде
где Ф — диагональная матрица, а матрица L невырождена. Имеем,
S2 - S, \S, S2 / \ U S2
Отсюда, воспользовавшись соотношением
Ф" = L'4nL,
и выражениями для чисел Si, 6'2, по«1учаем равенство B.7).
2.3. Рекуррентные соотношения и рациональные
производящие функции
Последовательность Фибоначчи определяется линейным рекуррент-
рекуррентным соотношением fn+2 = /n+i + /n- Исходя из этого соотношения
и начальных значений последовательности, мы смогли найти явный вид
2.3. Рекуррентные соотношения 27
производящей функции. Производящая функция оказалась рациональ-
рациональной - отношением двух многочленов. На самом деле в нашем выводе
нигде не использовался специальный вид рекуррентного соотношения.
Действуя точно таким же образом, мы можем доказать аналогичную
теорему о производящей функции для произвольной последовательно-
последовательности, задаваемой линейным рекуррентным соотношением.
Теорема 2.1. Пусть последовательность ап задается линейным ре-
рекуррентным соотношением порядка к с постоянными С\, .. ¦, с/,.:
fln-t-fc = Cjan+k~\ + c,2an+k-2 + ¦ ¦ ¦ + с*а„ B.8)
и числа по, п\, ..., ак-\ заданы. Тогда производящая функция A(s) —
, ... Pis)
= «о + <i) s + u2S + ... рациональна, A{s) — п. ., причем степень мно-
многочлена Q равна к, а степень многочлена Р не превосходит к — 1.
Доказательство. Доказательство этой теоремы повторяет, по суще-
существу, рассуждение для чисел Фибоначчи. Умножив производящую фун-
функцию A(s) на C\s + C'>s2 + ... + cksk, получим
cksk)A(s) =
+
+ C2UQS2
c3a0s3
= P(s) + A(s),
ckaosk
где степень многочлена Р не превосходит к - 1. Действительно, коэф-
коэффициент при sn+k в правой части первого равенства совпадает с правой
частью выражения B.8). Отсюда непосредственно получаем утвержде-
утверждение теоремы.
Заметим, что доказательство теоремы 2.1 дало нам более сильное
утверждение: мы доказали, что многочлен Q имеет вид
Q(s) = 1 - cis - c2s2 - ... - cksk.
Вывод векторной производящей функции для последовательности
Фибоначчи также непосредственно переносится на случай произволь-
произвольной рекуррентной последовательности. В общем случае двумерный
Глава 2. Известные последовательности
вектор следует заменить fc-мерным вектором
а матрица А перехода к следующему fc-мерному вектору, соответству-
соответствующая рекуррентному соотношению, будет выглядеть так:
/0 10 ... О 0\
0 0 1 ... 0 0
B.9)
0 0 0 ... 0 1
Ск-1 Ск-г ¦¦¦ с2 с\)
ч,+1\
«п+2
\ап+к/
ап
Таким образом, мы получаем векторную производящую функцию
Матрица А, вообще говоря, не приводится к диагональному виду
линейным преобразованием. Это можно сделать, лишь если ее собствен-
собственные числа (т. е. корни многочлена Q) попарно различны. Однако в об-
общем случае ее можно привести к жордановои нормальной форме, сте-
степени которой также несложно вычислить.
Оказывается, что рациональные производящие функции в точно-
точности совпадают с производящими функциями для последовательностей,
задаваемых линейными рекуррентными соотношениями. Точнее, спра-
справедлива следующая обратная теорема.
Теорема 2.2. Если производящая функция A(s) = ao + a\S + a,2S2 + ...
рациональна, A(s) = ojfj, где многочлены Р и Q взаимно просты, то
начиная с некоторого номера п последовательность ао, ai, аг, ¦ ¦ ¦ за-
задается линейным рекуррентным соотношением
где к — степень многочлена Q, ас\, Сг, .. -, с* — некоторые констан-
константы.
Доказательство читателю предлагается провести самостоятельно.
2.4. Произведение Адамара 29
2.4. Произведение Адамара рациональных производящих
функции
Одно из наиболее привлекательных свойств рациональных произ-
производящих функций — их замкнутость относительно произведения Ада-
Адамара.
Определение 2.3. Произведением Адамара производящих функций
А(в) = ао + ais + а^а2 + ...
B(s) = bo + hs + b2s2 + ...
называется производящая функция
А о B(s) = aobo + aibis + а^Ьга2 + ...
Таким образом, произведение Адамара двух последовательностей —
это последовательность, состоящая из почленных произведений соот-
соответственных членов этих последовательностей. Необходимость в про-
производящей функции для произведения Адамара уже встречалась: в за-
задаче о числе счастливых билетов нам понадобилось вычислить сумму
квадратов коэффициентов производящего многочлена А%. Эта необ-
необходимость возникает при перечислении пар объектов одинакового по-
порядка: если число объектов первого типа равно ап, а число объектов
второго типа Ьп, то число пар объектов, составленных из элементов
первого и второго типа, равно апЬп.
Теорема 2.4. Произведение Адамара двух рациональных производя-
производящих функций рационально.
Для доказательства этой теоремы нам понадобится новая характе-
ризация рациональных производящих функций.
Лемма 2.5. Производящая функция для последовательности ао, п\,
а,2, ... рациональна тогда и только тогда, когда существуют такие
числа (ft, ..., qi и такие многочлены pi(ri), ..., pt(n), что начиная с
некоторого номера п
an=Pl(n)q? + ...+Pl(n)q? B.10)
Выражение в правой части равенства B.10) называется квазимно-
квазимногочленом от переменной п.
30 Глава 2. Известный последовательности
Доказательство. Заметим прежде всего, что производящая функ-
функция A - qs)~k имеет вид
а - «-г* = 1 - (-;*) ч»+(~*) в2-2 - (~3*) в3-3+• ¦ ¦=
Jfc +1\ , 2 /Н2
2 J^+(
Коэффициент при sn в этой производящей функции равен
(п + 1)(п + 2) ¦¦¦(» + *-Dqn = Pt_i(n)gni BЛ1)
(,« — i).
где Pjt_i(n) — многочлен от п степени к—1. Всякая рациональная фун-
функция от переменной s представляется в виде линейной комбинации мно-
многочлена и элементарных дробей вида A — QiS)~ki, поэтому коэффици-
коэффициенты соответствующей производящей функции являются квазимного-
квазимногочленами.
Наоборот, предположим, что коэффициенты производящей функ-
функции, начиная с некоторого номера, представляются в виде квазимно-
квазимногочлена. Покажем, что в случае квазимногочлена p(n)qn соответству-
соответствующая производящая функция рациональна. Пусть степень многочле-
многочлена р равна к — 1. Многочлены Pq, Pi, ..., Рь-\. определенные равен-
равенством B.11), образуют базис в пространстве многочленов степени не
выше к—1. Действительно, любая последовательность многочленов сте-
степеней 0, 1, ..., к— 1 образует базис в этом пространстве. Поэтому мно-
многочлен р представляется в виде линейной комбинации многочленов Р;
и соответствующая производящая функция есть просто линейная ком-
комбинация функций A - qs)~i, j = 0, 1, ..., fe — 1. Для произвольного
квазимногочлена мы получаем линейную комбинацию функций такого
вида при разных д*. Лемма доказана.
Доказательство теоремы 2.4. Для завершения доказательства те-
теоремы осталось заметить, что произведение квазимногочленов явля-
является квазимногочленом. Это утверждение непосредственно вытекает
из формулы B.10).
2.5. Числа Каталана 31
2.5. Числа Каталана
Порядок вычислений в арифметических выражениях задается рас-
расстановкой скобок, например,
C-1)-D+ A5-9)-B +б)).
Если стереть все элементы выражения, за исключением скобок, то
оставшиеся скобки образуют правильную скобочную структуру:
Вот все правильные скобочные структуры с числом пар скобок 1, 2
иЗ:
0
00 @)
000 0@) @H @0) ((()))
Определение 2.6. Числом Каталана сп называется число различных
правильных скобочных структур из п пар скобок.
Удобно полагать Со = 1. Тогда последовательность чисел Каталана
начинается так:
1, 1, 2,5, 14,42, 132, ...
Чтобы вывести производящую функцию для чисел Каталана, най-
найдем сначала рекуррентное соотношение для этих чисел.
Всякая правильная скобочная структура удовлетворяет следующим
двум условиям:
1) число левых и правых скобок в правильной скобочной структуре
одинаково;
2) число левых скобок в любом начальном отрезке правильной ско-
скобочной структуры не меньше числа правых скобок.
Наоборот, всякая (конечная) последовательность левых и правых
скобок, удовлетворяющая условиям 1) и 2), является правильной ско-
скобочной структурой.
В правильной скобочной структуре все скобки разбиваются на па-
пары: каждой левой скобке соответствует парная ей правая. Парная пра-
правая скобка выделяется следующим правилом: это первая правая скобка
справа от данной левой скобки, такая, что между выбранными двумя
скобками стоит правильная скобочная структура.
32 Глава 2. Известные последовательности
Рассмотрим в правильной скобочной структуре из гг + 1 пары ско-
скобок пару скобок, в которую входит самая левая скобка структуры. То-
Тогда последовательность скобок внутри этой пары образует правильную
скобочную структуру и последовательность скобок вне этой пары обра-
образует правильную скобочную структуру: (...)..., где каждое многото-
многоточие обозначает некоторую правильную скобочную структуру. Если чи-
число пар скобок во внутренней структуре равно к, то во внешней струк-
структуре п — к пар скобок. Наоборот, по каждой паре скобочных структур
из к и п — к пар скобок можно восстановить структуру из п + 1 пары
скобок, заключив первую структуру в скобки и приписав к результату
справа вторую структуру.
Отсюда мы получаем рекуррентное соотношение для чисел Катала-
на. На этот раз соотношение оказывается нелинейным:
с„+1 =cocn + cicn_i +... + cnco- B.12)
Например, при п = 4
С5 = СоС4 + С1С3 + С2С2 + С3С1 + С4С0 =
= 1-14+ 2-5 + 2-2 + 5-1 +14-1 =
= 42.
Рассмотрим производящую функцию для чисел Каталана
Cat(s) = со + c\s + C2S2 + ... =
= 1 + s + 2s2 + 5s3 + ...
Возведя ее в квадрат и умножив результат на s, получим
sCat2(s) = els + (coci + cico)s2 + (сосг + CiCi + c2c0)s2 + ... =
= s + 2s2 + 5s3 + 14s4 + ... =
= Cat(s) - 1,
что дает нам квадратное уравнение на производящую функцию
s Cat2(s) - Cat(s) + 1 = 0, B.13)
откуда
B.14)
2.5. Числа Каталана
33
(Второй корень уравнения отбрасывается, так как A + \/1 - 4s)/2s =
= 1/s + ... содержит отрицательные степени s.)
Вид производящей функции B.14) позволяет найти явную формулу
для чисел Каталана. Согласно биному Ньютона
с„ =
113
2 ' 2'2
2п-1 .„+1
2(n+ 1)!
откуда, умножая числитель и знаменатель на п! и сокращая на 2"+1,
получаем
_ Bп)! _
41
B.15)
Последняя формула дает и более простое (хотя и с переменными
коэффициентами) рекуррентное соотношение для чисел Каталана:
Сп+1 =
B.16)
Числа Каталана перечисляют самые разнообразные комбинаторные
объекты. Литература, им посвященная, необозрима. Известно несколь-
несколько десятков их различных определений. Приведем лишь еще две часто
встречающиеся их реализации.
Рис. 2.1. Диагональные триангуляции 4- и 5-угольника
Рассмотрим выпуклый (п + 2)-угольник, вершины которого зануме-
занумерованы против часовой стрелки числами от 0 до п + 1. Диагональной
триангуляцией назовем разбиение многоугольника на треугольники не-
непересекающимися диагоналями. Всякая такая триангуляция содержит
п — 1 диагональ. На рис. 2.1 приведены все различные диагональные
триангуляции четырехугольника и пятиугольника.
34 Глава 2. Известные последовательности
О 1
Рис. 2.2. Треугольник, примыкающий к стороне 01
Пусть tn — число триангуляции (п 4- 2)-угольника при п ^ 1; поло-
положим $о = 1- Рассмотрим произвольную триангуляцию и выделим тре-
треугольник, примыкающий к стороне 01 (см. рис. 2.2). Пусть к — номер
третьей вершины этого треугольника. Выделенный треугольник разби-
разбивает (п+2)-угольник на &-утольник и (п—&4-3)-угольник, каждый из ко-
которых триангулирован диагоналями. Перенумеруем вершины этих мно-
многоугольников против часовой стрелки так, чтобы нумерация вершин
в каждом из них начиналась с 0 (см. рис. 2.3). В результате получим
пару триангуляции А;-угольника и (п - к + 3)-угольника.
Наоборот, каждая пара триангуляции А;-угольника и (п — к + 3)-
угольника определяет триангуляцию исходного многоугольника. По-
Поэтому
tn+l = Mr» + Mn-1 .+ •••+ tnto,
и, поскольку t0 = 1, последовательность чисел tn совпадает с последо-
последовательностью Каталана.
Описанная выше процедура сопоставления триангуляции (п + 2)-
угольника пары триангуляции А;-угольника и (п — к + 3)-угольника по-
позволяет установить и взаимно-однозначное соответствие между триан-
гуляциями (п + 2)-угольника и скобочными структурами из п пар ско-
скобок. Действительно, предположим, что для всех меньших значений п та-
такое соответствие установлено. Каждой триангуляции (п + 2)-угольника
мы сопоставили пару триангуляции многоугольников с меньшим чи-
числом сторон. По предположению, этой паре триангуляции соответству-
соответствует пара скобочных структур. Заключим первую из этих скобочных
2.5. Числа Каталана
35
Jfc-1
Jfc-2
Рис. 2.3. Перенумерация вершин многоугольников разбиения
структур в скобки и припишем к ней вторую — получим новую скобоч-
скобочную структуру, соответствующую исходной триангуляции всего (п+2)-
угольника.
Еще одна важная реализация чисел Каталана связана с путями Ди-
Дика на плоскости. Рассмотрим целочисленную решетку в положитель-
положительном квадранте. Путем Дика называется непрерывная ломаная в верх-
верхней полуплоскости, составленная из векторов A, 1) и A, -1), начина-
начинающаяся в начале координат и заканчивающаяся на оси абсцисс (см.
рис. 2.4).
Рис. 2.4. Путь Дика и соответствующая ему скобочная структура
36 Глава 2. Известные последовательности
Совершенно ясно, как устанавливается соответствие между путя-
путями Дика и правильными скобочными структурами: нужно сопоста-
сопоставить вектору A, 1) левую скобку, а вектору A, -1) — правую скоб-
скобку (рис. 2.4). Тогда условие, что путь лежит в верхней полуплоскости
и заканчивается на оси абсцисс, и есть в точности условие правильно-
правильности скобочной структуры. Поэтому
Число путей Дика из 2п звеньев равно п-му числу Капитана с„.
2.6. Задачи
2.1. Докажите, что если последовательность ап допускает предста-
представление в виде B.10) и все ф различны, то такаое представление един-
единственно с точностью до порядка слагаемых.
2.2. Воспользовавшись предыдущей задачей, докажите, что функ-
1 а2 а3
ция In = а + — + — + ... не рациональна.
1 — а ^ о
2.3. Рациональны ли производящие функции для последовательно-
последовательностей:
а) 1, -2, 3, -4, 5, ...;
б) 2, -6, 12, ..., (-l)*(fc + l)(fc + 2), ...;
вI,-4,9,-16,...,(-1)*(* + 1J,...;
.-11 1
rI'4'9'---'F'"";
д) /^, где /п — числа Фибоначчи?
Найдите соответствующие производящие функции в тех случаях,
когда они рациональны.
2.4. Пусть A(s) = ао + ais + a^s2 +... — производящая функция для
последовательности а0, а\, аг, ... Найдите производящие функции для
последовательностей:
а) ао + <*i, а\ + п2, Qq + аз, ¦. ¦ ;
б) ао, оо ¦+¦ а\, ао + ai 4- а2, • • ¦;
в) ао, a\b, а^Ь , азЬ , • -.;
г) ао, п2, Л4, Об, ag, ...
2.5. Пользуясь производящей функцией для чисел Фибоначчи, дока-
докажите для них тождества:
а) /о + /i + ... + /п = /п+2 - 1;
в) /i + /з + . • • + /2„_1 = /2п - 1;
2.6. Задачи
37
2.6. Докажите, что в жордановой нормальной форме матрицы из
уравнения B.9) каждому собственному числу соответствует одна жор-
данова клетка, размер которой равен кратности этого собственного
числа как корня характеристического многочлена.
2.7. Найдите производящие функции и явные выражения для эле-
элементов последовательностей, заданных рекуррентными формулами:
а) ап+2 - 4а„+1 - 4а„, а0 = ах = 1;
б) ап+3 = -За„+2 - За„+1 - а„, а0 = 1, ai = аг = 0;
3 1
в) ап+3 = 2ап+2 — 2а"> ао = 0, ai = 1, аз = 2.
2.8. Найдите произведения Адамара функций от s
1, A-д8)-1оA-д8Г\ (I - qs)~2 о (I -
A -
о A -
, A -
о A - rs)
'1
2.9. Пути Моцкина определяются так же, как и пути Дика, только
они могут включать в себя горизонтальные векторы A,0) (см. рис. 2.5).
Число путей Моцкина из п векторов называется n-м числом Моцки-
Моцкина и обозначается через тп. Вот начало последовательности Моцкина:
то = 1, mi = 1, ТП2 = 2, тпз = 3. Вычислите несколько следующих
членов этой последовательности. Найдите для нее рекуррентное соот-
соотношение и производящую функцию.
Рис. 2.5. Путь Моцкина
2.10. Придумайте алгоритмы последовательного вывода а) правиль-
правильных скобочных структур; б) путей Моцкина. Постарайтесь, чтобы ал-
алгоритмы были как можно более эффективны.
2.11. Рассмотрим множество путей на прямой, состоящих из шагов
длины 1 вправо или влево. Найдите производящую функцию для числа
38 Глава 2. Известные последовательности
таких путей из п шагов, начинающихся в 0 и а) оканчивающихся в 0;
б) оканчивающихся в 0 и не заходящих в отрицательную полупрямую;
в) оканчивающихся в фиксированной точке N > 0; г) оканчивающихся
в фиксированной точке N > 0 и не заходящих в отрицательную полу-
полупрямую.
2.12. Рассмотрим множество путей на плоскости, состоящих из век-
векторов A, 0), (—1, 0), @, 1). Найдите производящую функцию для числа
таких путей длины п, начинающихся в 0 и несамопересекающихся (т. е.
векторы A, 0) и (—1, 0) не могут идти непосредственно друг за дру-
другом).
2.13. Двое играют в такую игру. Один задумывает целое число от 1
до 144, а второй пытается его отгадать, задавая вопросы, на которые
первый (честно) отвечает «да» или «нет». В случае ответа «да» второй
платит 1 рубль, в случае ответа «нет» — 2 рубля. Как должен играть
второй игрок, чтобы сделать свой проигрыш в наихудшей ситуации
минимальным? А как он должен себя вести, если вместо 144 стоит
другое число?
2.14. (Задача Гиппарха.) Следующая цитата — из «Застольных бе-
бесед» Плутарха1': «Хризипп говорит, что число комбинаций, которые
можно получить из десяти простых предложений, превосходит один
миллион. На это возразил Гиппарх, указав, что одно утвердительное
предложение охватывает включенных в него сто три тысячи сорок де-
девять, а отрицательное — триста десять тысяч девятьсот пятьдесят
два».
Проверьте утверждение Гиппарха, считая что
> утвердительное сложное предложение строится из п простых
предложений (обозначаемых ниже латинскими буквами) путем
заключения их всеми возможными способами в (не более чем)
п — 2 пар скобок. Например, из трех простых предложений можно
составить 3 сложных:
а, Ь, с; (а,Ъ),с; а, (Ъ, с),
а из четырех простых предложений — 11 сложных:
а, Ъ, с, d; а, (Ь, с, d); (а, Ъ, с), d; а, Ь, (с, d);
а, (Ь, с), d; (а, Ь), c,d; а, (Ь, (с, d)); а, ((Ь, с), d);
(а, (b,c)),d; ((a,b),c),d; (а, Ь), (с, d);
^Плутарх. Застольные беседы / Перев. Я. М. Боровского. М., 1987. VIII.9, с. 157;
в переводе имеется опечатка: «триста девять тысяч...» вместо «триста десять...».
2.6. Задачи 39
> отрицательное сложное предложение строится из п простых пред-
предложений, предваряемых отрицанием, путем заключения их всеми
возможными способами в (не более чем) п — 1 пар скобок. Напри-
Например, из трех простых предложений можно составить 7 сложных
отрицательных:
поа, 6, с; (поа, 6), с; поа, F, с); по(а, Ъ), с;
по(а, 6, с); по((а, Ь), с); по(а, F, с)).
(Во втором случае ответ несколько отличается от предложенного Гип-
пархом.)
Выведите производящие функции для соответствующих последова-
последовательностей.
2.15. (Фибоначчиева система счисления.) Докажите, что любое на-
натуральное число единственным образом представляется в виде aifi +
+ ^2/2 + • • •, где /п — числа Фибоначчи, а каждое из чисел а,- равно
нулю или единице, причем единиц в сумме конечное число и два иду-
идущих подряд элемента последовательности а,- не могут равняться еди-
единице. (Обратите внимание на то, что число /о = 1 не используется,
так что последовательность Фибоначчи начинается так: 1, 2, 3, 5, 8, 13,
...) Придумайте алгоритмы перевода чисел из фибоначчиевой систе-
системы счисления в позиционную и обратно, а также алгоритмы сложения
и умножения чисел в этой системе счисления.
2.16. Пусть
рациональные производящие функции, заданные несократимыми дро-
дробями, и
их произведение Адамара, представленное в виде несократимой дроби.
Что можно сказать про многочлен Q, если многочлены Q\ и Q2 извест-
известны?
Глава 3
Формальные грамматики с однозначным
выводом. Теорема Лагранжа
3.1. Язык Дика
Как мы знаем, правильные скобочные структуры перечисляются чи-
числами Каталана. Выпишем все правильные скобочные структуры до по-
порядка 4:
О (О) ((())) ( ( ( ( )))) ((()))() ()(()())
abab
н н птш mum
aba aH aataalH ааббаЬаЬ abababab
a b a b a b aabababb abaaabbb
Если обозначить левую скобку буквой а, а правую — буквой Ь, то
можно переписать правильные скобочные структуры в виде «слов» в ал-
алфавите {a, b}. В приведенной выше таблице под каждой скобочной
структурой записано соответствующее ей слово.
При такой записи мы получаем не все слова в алфавите {а, Ь}, а толь-
только некоторые. Например, слова а, Ь, аа, Ьа не соответствуют никаким
правильным скобочным структурам.
Определение 3.1. Пусть А = {а\, аг, .. -, а*} — произвольный ко-
конечный набор различных букв. Словом в алфавите А называется про-
произвольная конечная последовательность букв aiQ2 • • -ат, где щ € А,
i = 1, ..., т. Число т называется длиной слова. Языком над алфави-
алфавитом А называется произвольное (конечное или бесконечное) множество
слов в алфавите А.
Пустое слово А имеет длину 0 и может входить или не входить
в язык.
Пример 3.2. Язык J- состоит из слов в алфавите {a, b}, не содержа-
содержащих двух букв Ь подряд: A, a, b, ab, ba, aaa, aab, aba, baa, bab, aaaa, ...
Множество правильных скобочных структур вместе с пустой струк-
структурой образует язык над алфавитом {a, b}. Этот язык называется язы-
языком Дика. Конечно, тот же язык мы могли бы рассматривать и над
алфавитом {( , )}; просто символы а, Ь в нашем восприятии более со-
соответствуют термину «буква».
3.2. Правила вывода - 41
Определение 3.3. Производящей функцией языка L называется про-
производящая функция
L(s) =¦ lo + l\s + l^s + ...,
где Ik есть число слов длины А; в языке L.
3.2. Правила вывода в языке Дика
Выписывание всех скобочных структур данной длины — трудоем-
трудоемкий процесс. Чтобы не пропустить ни одной структуры и не повторить
никакую структуру дважды, этот процесс надо упорядочить. Один из
способов добиться упорядочения состоит в том, чтобы рассмотреть
два правила вывода в языке Дика:
1) г —» А;
2) г —> arbr. * " '
Здесь г — буква, не входящая в алфавит {a, ft}. Вместо нее мы могли
бы выбрать любую букву, отличную от а и Ь.
Стрелка в правилах вывода C.1) заменяет фразу:
если в слове есть буква г, то эту букву можно заменить на слово,
стоящее справа от стрелки.
Покажем, как работают правила вывода: выведем по этим правилам
заданную скобочную структуру.
Пусть нам нужно вывести слово aabaabbb. Вот, как выглядит вывод:
2) 1) 2) 1) 2) 1)
г —> arbr_ —> arb —> aarbrb —> aabrb —> aabarbrb —>
—> aabarbb —l aabaarbrbb —'-4 aabaabbb.
Над каждой стрелкой в процессе вывода написан номер применен-
примененного правила. Буква г, к которой применялось правило, подчеркнута.
Правила вывода в языке Дика можно понимать следующим образом:
Всякое слово в языке Дика есть либо
1) пустое слово,
либо
2) слово, в котором внутри самой левой пары соответственных
скобок стоит некоторое слово языка Дика и после этой пары стоит
слово языка Дика.
Ясно, что для каждого слова языка Дика такое представление един-
единственно.
42 Глава 3. Формальные грамматики
Вычислим с помощью правил вывода производящую функцию для
языка Дика. Для этой цели выпишем «некоммутативный производящий
ряд», перечисляющий слова языка. Этот ряд представляет собой просто
формальную сумму всех слов языка, выписанных в порядке возрастания
длины:
V(a, b) = X + ab+ aabb + abab + aaabbb + aababb + ... C.2)
Теорема З.4. Ряд C.2) удовлетворяет уравнению
V{a, b) = X + aV{a, b)W(a, b). C.3)
Доказательство. Действительно, в левой части равенства C.3) запи-
записана сумма всех слов языка Дика. Равенство означает справедливость
утверждения
Всякое слово в языке Дика есть либо
1) пустое слово,
либо
2) слово, в котором внутри самой левой пары соответственных
скобок стоит некоторое слово языка Дика и после этой пары стоит
слово языка Дика.
При этом такое представление единственно. Теорема доказана.
Чтобы перейти от некоммутативного производящего ряда к обыч-
обычному, сделаем подстановку а = s, b = s, A = s° = 1. Уравнение C.3)
примет вид
V(s, s) = l+s2V(s, s).
Отсюда, обозначив T>(s, s) через d(s), получим
d(s) = l + s2d2(s). C.4)
Решение
этого уравнения, конечно же, совпадает (с точностью до возведения
формальной переменной в квадрат) с производящей функцией для чи-
чисел Каталана B.14). Необходимость подстановки переменной s2 вместо
s объясняется тем, что в языке Дика длина слова, составленного из п
пар скобок, равна 2п, тогда как ранее мы перечисляли эти слова по
числу пар скобок.
3.3. Формальные грамматики 43
3.3. Формальные грамматики с однозначным выводом
Приведем обобщение рассуждения из предыдущего раздела.
Определение 3.5. Слово w = Д.... /Зт языка L называется неразло-
неразложимым в этом языке, если никакое его непустое подслово /?i/?i+i • • • А+/ >
1 ^ г, г + I ^ т, I ^ 0, отличное от самого слова w, не принадлежит
языку L.
В частности, пустое слово в любом языке неразложимо. Предполо-
Предположим, что язык L обладает следующими свойствами:
1) пустое слово входит в язык L;
2) начало всякого неразложимого слова
не совпадает с концом другого или того же
самого неразложимого слова;
3) если между любыми двумя буквами C-5)
любого слова языка L вставить слово языка L,
то получится слово языка L;
4) если из любого слова языка L выкинуть подслово,
входящее в язык L, то получится слово языка L.
Обозначим через n(t) = по + пуг + гаг*2 +... производящую функцию
для числа неразложимых слов языка L, через l(s) = l0 + hs+fas2 +... —
производящую функцию для языка L.
Теорема 3.6. Производящая функция для языка L, удовлетворяю-
удовлетворяющего условиям C.5), и производящая функция для подъязыка неразло-
неразложимых слов в нем связаны между собой уравнением Лагранжа
1(8) = n(8l(S)). C.6)
Доказательство. Каждому неразложимому слову а^ ...сцт в язы-
языке L сопоставим правило вывода
г —> а^га^г.. .сщтг.
Ясно, что каждое слово языка допускает вывод по этим правилам. Та-
Такой вывод однозначен. Действительно, пусть 0i.. ¦ 0k —-произвольное
слово языка L. Если оно неразложимо, то оно представляется в виде
правой части правила вывода
44 Глава 3. Формальные грамматики
где каждое вхождение символа г следует заменить на пустое слово.
Из определения неразложимого слова вытекает, что такое представле-
представление единственно.
Предположим теперь, что есть разложимые слова, допускающие
различное представление. Рассмотрим самое короткое такое слово w.
В нем содержится неразложимое подслово. Выберем из всех неразло-
неразложимых подслов слова го самое правое (это возможно, так как нераз-
неразложимые подслова не могут пересекаться) и выкинем его из слова w.
Получим новое слово w'. Это слово имеет те же самые представления
в виде правых частей правил вывода, что и слово w. Поэтому w' — бо-
более короткое слово, допускающее несколько различных представлений.
Полученное противоречие доказывает единственность представления.
Таким образом, некоммутативная производящая функция для язы-
языка L удовлетворяет уравнению
.., ат) =
Делая подстановку А = 1, сц = t и учитывая, что l(t) = C(t, t, ..., t),
получаем заключение теоремы.
Пример 3.7. Для языка Дика n(t) = 1 + t2. Неразложимые слова —
это А и aft. Отсюда немедленно получаем уравнение C.4) на производя-
производящую функцию для языка Дика.
Одного символа зачастую бывает недостаточно для построения
грамматики. Дадим формальное определение грамматики.
Определение 3.8. Пусть R = {п, ...,г/} — конечное множество
символов, не входящих в алфавит А. Правилом вывода называется за-
запись вида
П —>w,
где п € R, а w — слово в алфавите A LJ R. Множество Г (конечное или
бесконечное) правил вывода
П —У wn,
называется (контекстно свободной) грамматикой (над алфавитом А).
Слово в алфавите А порождается символом г*, если оно может быть по-
получено цепочкой подстановок, задаваемых грамматикой, из символа г*.
3.3. Формальные грамматики 45
Язык Li, порождается символом г*, если все слова языка Li и только
они порождаются символом п. Грамматика Г является грамматикой
с однозначным выводом, если каждое слово, выводимое из символа г*,
единственным образом представляется в виде правой части одного из
правил вывода гj —> Wik.
В связи с задачами перечисления наибольший интерес для нас пред-
представляют формальные грамматики с однозначным выводом. Такая
грамматика была построена для языка Дика. Приведем еще один по-
подобный пример.
Пример 3.9. Рассмотрим язык Т из примера 3.2. Вот возможная
грамматика для этого языка:
П -
п -
п -
Гл -
н- А,
-+ ь,
-> г2Ь,
~* Г2,
Т2 \ Т\п.
Язык Т выводится из символа ri. Из символа г2 выводится подъязык
языка J-, состоящий из слов, кончающихся на а.
Приведенная грамматика читается так:
1) всякое слово языка Т есть либо пустое слово, либо слово Ь, либо
слово языка Т, кончающееся на а, к которому приписана буква Ь, либо
слово языка Т, кончающееся на а;
2) всякое слово языка Т, кончающееся на а, есть некоторое слово
языка Т, к которому приписана буква а.
Теорема 3.10. Пусть Г — грамматика с однозначным выводом.
Обозначим через rj(s) производящую функцию для числа слов в языке
Li, выводимого из символа rj. Тогда производящие функции ri удовле-
удовлетворяют системе уравнений
В частности, если число правил вывода конечно, то функции ri удо-
удовлетворяют системе полиномиальных уравнений и поэтому являются
алгебраическими функциями.
Доказательство. Поступим, как и в ситуации с одним порождаю-
порождающим символом, — введем некоммутативные производящие степенные
46 Глава 3. Формальные грамматики
ряды для каждого из языков L{. Ввиду однозначности представления
каждого слова в виде правой части правила вывода получаем систему
уравнений на некоммутативные ряды. Делая подстановку А = s° = 1,
щ = s при i = 1, ..., т, получаем систему уравнений на производящие
функции для числа слов. Теорема доказана.
3.4. Уравнение Лагранжа и теорема Лагранжа
Посмотрим повнимательнее на равенство C.6). Это функциональное
уравнение, связывающее между собой производящие функции для числа
слов в языке и числа неразложимых слов в нем. Нам бы хотелось уметь
его решать, если одна из функций задана. Оказывается, это всегда
возможно.
Чтобы привести наше уравнение к классическому виду, домножим
обе его части на s и положим sl(s) = l(s). Тогда уравнение C.6) примет
вид
Последнее уравнение называется уравнением Лагранжа, и для него
справедлива следующая теорема.
Теорема 3.11 (Лагранж). Пусть в уравнении C.7) задана одна из
производящих функций l(s) (lo = О, 1\ф 0) или n(t) (no ф 0). Тогда
вторая производящая функция однозначно восстанавливается по ней.
Доказательство. Уравнение C.7) можно переписать в следующем ви-
hs + hs2 + ... = щ,8 + nis hs + hs2 + ks3 +.
+ 2IJ2S3 +.
lh3 + ¦
Докажем сначала, что если функция I(s) задана, то n(t) однозначно
восстанавливается по ней. Доказательство проведем по индукции, при-
приравнивая последовательно коэффициенты при одинаковых степенях s
в левой и правой частях.
Коэффициент по определяется равенством
по = h-
3.5. Задачи 47
Предположим теперь, что коэффициенты по, щ, ..., Пк-i уже опреде-
определены. Тогда коэффициент п* определяется из уравнения, составленного
приравниванием коэффициентов при sk+1:
nj* + nfc_iAfc_i + ... + щAi = f*. C.8)
Здесь через Aj, i — 2, ..., A; - 1, обозначены коэффициенты при sk
в производящих функциях Iх {s). Уравнение C.8) — линейное уравне-
уравнение относительно Пк- Коэффициент при Пк в нем равен [f и, по усло-
условию теоремы, отличен от нуля. Поэтому п* однозначно определяется
из уравнения C.8).
С другой стороны, если задана функция n(t), то мы должны поло-
положить h = «о. Коэффициенты /* определяются теперь равенством C.8),
так как все коэффициенты А; являются многочленами от /i, ..., lk-i-
Теорема доказана.
Замечание 3.12. Если коэффициенты функции п — целые неотрица-
неотрицательные числа, то и коэффициенты функции I будут целыми и неотри-
неотрицательными. Если коэффициенты функции J целые и неотрицательные,
причем 1\ — 1, то и коэффициенты функции п оказываются целыми.
Однако при этом среди них могут оказаться и отрицательные числа.
3.5. Задачи
3.1. Докажите, что грамматика из примера 3.9 действительно опи-
описывает язык J- из примера 3.2 и что вывод в ней однозначен. Воспользо-
Воспользовавшись этой грамматикой, найдите производящую функцию для язы-
языка Т.
3.2. Придумайте для языка Т порождающую грамматику с одним
порождающим символом и однозначным выводом.
3.3. Покажите, что в грамматике
г —v А;
г —> га;
г —> br;
г —> агЬ
вывод не однозначен.
3.4. Напишите правила вывода для языка правильных скобочных
структур из двух пар скобок (круглых и квадратных) и выведите про-
производящую функцию для него. Этот яэык называется языком Дика
48 Глава 3. Формальные грамматики
второго порядка. Обобщите результат на языки Дика произвольного
порядка.
3.5. Задайте с помощью формальных грамматик языки систем путей
из задач 2.11, 2.12; выведите отсюда соответствующие производящие
функции.
3.6. Языком Моцкина называется язык в алфавите {а, Ь, с}, состо-
состоящий из таких слов, что зачеркивание всех букв с в них дает слово
из языка Дика. Слова в языке Моцкина находятся во взаимно одно-
однозначном соответствии с путями Моцкина из задачи 2.9. Постройте для
языка Моцкина грамматику с однозначным выводом и найдите с ее
помощью производящую функцию для этого языка.
3.7. Постройте грамматику для языка натуральных чисел, записан-
записанных в двоичной системе счисления.
3.8. Постройте грамматику для языка правильных арифметических
выражений в двоичной системе счисления в алфавите: {(,),+, 1, 0}.
3.9. Постройте грамматики для языков
) {|?j?};
в) Lz = {w | число вхождений буквы а в слово w равно числу вхожде-
вхождений буквы b в это слово};
г) L/4 = {w | число вхождений буквы а в слово w вдвое больше числа
вхождений буквы Ь);
д) L5 = {слова в однобуквенном алфавите, длина которых делится
на 2 или на 3};
е) Ьв = множество палиндромов в алфавите из трех букв. (Палин-
(Палиндромом называется слово, одинаково читающееся слева направо и спра-
справа налево.)
ж) L-r = {слова в алфавите {а, Ь}, содержащие четное число вхожде-
вхождений буквы а}.
Найдите производящие функции для этих языков.
3.10. Докажите справедливость замечания 3.12.
3.11. Найдите производящие функции для языков из двух букв, слова
которых не содержат:
а) подслова Ьа;
б) подслова aba.
Глава 4
Аналитические свойства функций,
представляемых степенными рядами,
и асимптотика их коэффициентов
4.1. Степенные оценки для асимптотики
При решении перечислительных задач зачастую приходится инте-
интересоваться поведением числа элементов множества при росте перечи-
перечисляющего параметра. Это особенно важно, если мы хотим, например,
перечислять объекты на компьютере и пытаемся оценить время работы
программы.
Определение 4.1. Функции /:N-»Rhj:N->R имеют одинако-
одинаковую асимптотику, или одинаковый рост, при п -* оо, если существует
предел lim ЦЩ и он равен 1. Функция / растет медленнее функции д,
если предел lim Д^4 существует и он равен 0. В последнем случае го-
говорят также, что функция д растет быстрее функции /.
При вычислении асимптотики некоторые функции мы считаем «об-
«образцами», а другие «сводим» к этим образцам. В качестве образцов бе-
берутся обычно наиболее простые монотонные функции, поведение кото-
которых хорошо изучено. Образцами могут служить:
> экспонента а" при различных значениях основания а;
> степенная функция па при различных значениях показателя а;
> факториал п\;
> логарифм In n;
а также произведения и композиции этих функций в различных комби-
комбинациях.
Нетрудно расположить функции-образцы в порядке убывания ско-
скорости роста:
п\; ап,а>1; па,а>0; Inn; па, а < 0; а", 0 < а < 1.
Пример 4.2. Коэффициенты производящей функции 1пA — s)-1 =
= s + |s2 + |s3 +... растут, как п" (в этом случае естественнее было
бы говорить «убывают, как п~1*).
50 Глава 4. Асимптотика коэффициентов
В наших дальнейших рассуждениях формальная переменная s заме-
заменяется комплексной переменной s € С.
Наиболее простой и чаще всего используемый способ оценки ско-
скорости роста коэффициентов производящей функции дает следующая
теорема, основанная на признаке Коши сходимости числовых рядов.
Теорема 4.3. Пусть ряд F(s) сходится в некоторой точке so,
|so| = г. Тогда последовательность коэффициентов этого ряда ра-
растет медленнее, чем (? + е)" для любого положительного числа е.
Следствие 4.4. Если ряд сходится на всей плоскости, то последо-
последовательность его коэффициентов растет медленнее, чем еп, для лю-
любого положительного числа е.
С каждым степенным рядом (с числовыми — целыми, вещественны-
вещественными или комплексными коэффициентами) можно связать его круг сходи-
сходимости. Круг сходимости ряда — это наибольший открытый (не содер-
содержащий границы) круг на комплексной плоскости с центром в начале
координат, в каждой точке которого ряд сходится. Круг сходимости
может быть пустым, совпадать со всей плоскостью или иметь нену-
ненулевой конечный радиус R. В последнем случае справедливо следующее
полезное предложение.
Предложение 4.5. Радиус сходимости ряда F(s) равен модулю бли-
ближайшей к началу координат особой точки функции F на комплексной
плоскости.
Не давая строгого определения особой точки функции, приведем
лучше несколько поясняющих примеров.
Пример 4.6. Рассмотрим производящую функцию для чисел Фибо-
Фибоначчи Fib(s) = 1_g1_a? (см. уравнение B.6)). Ее особенности — это те
значения переменной s, для которых знаменатель дроби обращается в
нуль, т.е. корни знаменателя si = (—1-Ьл/5)/2, s2 = (-l-\/5)/2. Точка
51 ближе к началу координат, чем точка s2. Поэтому радиус сходимо-
сходимости ряда Фибоначчи равен
-«Fib =
Из теоремы 4.3 теперь немедленно вытекает, что числа Фибоначчи
растут медленнее, чем ( ^+1 +?] для любого е > 0. Формула B.7)
позволяет сделать и более точное утверждение. На самом деле, числа
4.2. Асимптотика гипергеомбтрических последовательностей 51
Фибоначчи растут, как 4= ( -^ ) • Действительно, из B.7) имеем
п+1
= 1 + сп
— -1 + с i
где с =
< 1. Ясно, что сп стремится к нулю при п —> ос.
Пример 4.7. Производящая функция для чисел Каталана имеет вид
(см. уравнение B.14))
Cat(s) =
2s
Корень знаменателя s = 0 не является ее особенностью, так как при
s = 0 числитель дроби также обращается в нуль. Единственная особен-
особенность этой функции отвечает обращению в нуль подкоренного выраже-
выражения, т.е. значению s = |. Поэтому числа Каталана растут медленнее,
чем D+е)" для любого е > 0. Более точные сведения об их асимптотике
мы получим ниже.
4.2. Асимптотика гипергеометрических
последовательностей
В перечислительных задачах очень часто встречаются последова-
последовательности, отношение соседних членов которых равно отношению двух
многочленов одинаковой степени. Для геометрической прогрессии, на-
например, это отношение просто равно константе. Если же степени мно-
многочленов больше нуля, то соответствующую последовательность назы-
называют гипергеометрической. Очень хорошее описание асимптотики ги-
гипергеометрических последовательностей дает следующая лемма.
Лемма 4.8. Пусть последовательность ао, а\,
чисел такова, что
положительных
an
для всех достаточно больших п, причем а\ ф /3i. Тогда ап растет как
an~cAnnQ1-01 D.2)
для некоторой постоянной с > 0.
52 Глава 4. Асимптотика коэффициентов
Замечание 4.9. Предположения леммы не позволяют определить ве-
величину константы с. Действительно, умножив последовательность о„
на произвольную постоянную d > О, мы получим новую последователь-
последовательность с тем же отношением последовательных членов, константа с для
которой увеличивается в d раз.
Пример 4.10. Для чисел Каталана имеем (см. B.16))
Сп+1 _ _ 4
сп п +2 п + 2'
Поэтому с„ ~ с • 4" • п~3/2 для некоторой постоянной с.
Пример 4.11. Найдем асимптотику коэффициентов для функции
(o-s)a, где а вещественно. В ряде случаев эта асимптотика нам уже из-
известна, например, при a = — 1. Согласно определению функции A - s)a
имеем
(l)a = D.3)
Если a — целое неотрицательное число, то ряд обрывается и вопроса об
асимптотике не возникает. В противном случае начиная с некоторого
номера все коэффициенты ряда D.3) имеют одинаковый знак. Для опре-
определения асимптотики мы можем воспользоваться предыдущей леммой
2s±L = I»^? D.4)
an a n +1
Поэтому ап ~ с ¦ a~n • n~a~i. Например, коэффициенты функции
—A — 4sI/2 ведут себя как с • 4" ¦ га~3/2, и мы получаем повторный
вывод асимптотики для чисел Каталана.
Доказательство леммы. Утверждение леммы эквивалентно тому, что
существует предел
lim ^-г-
п—юо А п Р1
Прологарифмировав, мы приходим к необходимости доказать суще-
существование предела
lim Aпа„ - п1пЛ - (ai-/?i)lnn). D.5)
4.2. Асимптотика гипергеометрических последовательностей 53
Для доказательства существования предела D.5) применим критерий
Коши, т.е. будем доказывать, что рассматриваемая последователь-
последовательность фундаментальна. Фундаментальность последовательности озна-
означает, что для любого е > О существует такой номер N, что для всех
п> N и всех положительных т
| Inan+m-lnan-(n+m) In A+nIn A-{a\-ft) ln(n+m)+(ai-ft) Inn\ < e,
или
| In an+m - In an - m In A - (c*i - ft) ln(n + m) + (ai - ft) In n\ < e. D.6)
Перепишем отношение ^^ в виде
Дп+i _ A k
an 1 + /Зхи + ... + /?*«"
где
= l + axx + ...+а.х
Прологарифмировав D.7), получаем
Q) D.9)
Посмотрим на функцию In f(x). Выпишем начальные члены разложения
функции /, определенной формулой D.8), в ряд в точке 0:
для некоторой константы 7- Это разложение — самый существенный
элемент доказательства. Именно коэффициент ai — ft (отличный от
нуля по предположению теоремы) при линейном члене указывает на
присутствие сомножителя nai~®1 в асимптотике. Для логарифма фун-
функции / имеем
1п/(аг) = (ai - ft)ar + >yx2 + ...
Поэтому для некоторой постоянной С при достаточно маленьком х име-
имеем | In f(x) — (ai - ft )x\ < Сх2. В частности, если N достаточно велико,
54
Глава 4. Асимптотика коэффициентов
то Vn > N
lnon+i -lnan-lnA-
lnan+2 - 1па„+1 - In Л - (ai -
h)^+l
<c-
<c
D.10)
lnan+m - lnon+m_i - In A - (c*i -
1
n + m
<C
(n + mf'
Теперь интересующее нас выражение в левой части неравенства D.6)
можно оценить с помощью системы D.10) и неравенства треугольника:
|lnan+m — \па„ — тп1пЛ — (c*i — /3i)(ln(n + m) — \пп)\ =
= |lnon+m -lnan+m_i +lnan+m_i -... + lnan+i -lnan-
*=o
*=o
-(ai - /?i)(ln(n + m) - In n)|<
lnan+i — In an — In A — (a\ — /?i
lnan+2 - lnan+i - lnA - (ai - ,
n
lnan+m - lnan+m_i - In A -
1
'n + m
m-l
fc=0
Inn
С [A:
m-l
fc=0
D.11)
Поскольку ряд ^Z^j I/A;2 сходится, первое слагаемое в правой ча-
части последнего неравенства при больших п можно сделать сколь угодно
малым. Чтобы оценить второе слагаемое, заметим, что стоящая в нем
сумма представляет собой площадь под графиком ступенчатой функ-
функции щ на отрезке [п, п + т], см. рис. 4.1. (Здесь через [х] обозначена
4.3. Асимптотика и уравнение Лагранжа
55
п
п + тп
Рис. 4.1. График функции у = т—г на отрезке [п, п + тп]
целая часть числа х, наибольшее целое число, не превосходящее х.) Эта
площадь больше, чем площадь под графиком функции у = ^, но мень-
меньше, чем площадь под графиком функции у = ^^у на этом же отрезке.
Площадь под графиком функции у = j равна 1п(га + тп) — In n, пло-
площадь под графиком функции j^j равна ln(ra + m - 1) — ln(n — 1). Таким
образом, интересующая нас разность не превосходит
m - 1) - ln(n - 1)) - (-l
m) + lnn)| =
n
Доказательство леммы завершено.
4.3. Асимптотика коэффициентов функций, связанных
между собой уравнением Лагранжа
Пусть производящие функции <р = <p(s) и ip = ip(t) связаны между
собой уравнением Лагранжа (см. C.7))
tp(s) =
D.12)
Мы хотим выяснить, как связаны между собой их радиусы сходимо-
сходимости. На первый взгляд никакой связи нет. Действительно, мы видели
в примере 3.7, что если %l>(t) = 1 + t2 — производящая функция для
подъязыка неприводимых слов в языке Дика, то y>(s) — производя-
производящая функция для самого языка Дика, умноженная на s. При этом если
56 Глава 4. Асимптотика коэффициентов
первая функция является многочленом и сходится на всей плоскости,
то вторая имеет своим радиусом сходимости ^. Аналогичная картина
наблюдается и для любых языков, задаваемых контекстно свободны-
свободными грамматиками с конечным числом правил вывода и однозначным
выводом.
Ситуация, однако, разительно меняется, если число правил вывода
в языке (число неразложимых слов) бесконечно.
Теорема 4.12. Пусть две производящие функции ip = tp(s) и ф =
= ip(t), ф@) = 1 с неотрицательными коэффициентами связаны меж-
между собой уравнением Лагранжа D.12). Пусть г > 0 — радиус сходи-
сходимости ряда if, причем числовой ряд ip(r) сходится. Тогда радиус схо-
сходимости ряда ф не меньше р = <р(г). Если числовой ряд tp'(r) также
сходится, то радиус сходимости ряда ф равен р = <р(г).
Замечание 4.13. Требование неотрицательности коэффициентов ря-
рядов естественно, если мы рассматриваем производящие функции для
языков. В этом случае естественно также ожидать, что радиус сходи-
сходимости производящего ряда для числа неприводимых слов больше ради-
радиуса сходимости производящего ряда для числа всех слов в языке (по-
(последняя последовательность растет быстрее последовательности чисел
неприводимых слов).
Доказательство. Докажем, что ряд ^(s) сходится абсолютно в лю-
любой точке s, \s\ = q < р. Поскольку функция <р монотонна и непрерывна
на отрезке [0, г], существует точка р € [0, г], такая что <р(р) = q. Поэто-
Поэтому для любой частичной суммы ф№(s) =фо + ф\8 +.. . + фпзп рядаip(s)
где последнее неравенство следует из предыдущего замечания.
Первое утверждение теоремы доказано.
Перепишем теперь уравнение Лагранжа D.12) в виде
Функции ф(Х) и у (А) определены и голоморфны внутри круга ради-
радиуса р. Теорема будет доказана, если мы покажем что функцию f~1{X)
нельзя продолжить голоморфно ни в какую окрестность точки р. Пред-
Предположим, что такое продолжение существует. Тогда
t—»i—О
4.4. Асимптотика и характер особенностей 57
Последний предел существует и, по условию теоремы, положителен. По-
Поэтому функция цГх обратима в окрестности точки р, что, в свою оче-
очередь, противоречит условиям теоремы.
Отметим, что производящий ряд для чисел Каталана Cat(s) схо-
сходится при s = г — \, так как числа Каталана имеют асимптотику
4" • п~3/2, а ряд ^п~312 сходится. С другой стороны, коэффициенты
производной имеют асимптотику 4" • п/2, и поэтому ряд Cat'(\) рас-
расходится. В результате теорема в полном объеме к функции Каталана
неприменима, а второе утверждение оказывается неверным.
4.4. Асимптотика коэффициентов производящего ряда
и характер особенности на границе круга сходимости
Мы уже видели, что радиус сходимости производящего ряда определяет-
определяется расположением ближайшей к началу координат особой точки этого ряда.
В ситуации, когда радиус сходимости конечен (отличен от нуля и от бес-
бесконечности), асимптотика коэффициентов ряда тесно связана с характером
особенности на границе круга сходимости.
Простейший вид особенности — это полюс, особенность вида A — з/а)~
при натуральном к. Как мы уже видели, такие (и только такие) особенности
встречаются у рациональных функций. Коэффициенты производящей функ-
функции с такой особенностью имеют асимптотику пк~хап.
Более сложными оказываются алгебраические и алгебро-логарифмичес-
кие особенности.
Определение 4.14. Особая точка s = А называется алгебро-логарифмичес-
кой особой точкой функции f(s), если в некоторой окрестности точки А
функция / может быть представлена в виде суммы конечного числа функций
вида
(s-A)-a\nk(s-A)ip(s), D.13)
где а — комплексное число, к — целое неотрицательное число, а функция <р
не имеет особенностей в точке А и ц>{А) ф 0.
Коэффициенты ряда D.13) имеют следующую асимптотику:
const- ЛппЕеа-11п'сп при а # 0, -1, -2, ...
const ¦Anna-1 In* п при а = 0, -1, -2, ... (" '
В разделе 3.4 было установлено, что формальные грамматики с однознач-
однозначным выводом естественно приводят к алгебраическим производящим функ-
функциям. Произведение Адамара рациональных функций рационально (см. тео-
теорему 2.4). Аналогичное утверждение справедливо и для произведения Ада-
Адамара рациональной и алгебраической функции.
58 Глава 4. Асимптотика коэффициентов
Теорема 4.15. Если функции f(s) рациональна, a g(s) — алгебраическая,
то их произведение Адамара — алгебраическая функция.
Однако сами по себе алгебраические производящие функции, в отличие
от рациональных, не замкнуты относительно произведения Адамара. Напри-
Например, квадрат Адамара функции A — s)'1^2 (и, вообще, произведение Ада-
Адамара функций вида A — s)~a) — неалгебраическая функция. Замкнуты-
Замкнутыми относительно цроизведения Адамара оказываются функции с алгебро-
логарифмическими особенностями. Точнее, справедлива следующая теорема.
Теорема 4.16. Если функции f(s) и g(s) имеют на границе круга сходимо-
сходимости только алгебро-логарифмические особенности, то это оке справедливо
и для их произведения Адамара. При этом радиус сходимости произведенил
равен произведению радиусов сходимости функций fug.
Еще один важный результат о произведении Адамара был получен Гур-
вицем.
Теорема 4.17 (Гурвиц). Если функции f, g являются решениями однород-
однородных дифференциальных уравнений с полиномиальными коэффициентами, то
таким же свойством обладает и их произведение Адамара.
4.5. Задачи
4.1. Найдите асимптотику чисел Моцкина (см. задачу 2.9).
4.2. Найдите асимптотику для числа слов в языке Дика (задача 3.4)
а) второго; б) произвольного порядка.
4.3. Найдите асимптотику для числа путей длины к из задач 2.11,
2.12.
4.4. Найдите асимптотику числа слов в языках из задач 3.9, 3.11.
4.5. Рассмотрим на горизонтальной прямой точки 1, 2, ..., 2п и со-
соединим их попарно набором из п попарно непересекающихся полу-
полуокружностей в верхней полуплоскости и га попарно непересекающих-
непересекающихся полуокружностей в нижней полуплоскости. Полученная картинка
называется системой меандров порядка га. Найдите асимптотику для
числа систем меандров.
Систему меандров можно закодировать словом длины 2га в алфавите
из четырех букв {а, Ь, с, d}, сопоставив каждой из точек 1, ..., 2п одну
из букв по следующему правилу:
4.5. Задачи 59
(Картинка изображает поведение верхней и нижней полуокружно-
полуокружностей, проходящих через выбранную точку.) Найдите асимптотику для
числа неразложимых систем меандров (т. е. для числа неразложимых
слов в языке систем меандров).
4.6. Докажите формулу Стирлинга
п!~с-пп+1/2е-".
4.7. Докажите, что квадрат Адамара производящей функции для
чисел Каталана не является алгебраической функцией.
4.8. Обозначим через а* число способов уложить прямоугольник
3 х 2к костями домино размером 1x2 так, чтобы они не перекры-
перекрывались. Например, ai = 3, a2 = 11. Найдите асимптотику чисел а*
и производящую функцию для них.
Глава 5
Производящие функции нескольких
переменных
Производящие функции от двух переменных отвечают двухиндекс-
ным последовательностям. Такие последовательности удобно записы-
записывать в виде треугольника (соответствующего положительному ква-
квадранту целочисленной решетки).
5.1. Треугольник Паскаля
Треугольник Паскаля изображен на рис. 5.1. Элементы этого тре-
треугольника перечисляют пути, идущие из его вершины в соответствую-
соответствующую клетку. Пути имеют вид ломаных, составленных из векторов еди-
единичной длины двух видов: идущих вправо-вниз и идущих влево-вниз.
б)
со,о
Cl,0
С2,0
СЗ,0 С3,1
\ ,о
С2,2
с4,0 С4,1
ч
С3C
Сз,о
С5,2 С5,3 С5,4 С5,5
в)
Ci ,2 Со,з
2 С\?
С2K С1,4
г)
Рис. 5.1. Треугольник Паскаля и пути, которые он перечисляет
5.1. Треугольник Паскаля ' 61
Числа, стоящие в треугольнике Паскаля, — это уже хорошо знако-
знакомые нам биномиальные коэффициенты
C"'fc = (*
Это несложно доказать индукцией по п. Предположим, что числа
в n-й строчке треугольника совпадают с коэффициентами разложения
многочлена (l + s)n. Число различных путей, ведущих в точку (п + 1, к),
равно сумме числа путей, ведущих в точку (п, к - 1), и числа путей,
ведущих в точку (п, к), cn+i)fc = cn^-i + с„,*. Поэтому число cn+1,fc
совпадает с коэффициентом при sk в многочлене A + s) • A + s)n =
Производящая функция может быть сопоставлена треугольнику Па-
Паскаля несколькими способами. Например, можно рассмотреть произво-
производящую функцию
n,fc=O
Второй способ соответствует нумерации элементов треугольника
числом отрезков каждого типа на путях, ведущих в соответствующую
точку (рис. 5.1 г)). Для этой нумерации
п + т
т
и производящая функция имеет вид
n,m=O
-±
к=Оп+т=к
оо
fc=O
На этот раз она оказалась симметричной по переменным х и у.
62 Глава 5. Функции нескольких переменных
И, наконец, имеется еще один способ: сопоставить треугольнику
Паскаля экспоненциальную производящую функцию. Экспоненциаль-
Экспоненциальная производящая функция отличается от обычной тем, что в качестве
коэффициентов степенного ряда берутся не элементы последовательно-
последовательности ап, а числа ап/п\.
5.2. Экспоненциальные производящие функции
Зафиксируем произвольную последовательность {ап}. Каждой по-
последовательности {ап} мьг можем сопоставить производящую функцию
{а„} »->
71=0
определяемую последовательностью {а„}. Если в последовательности
{ап} отсутствуют нулевые элементы, то такое сопоставление взаимно
однозначно. До сих пор мы пользовались только обычными производя-
производящими функциями — отвечающими последовательности ап = 1. В зави-
зависимости от преследуемых целей пользу могут принести и другие после-
последовательности. Чаще всего используется последовательность ап = ^.
Соответствующие ей производящие функции называются экспоненци-
экспоненциальными.
Экспоненциальные производящие функции для целочисленных по-
последовательностей называются функциями Гурвица.
Чем отличаются экспоненциальные производящие функции от обыч-
обычных? Посмотрим на поведение экспоненциальных производящих функ-
функций при выполнении операций над ними. Сумма ведет себя обычным
образом:
оо оо оо
Ьпп = у
71=0
а вот произведение иначе:
п=0 71=0 п=0
~ 0! 0! \ 0! 1! 1! О! / Ч 0! 2! 1! IT + 2f 0!
Коэффициенты ^ произведения вычисляются по формуле
/¦пл
Сп =
5.3. Треугольник Дика 63
Еще одно существенное отличие экспоненциальных производящих
функций от обычных наблюдается при взятии производных (и инте-
интегрировании). Дифференцирование или интегрирование экспоненциаль-
экспоненциальной производящей функции приводит к сдвигу последовательности ее
коэффициентов без изменения их величины:
Ж
Обычная производящая функция A(s) = а0 + a^s + a2s2 + ... выра-
выражается через экспоненциальную A{t) = ^ + ^ft + Щ12 +... по формуле
оо
A(s) = I e-lA{st)dt.
о
Действительно,
jfc!= (e-Hkdt.
о
Теперь мы можем выписать экспоненциальную производящую фун-
функцию для треугольника Паскаля:
xnym = У vx 7 = ex+v.
(n + m)\\ m * ^ n\
n,m=O ч ' n=0
Несколько более сложных примеров экспоненциальных производя-
производящих функций будут обсуждаться ниже.
5.3. Треугольник Дика
Треугольник Дика перечисляет пути в положительном квадранте
плоскости, выходящие из начала координат и составленные из векторов
A, 1) и A, —1) (см. рис. 5.2). Пути, оканчивающиеся на оси абсцисс, —
это пути Дика из раздела 2.5.
Нетрудно видеть, что элементы dy треугольника Дика отличны
от нуля в том и только в том случае, если i ^ j и i + j четно. Обо-
Обозначим через D(x, у) производящую функцию Дика двух переменных
D(x, y)=
• J=0
64
Глава 5. Функции нескольких переменных
^4,4
а) б)
Рис. 5.2. Треугольник Дика
3
d'2,2 ^4,2 ,2
/
Правило построения треугольника Дика подсказывает нам уравне-
уравнение на эту производящую функцию
xyD(x, у) + (D(x, у) - D(x, 0))- = D(x, у) - 1.
У
Действительно, коэффициент при любом мономе x'yi, отличном от
единичного, представляет собой сумму коэффициентов при мономах
х'~1у%~1 и x'~ly*+l. Функция
D(x, 0) =
нам хорошо известна, и ряд D(x, у) находится решением линейного
уравнения,
D{Xt у) =
V 'У> 2х(ху2+х-у)
5.4. Треугольник Бернулли-Эйлера и перечисление змей
Треугольник Бернулли - Эйлера (см. рис. 5.3), как и треугольник Па-
Паскаля, обладает многими замечательными свойствами. Левая сторона
этого треугольника называется стороной Бернулли, правая — сторо-
стороной Эйлера 1К
Элементы треугольника Бернулли - Эйлера -— тоже числа путей из
вершины треугольника в данную клетку. Но при этом рассматрива-
рассматриваются только пути, идущие зигзагом: нечетные шаги влево, четные -¦-
''Отметим, что есть еще две последовательности чисел, которые также носят
имена Бернулли и Эйлера.
5.4. Треугольник Бернулли-Эйлера
65
A6) A
а)
в)
Рис. 5.3. Треугольник Бернулли - Эйлера и пути, которые он перечисляет
66 Глава 5. Функции нескольких переменных
nik = 6еп-1,Л-1 +ben<k-i
Рис. 5.4. Альтернированный треугольник Бернулли - Эйлера
вправо. Поэтому каждое число в треугольнике Бернулли - Эйлера рав-
равно сумме чисел предыдущей строки, стоящих слева или справа от него,
в зависимости от четности строки.
Можно дать и более простое индуктивное правило определения чи-
чисел в треугольнике Бернулли-Эйлера, если чередовать знаки через ка-
каждые две строчки (см. рис. 5.4). В таком альтернированном треуголь-
треугольнике каждый элемент равен сумме двух ближайших элементов, стоящих
справа и справа сверху от него. Для того чтобы однозначно задать
треугольник, необходимо доопределить сторону Эйлера, чем мы сей-
сейчас и займемся. Нам понадобятся еще две интерпретации треугольни-
треугольника Бернулли - Эйлера — в терминах морсовских многочленов и up-down
перестановок.
Определение 5.1. Точка а:о называется критической точкой много-
многочлена р = р(х), если она является корнем его производной, р'(а:о) = 0.
Касательная к графику многочлена в критической точке горизонталь-
горизонтальна. Значение р(хо) многочлена р в критической точке называется кри-
критическим значением этого многочлена. Многочлен р называется мор-
совским, если
а) все его критические точки вещественны и различны;
б) все его критические значения различны.
Морсовский многочлен степени п + 1 имеет п критических точек и
п критических значений. Мы будем рассматривать многочлены вида
р(а:)=а:"+1+о1а:п + ...+о„+1, E.1)
старший коэффициент которых равен 1.
5.4. Треугольник Бернулли - Эйлера
67
Рис. 5.5. Перестановка, соответствующая морсовскому многочлену
Каждому морсовскому многочлену можно сопоставить перестанов-
перестановку на множестве из п элементов. Эта перестановка указывает порядок,
в котором идут критические значения многочлена. Для построения пе-
перестановки перенумеруем критические точки и критические значения
многочлена в порядке возрастания. На г-м месте в определяемой пере-
перестановке стоит номер критического значения в г-й критической точке
(см. рис. 5.5). Ясно, что каждый элемент такой перестановки либо боль-
больше обоих своих соседей (отвечающее ему критическое значение явля-
является локальным максимумом), либо меньше их (соответственно, крити-
критическое значение является локальным минимумом). Такие перестановки
называются пилообразными, или up-down перестановками. Пилообраз-
Пилообразную перестановку, отвечающую морсовскому многочлену, назовем ти-
типом этого многочлена.
Заметим, что не любая пилообразная перестановка может служить
типом морсовского многочлена вида E.1): последний элемент в ней дол-
должен быть меньше своего левого соседа. Как результат, при п нечетном
первый элемент в перестановке должен быть меньше, а при п четном —
больше своего правого соседа.
Типы морсовских многочленов при малых значениях п изображе-
изображены на рис. 5.6. При п = 1 и п = 2 имеется ровно одна возможность.
При п = 3 имеется 2 возможности, при п = 4 таких возможностей 5.
68
71=1
Глава 5. Функции нескольких переменных
п=2
A)
B1)
A32)
B31)
B143)
C142)
C241)
D132)
D231)
Рис. 5.6. Типы морсовских многочленов при п = 1, 2, 3, 4
Если продолжить перечисление, то можно получить последователь-
последовательность
1, 1,2,5,16,61,272, ...
Элементы этой последовательности, отвечаюшие нечетным значени-
значениям п, совпадают с последовательностью ненулевых элементов сторо-
стороны Бернулли, а подпоследовательность элементов с четными номерами
совпадает с ненулевой частью стороны Эйлера.
Чтобы понять, откуда берется связь с треугольником Бернулли-
Эйлера, рассмотрим типы морсовских многочленов, у которых первое
критическое значение имеет номер к.
Лемма 5.2. Пусть cn,k — число типов морсовских многочленов
степени п+1, у которых первое критическое значение имеет номер к.
Тогда сп^ есть к-е число в п-й строке треугольника Бернулли - Эй-
Эйлера.
Доказательство. Для первых двух строк треугольника утвержде-
утверждение проверяется непосредственно. Докажем, что если оно верно для п-й
строки, то оно верно и для строки с номером п + 1. Пусть, для опре-
определенности, п + 1 четно. Тогда п и п + 2 нечетны; мы изучаем типы
многочленов степени п + 2. Первое критическое значение в таком мно-
многочлене является максимумом, второе — минимумом, поэтому второе
критическое значение меньше первого.
Отбрасывание первого критического значения многочлена дает од-
однозначно определенный тип Морсовского многочлена степени п+1.
5.4. Треугольник Бернулли- Эйлера 69
Первое критическое значение у такого многочлена может быть к-м,
к + 1-м, ..., n-м по величине. Наоборот, по каждому типу многочле-
многочлена степени п + 1, у которого первое критическое значение является
1-м по величине (/ ^ к), мы можем единственным образом построить
тип многочлена степени п + 2, у которого первое критическое значение
является &-м по величине. Таким образом,
Cn + l,fc = Cn<k + Cn,fc+i + . - . + С„,„.
Для строки с нечетным номером справедливо аналогичное рассуждение.
Тем самым, числа с,,,* удовлетворяют тем же соотношениям, что и эле-
элементы треугольника Бернулли - Эйлера, а значит, именно они и стоят
в этом треугольнике.
Рассмотрим по отдельности два случая:
> п нечетно; соответствующее число up-down перестановок обозна-
обозначим через Ьп и введем экспоненциальную производящую функцию
B(x) = ^+|x» + ...= ix + lx» + |fx» + ...;
> п четно; соответствующее число up-down перестановок обозначим
через е„ и введем экспоненциальную производящую функцию
Выведем рекуррентную формулу для числа up-down перестановок.
Для этого возьмем самый высокий максимум многочлена и унесем его
в бесконечность (см. рис. 5.7). В результате мы сопоставили каждому
типу многочлена два новых типа, причем если изначально имелась п +1
критическая точка, то получились многочлены с кип —к критическими
точками, п — к нечетно.
При нечетном п получаем рекуррентное соотношение на числа Ьп:
ьп+1= J2 (пк)ЬкЬп-к- E-2)
к нечетно ^ '
Биномиальный коэффициент возникает из-за того, что мы должны пе-
перемешать множество критических значений левого и правого многочле-
многочлена, т. е. выбрать из п критических значений те, которые принимаются
левым многочленом.
70
Глава 5. Функции нескольких переменных
Рис. 5.7. Сопоставление типу многочлена двух новых типов
Вспоминая, что для экспоненциальных производящих функций пра-
правая часть соответствует квадрату производящей функции В(х), а ле-
левая — ее же производной, перепишем уравнение E.2) в виде
В'(х) = В2(х)
E.3)
Последнее уравнение представляет собой обыкновенное дифференци-
дифференциальное уравнение с разделяющимися переменными. Решая его, полу-
получаем
dB = (В2 + 1) dx,
arctg В = х,
В(х) = Щх.
Таким образом, сторона Бернулли определяет разложение в ряд тан-
тангенса:
(х) = tg х = х
^ + 272^
Коэффициенты bn в разложении тангенса называются тангенциальны-
тангенциальными числами. Обратите внимание на то, что единица в вершине тре-
треугольника не включается в сторону Бернулли.
Если же п четно, то рекуррентное соотношение принимает вид
E.4)
E-5)
е„+1 = 2^
к нечетно
и ему соответствует уравнение
?'{у) = ?{у)В{у).
5.4. Треугольник Бернулли-Эйлера 71
на производящие функции. Решая последнее уравнение, получаем
(\n?(y))'=tgy,
\п?(у) = / tgy,
?Ы = ^'
и сторона Эйлера определяет разложение в ряд секанса. Коэффициенты
еп этого разложения называются числами Эйлера 2).
Воспользовавшись подстановкой
sinx = (eix - e~ix) /2г, cosx = (eix + e~ix) /2,
мы можем переписать производящие функции сторон для альтерниро-
альтернированного треугольника в виде
Теперь у нас есть все необходимое для вычисления экспоненциаль-
экспоненциальной производящей функции альтернированного треугольника Бернул-
Бернулли-Эйлера. Обозначим через Ье^ элемент треугольника, имеющий ко-
координату к вдоль стороны Бернулли и координату I вдоль стороны
Эйлера.
Теорема 5.3. Экспоненциальная производящая функция для альтер-
альтернированного треугольника Бернулли - Эйлера имеет вид
оо к I х
В?(х, y)=Y, beM frTT = г+у 2е-(х+у)- E-6)
Доказательство. Докажем, что экспоненциальная производящая
функция для треугольника Бернулли-Эйлера удовлетворяет диффе-
дифференциальному уравнению
с, у)
2'Обычно числами Эйлера называют числа, стоящие на стороне Эйлера в альтер-
альтернированном треугольнике (т.е. числа, знак которых меняется). Мы, однако, позво-
позволим себе не проводить различия между этими двумя последовательностями.
72 Глава 5. Функции нескольких переменных
Записанное выше равенство есть не что иное, как правило образо-
образования альтернированного треугольника. Действительно, рассмотрим
прямую в треугольнике, параллельную стороне Эйлера. Дифференциро-
Дифференцирование по у экспоненциальной производящей функции этой прямой есть
сдвиг на единицу вдоль стороны Эйлера. Суммируя результат диффе-
дифференцирования с исходной функцией, мы получаем соседнюю прямую
(так как befc,m = befc_i,m + befc_i,m+i), т.е. результат дифференциро-
дифференцирования по х исходной экспоненциальной производящей функции.
Таким образом, функция BS{x, у) однозначно определяется своим
начальным значением
В?@, у) = ?(у) =
еу+е~у
и дифференциальным уравнением. Для доказательства теоремы оста-
осталось только проверить, что функция E.6) удовлетворяет выписанному
дифференциальному уравнению.
5.5. Представления производящих функций в виде
непрерывных дробей
Производящая функция для чисел Каталана удовлетворяет квадрат-
квадратному уравнению B.13)
s2Cat2(s)-Cat(s) + l = 0.
Перепишем это уравнение в виде
Cat(s)-s2Cat2(s) = 1,
или
Cat(s) = rr?kw- E-7)
Подставив выражение для Cat(s) из левой части равенства E.7) в
правую часть того же равенства, получим
Cat(a) = Ц .
1 ?—
1 - s2 Cat(s)
Подставляя вновь выражение E.7) для Cat(s) в получившееся равенство
и продолжая этот процесс, мы получаем представление для функции
5.5. Непрерывные дроби 73
Каталана в виде непрерывной дроби:
Cat(s) = Ц . E.8)
1
Полученное разложение нужно понимать следующим образом. Если мы
оборвем непрерывную дробь на n-м шаге (оставив вместо нее конеч-
конечную непрерывную дробь, которая представляет собой рациональную
функцию), то коэффициенты разложения полученной функции по сте-
степеням s будут совпадать с коэффициентами разложения функции Cat(s)
вплоть до члена s2n. Заметим, что из-за наличия множителя s2 в числи-
числителе очередной дроби, присоединяемой на (п + 1)-м шаге, увеличение
числа членов в непрерывной дроби не приводит к изменению первых п
коэффициентов в ее разложении. Например,
= 1 + s2 + s4 + s6 + s8 + ...,
= 1 + s2 + 2s4 + 4s6 + 8s8 + ...,
= 1 + s2 + 2s4 + 5se + 13s8 + ...,
= 1 + s2 + 2s4 + 5se + 14s8 + ...
1-
1-
1-
1
1
1
1
1
1
1
1
s2
1
s2
s2
~ 1
1
— s
s2
-s2
!
s2
-s2
sL_
— s
Стабилизирующаяся часть разложения выделена.
Представление функции Каталана в виде непрерывной дроби тес-
тесно связано с двумя способами ее получения — перечислением путей по
треугольнику Дика (раздел 2.5) и с помощью производящей граммати-
грамматики (раздел 3.2). Подобное представление можно распространить и на
другие функции, перечисляющие различные пути.
Изменим несколько треугольник Дика (рис. 5.1), поставив на стрел-
стрелках числа. А именно, поставим на каждой стрелке номер того ряда,
в котором она находится (см. рис. 5.8 а)). Номер на стрелке мы будем
интерпретировать как ее кратность, т. е. как число различных стрелок,
74
Глава 5. Функции нескольких переменных
а) б)
Рис. 5.8. Треугольник Дика с кратностями
проходящих в данном направлении. В результате одному пути в тре-
треугольнике Дика отвечает несколько «различных» путей в треугольнике
с кратностями. Их число равно произведению кратностей всех ребер,
входящих в данный путь.
Числа, стоящие в нижней строке треугольника (рис. 5.8 а)), напо-
напоминают уже хорошо нам известную последовательность чисел Эйлера
из раздела 5.4. Сейчас мы построим непрерывную дробь, отвечающую
этому треугольнику, а доказательство того, что в его основании дей-
действительно лежат числа Эйлера, отложим до следующего раздела.
Теорема 5.4. Производящая функция
F0(s) = 1 + s2 + 5s4 + 61s6 + 1385s8 + ...
для нижней стороны треугольника с рис. 5.8 а) представляется в виде
непрерывной дроби
вд = ^
X ~~
1-
1-
о2 2
О О
Доказательство. Производящая функция Fo(s) перечисляет раз-
различные пути с началом и концом на высоте 0. Обозначим через Fj(s)
производящую функцию, перечисляющую пути с началом и концом на
высоте г, которые не опускаются ниже уровня i, по их длине. Тогда
5.5. Непрерывные дроби 75
Действительно, каждый путь с началом и концом на высоте 0 един-
единственным образом разбивается на такие участки, что
1) концы пути на каждом участке лежат на высоте 0;
2) высота всех промежуточных точек пути на каждом участке боль-
больше нуля.
Если отбросить начальный и конечный отрезок такого участка,
то мы получим путь, начинающийся и заканчивающийся на высоте 1.
Аналогично,
Fi{s) = \ .
l-4s2F2(s)
Появление четверки в коэффициенте при s2 объясняется тем, что к дан-
данному пути, начало и конец которого лежат на высоте 2, начальный и
конечный векторы, превращающие его в путь на высоте 1, можно до-
добавить четырьмя «различными» способами.
Продолжая это рассуждение, мы заключаем, что
ад =, \
и непрерывная дробь теперь выписывается очевидным образом:
F0{s) = 1 =
1
l-4s2F2(s)
1-
4*2
Из доказательства теоремы непосредственно вытекает, что распре-
распределение кратностеи по восходящему и нисходящему векторам пути в ка-
каждом слое не имеет значения. Необходимо лишь, чтобы произведение
этих кратностеи внутри каждого слоя было постоянным. Например,
треугольник, изображенный на рис. 5.9, порождает ту же производя-
производящую функцию для путей с нулевой высотой начала и конца, что и тре-
треугольник с рис. 5.8 а). Заметим, что то же справедливо и для путей на
других высотах.
76
Гллвл 5. Функции нескольких переменных
Рис. 5.9. Другая расстановка кратностей в треугольнике Дика
Cm-l,n+l
—1,п —*¦*-»»,?
а) б)
Рис. 5.10. Треугольник Моцкина с кратностями
Конечно, доказательство теоремы обобщается на произвольную рас-
расстановку кратностей. Более того, его можно без труда перенести и на
треугольник Моцкина (см. рис. 5.10).
Теорема 5.5. Пусть через оч, &, 7» обозначены кратности векто-
векторов A, 1), A, —1) и A, 0) соответственно в г-м слое взвешенного
треугольника Моцкина. Тогда производящая функция Fk(s) для путей
с началом и концом на высоте к, не опускающихся ниже этой высоты,
представляется в виде непрерывной дроби
Fk(8) =
Доказательство. Конечно, эта теорема доказывается так же, как
и ее частный случай теорема 5.4. Мы, однако, хотим изложить то же
5.5. Непрерывные дроби • 77
самое доказательство на языке формальных грамматик (глава 3). Со-
Сопоставим векторам A, 1), A, -1), A, 0) в г-м слое буквы a,, b,, ct со-
соответственно. Мы будем рассматривать языки То, Т\, ... в алфавите
из бесконечного набора букв {ао, bo, со,а\,Ь\, С\, ...,}. Язык Тк со-
состоит из слов, отвечающих путям с началом и концом на высоте А;, не
опускающимся ниже этой высоты.
Грамматика
го —> А,
го —>
го —>
п —>•
п —>
является грамматикой с однозначным выводом. Буква г*, А: = 0, 1, 2,
... порождает язык Тк- Поэтому некоммутативные производящие фун-
функции для языков Тк удовлетворяют соотношениям
То = А + соТо +
Подставляя Л = 1, а* = QjS, bi = fas, Cj = 7jS, получаем систему
уравнений на коммутативные производящие функции
F0(e) = 1 +7os^o(s) +ao0os2Fo(s)F1(s),
«) +a1p1s2F1{s)F2{s),
откуда
1
ВД =
1 - 70s - e0/3os2Fi (s)
1
i_70S
Вывод формул для остальных Fk аналогичен, и теорема доказана.
78 Глава 5. Функции нескольких переменных
5.6. Числа Эйлера в треугольнике с кратностями
Предложение 5.6. В основании треугольника на рис. 5.8 а) находят-
находятся числа Эйлера.
Доказательство. Мы будем доказывать, что число различных пу-
путей длины In в треугольнике Дика с кратностями равно числу пило-
пилообразных перестановок на множестве {1, ..., 2п — 1} или, что то же
самое, числу типов морсовских многочленов степени 2п. Присоединим
к множеству элементов перестановки дополнительный элемент 2п, счи-
считая его последним элементом каждой перестановки. (Напомним, что
мы рассматриваем только такие пилообразные перестановки, которые
остаются пилообразными при присоединении последним максимально-
максимального элемента.)
Сопоставим пилообразной перестановке путь в треугольнике Дика
по следующему правилу. Элемент i перестановки является либо (ло-
(локальным) максимумом, либо (локальным) минимумом в ней. Выберем
г-й отрезок пути идущим вверх, если элемент i перестановки является
минимумом, и идущим вниз в противном случае. На рис. 5.11 приведе-
приведены пилообразная перестановка и соответствующий ей путь. Ясно, что
получившийся путь действительно является путем Дика. В самом деле,
количество максимумов в пилообразной перестановке равно количеству
минимумов, и среди первых А; элементов I, ..., к не более половины
максимумов при любом к.
F,9,2,7,5,10,8,11,1,4,3,12)
1 2 3 4 5 6 7 8 9 10 11 12
Рис. 5.11. Путь Дика, отвечающий пилообразной перестановке
Выясним, сколько перестановок соответствуют данному пути.
Предположим, что путь, отвечающий первым т элементам перестанов-
перестановки, заканчивается на высоте к. И предположим также, что последний
элемент т является максимумом (т. е. последний вектор пути — спуск).
5.7. Сравнения 79
Каким может быть минимум, примыкающий к максимуму т справа?
Этот минимум лежит среди первых т — 1 элементов перестановки и его
можно выбрать к + 1 различными способами. Действительно, если за
каждым максимумом среди элементов 1, ..., т - 1 уже закреплен пар-
парный соседний справа минимум, то свободных минимумов осталось ров-
ровно А: + 1.
Рассуждение для случая, когда последний элемент т — минимум
проводится аналогично, только нужно выбирать соседний справа мак-
максимум и идти по перестановке справа налево, а не слева направо.
5.7. Сравнения в последовательностях
Этот раздел посвящен свойствам последовательностей целых чисел,
приведенных по различным модулям.
Рассмотрим, например, последовательность чисел Эйлера
1, 1,5,61, 1385,...
Остатки от деления элементов этой последовательности на 4 образуют
новую последовательность
1,1,1,1,1,...
Можно проверить, что и последующие члены этой последовательности
также будут единицами.
Та же самая последовательность, взятая по модулю 3, выглядит сле-
следующим образом:
1, 1,2, 1,2, 1,2, ...
Периодичность последовательности подсказывает нам, что она за-
задается рациональной производящей функцией. Действительно, пусть
N — длина периода последовательности at, т.е. од+лг — о* для всех
достаточно больших к. Тем самым, последовательность задается ли-
линейным рекуррентным соотношением и, согласно теореме 2.1, соответ-
соответствующая производящая функция рациональна.
В случае чисел Эйлера такую производящую функцию несложно
найти. Действительно, рассмотрим представление производящей фун-
функции для них в виде непрерывной дроби
E{s)=
1
1-
1-
2V
зУ
80 Глава 5. Функции нескольких переменных
При приведении последовательности по модулю 4 второй член этой дро-
дроби обращается в нуль, поэтому вся дробь принимает вид
Ei (s) = s- mod 4.
1 - s
(Два ряда с целыми коэффициентами сравнимы по какому-либо моду-
модулю, если по этому модулю сравнимы соответствующие коэффициенты
рядов.) При приведении по модулю 3 обращается в нуль третий член,
и дробь выглядит так:
¦i 1
E3(s) = 5— mod 3 = —-^ mod 3.
s 1 +
Вообще, при приведении последовательности чисел Эйлера по моду-
модулю р мы получаем конечную дробь
Ep(s) = Ц-5 modp,
1 ls .
так как коэффициент Р2 в следующем числителе сравним с нулем по мо-
модулю р и, тем самым, обращает в нуль весь хвост непрерывной дроби.
Ясно, как распространить это рассуждение на произвольную непрерыв-
непрерывную дробь.
Теорема 5.7. Пусть производящая функция A(s) представлена в ви-
виде непрерывной дроби
А(в)= 1
1 Ci
1-
-C2S -
pis2
P2S
1 -C3S -
2
P3S2
1 - ...
Тогда функция Ap(s) = A{s)iaodp рациональна для любого числа р,
являющегося делителем одного из произведений р\, р\р2, Р1Р2Р3, ¦¦¦
Если р делит произведение р\.. .pkt то
Ap(s) = —^5 mod p.
1 -C\S -
1 -Cfc_iS -Pk-l
5.7. Сравнения 81
Таким образом, теорема 5.7 позволяет найти представление в виде
рациональной производящей функции для последовательностей, отве-
отвечающих взвешенным треугольникам Дика, которые приведены по не-
некоторым (иногда даже по всем, как в случае чисел Эйлера) модулям.
Другой подход к изучению арифметических свойств элементов чи-
числовых последовательностей основан на использовании различных ком-
комбинаторных представлений для них. Вот простейший пример подобного
рассуждения. Число
Bп)!
n + l\nj (n + 1)\п\
является целым при любом п, однако непосредственно из формулы это
не очевидно. Мы знаем, впрочем, что это число равно числу правильных
скобочных структур из п пар скобок, и поэтому оно не может не быть
целым.
Представление чисел Каталана триангуляциями правильных (п+2)-
угольников позволяет доказать следующее утверждение.
Предложение 5.8. Если число п+2 является степенью простого
числа, п + 2 = рк и п > 1, то число Каталана с„ делится на р.
Например,
c2 = 2 = 0mod2; c5 = 42 = 0mod7; c7 = 429 = 0 mod 3.
Доказательство. Группа Zn+2 вычетов по модулю п + 2 действует
на множестве триангуляции правильного (п+2)-угольника поворотами.
При п > 1 у этого действия нет неподвижных точек. Поэтому длина
каждой его орбиты делится на р, а, значит, делится на р и число три-
триангуляции.
Аналогично, представление чисел Каталана правильными скобоч-
скобочными структурами дает еще одно свойство этих чисел.
Предложение 5.9. Если число п есть степень простого числа,
п — р*, то с„ = 2 mod р.
Например,
c2 = 2 = 2mod2; c3 = 5 = 2mod3; c5 = 42 = 2mod5.
Доказательство. Группа вычетов Z2n по модулю 2п действует на
множестве правильных скобочных структур из п пар скобок по следую-
следующему правилу. Образующая этой группы представляется циклическим
сдвигом на единицу. При таком сдвиге
82 Глава 5. Функции нескольких переменных
1) самая левая скобка стирается;
2) вместо нее в структуру добавляется самая правая скобка;
3) правая скобка, парная стертой самой левой скобке, заменяется на
левую скобку. Все остальные скобки не меняются. При п > 1 у этого
действия нет неподвижных точек.
Ровно одна орбита такого действия имеет длину 2. Она состоит
из скобочных структур
0(^_0 и
п пар скобок п — 1 пара скобок
Длины остальных орбит делятся на р, что и доказывает утверждение.
5.8. Решение обыкновенных дифференциальных
уравнении на производящие функции
При выводе производящих функций для сторон Бернулли и Эйле-
Эйлера треугольника Бернулли - Эйлера нам пришлось решать дифферен-
дифференциальные уравнения на эти функции. Оба эти уравнения E.3) и E.5)
принадлежат к одному классу обыкновенных дифференциальных урав-
уравнений, вопрос о существовании и единственности решения которых ре-
решается следующей теоремой.
Теорема 5.10. Рассмотрим обыкновенное дифференциальное урав-
уравнение
/'(«) = F(s, /(«)) E.9)
на производящую функцию f{s), где F — F(s, t) — производящая фун-
функция двух переменных, являющаяся многочленом по t (т. е. стпепеиь F
по t конечна). Тогда для каждого /о уравнение E.9) имеет единствен-
единственное решение, удовлетворяющее условию /@) = /о-
Для уравнения E.3) функция F имеет вид
F(s,t) = t2 + 1,
а для уравнения E.5) она равна
F{s, t) = B{s)t.
Доказательство теоремы. Доказательство проводится обычным спо-
способом последовательного нахождения коэффициентов функции /.
5.9. Задачи 83
Пусть степень F not равна п и
F(s,t)= (Foo + Fois
+ (FOn + Flns + F2ns2 + ...)tn,
f(s) = fo + fis + f2s2 + ...
Приравнивая коэффициенты при s° в левой и правой частях уравне-
уравнения E.9), получаем
Л = Foo + F01/0 + ... + FOn/o".
Аналогично, равенство коэффициентов при s1 дает
2/2 = Fio + F01/1 + Fufo + ¦ ¦ ¦ + ^„/(TVi + fin/on-
Вообще, /„ находится из уравнения
п/„ = ..., E.10)
где точками обозначен многочлен от коэффициентов функции F и ко-
коэффициентов /о, Д, ..., fn-i функции /. При каждом п > 0 уравне-
уравнение E.10) имеет единственное решение, и теорема доказана.
5.9. Задачи
5.1. Многочлен Чебышева Т„ определяется формулой
cos nip = Tn(costp).
Вот несколько первых многочленов Чебышева:
Г0(ж) = 1, Т!(х)^х, T2{x) = 2x2-l, T3(x)=4x3-Zx.
Докажите, что Tn+i(x) = 2хТп(х) — Tn-i(x) и выведите отсюда, что
5.2. Пусть последовательность {о„}, начинающаяся с чисел 1, 1, 2,
5, 17, 73, ..., определена условиями
= (п + 1)о„ - f jan_2, n > 1.
84 Глава 5. Функции нескольких переменных
Докажите, что экспоненциальная производящая функция A(s) для этой
последовательности удовлетворяет дифференциальному уравнению
(l-8)A'{8)=(l-\f)A{8)
и имеет вид
5.3. Докажите, что:
а) сумма и произведение двух функций Гурвица является функцией
Гурвица;
б) производная и интеграл функции Гурвица является функцией
Гурвица;
в) результат подстановки функции Гурвица в функцию Гурвица
является функцией Гурвица;
г) если в условиях теоремы 5.10 правая часть F уравнения является
функцией Гурвица и число /о целое, то решение / этого уравнения с
начальным условием /@) = /о будет функцией Гурвица.
5.4. Обозначим через ап,к число путей в треугольнике Дика, состо-
состоящих из п звеньев, площадь под которыми равна к; а2д = 1, аг,* = 0
при к четном. Докажите, что
1-
г
„2,5
l__i_L_
5.5. Докажите справедливость следующих разложений в непрерыв-
непрерывные дроби:
а)
B{s) = 7 *'•** '
7
2 -За2
где B(s) — производящая функция для стороны Бернулли треугольни-
треугольника Бернулли-Эйлера;
5.9. Задачи 85
б)
D2» -1)!!s2n = —
n=0 1 -
1-
гдеBп-1)!! =
в)
* ~~ s2
n=0 1 - S
1 — a —
2з2
1-s-
1
где /„ — число инволюций (перестановок, квадрат которых есть тожде-
тождественная перестановка) на множестве из га элементов, /i = 1, /2 = 2,
/з=4, /4 = Ю, ...;
г)
. ,ч. « 1
п=о l-2s
l-4s-
1-ба-!^2-
[Подсказка: Припишем к любой перестановке множества {1,..., п+1}
слева и справа 0, а затем сопоставим каждому элементу i = 1, ..., га
вектор в треугольнике Моцкина.]
Д)
n=0 1 - S
- 3S
о2.2
1 _ 5s - т^-5-
[Подсказка: Припишем к любой перестановке множества {1,..., п} сле-
слева 0, а справа га + 1, а затем сопоставим каждому элементу i = 1, ..., га
вектор в треугольнике Моцкина.]
5.6. Рассмотрим гипергеометрическую функцию
86 Глава 5. Функции нескольких переменных
а) Докажите, что
вA - в)Л"(в) + A - 2в)Л'(в) - \h(s) = 0.
б) Найдите асимптотику коэффициентов функции h.
5.7. Докажите, что степенной ряд
, ч , 2s 6s2 20s3 , , f2n
удовлетворяет дифференциальному уравнению
ну" + A - W - 2j/ = 0.
5.8. Найдите несколько первых членов разложения по х решения у
дифференциального уравнения
у' = 2 + Заг - 2у + х2 + х2у.
г л гт j. / \ arcsin s ,
5.9. Докажите, что функция y(s) = Т77о удовлетворяет диф-
A -а ) I
ференциальному уравнению
(l-s2)y'-sy = l
и найдите последовательность ее коэффициентов.
5.10. Выпишите дифференциальное уравнение, которому удовлетво-
удовлетворяет функция
и найдите последовательность ее коэффициентов.
5.11. Выпишите треугольник Бернулли-Эйлера mod2.
5.12. Докажите, что число неразложимых систем меандров (см. зада-
задачу 4.5) порядка рга (где р — простое, m ^ 1) сравнимо с 2 по модулю р.
Глава 6
Разбиения и разложения
6.1. Разбиения и разложения
В первой главе, решая задачу про число счастливых билетов, мы
уже изучали вопрос о числе представлений натурального числа тг в ви-
виде суммы к слагаемых. Оставим в стороне ограничение на величину
слагаемых (в задаче о числе счастливых билетов слагаемые были ци-
цифрами, поэтому их величина не должна была превышать 9). Найдем,
сколькими способами можно представить число тг в виде суммы нео-
неотрицательных слагаемых.
Два представления
тг = ai + ... + ак — Ь\ + ... + Ьк
будем считать различными, если а* ф Ь* хотя бы для одного индекса г,
1 ^ г ^ к. Такое представление числа тг будем называть его разложе-
разложением.
Предложение 6.1. Число различных разложений числа п в сумму к
целых неотрицательных слагаемых равно ("'It^1)-
Доказательство. Представим себе число тг в виде набора из тг оди-
одинаковых шариков, лежащих на прямой. Каждому разложению числа тг
в сумму к слагаемых сопоставим расстановку к — 1 палочки между ша-
шариками. Элемент а* разложения равен числу шариков между палочками
с номерами г - 1 и г. Вместе палочки и шарики составляют тг + к — 1
предмет. При этом назначить fc — 1 предмет палочками можно ровно
(п^'_~1) различными способами. Утверждение доказано.
Несложно выписать и производящую функцию для числа разложе-
разложений. По сути дела, мы уже сделали это в первой главе.
Предложение 6.2. Производящая функция для числа разложений
на к слагаемых имеет вид
Сложнее подсчитать число разбиений числа тг. Разбиением мы бу-
будем называть класс эквивалентности разложений, ни одно из слагае-
слагаемых в которых не равно нулю. При этом два разложения считаются
88 Глава 6. Разбиения и разложения
эквивалентными, если одно можно получить из другого перестановкой
слагаемых.
Вот все разбиения маленьких чисел:
п = 1 1
п = 2 2 =1 + 1
п = 3 3 =2 + 1 = 1 + 1 + 1
п=4 4=3+1=2+2=2+1+1=1+1+1+1
п=Ь 5=4+1=3+2=3+1+1=
=2+2+1=2+1+1+1=1+1+1+1+1
Обратите внимание на то, что каждое разбиение в таблице записано
в порядке убывания слагаемых: два разбиения, записанных в таком ви-
виде, легко сравнивать.
Обозначив число разбиений числа п через рп, получаем таблицу на-
начальных значений последовательности рп:
П0123456 7 8
р„ 1 1 2 3 5 7 11 15 22
Наша ближайшая задача — найти производящую функцию для по-
последовательности р„. Для этого подсчитаем сначала число разбиений на
части, удовлетворяющие некоторым ограничениям. Пусть P\(s) — про-
производящая функция для числа разбиений числа п на части, равные 1.
Очевидно, что для каждого числа такое разбиение единственно, по-
поэтому
Pt (в) = 1 + s + S2 + S3 + .. . = —!—.
1 ™~ S
Число разбиений числа п на части, равные 2, равно 1 для четных тг
и равно нулю в противном случае. Поэтому
P2(s) = 1 + s2 + s4 + s6 + ... = —
1-з2'
Число разбиений числа п на части, не превосходящие двух, тем са-
самым, описывается производящей функцией
Аналогично, числу разбиений п на части, равные трем, соответствует
производящая функция Рз(в) = 1/A - s3), а число его разбиений на
части, не превосходящие трех, описывается производящей функцией
Продолжая это рассуждение, мы приходим к следующей теореме.
6.1. Разбиения и разложения 89
Теорема 6.3 (Эйлер). Производящая функция для числа разбиений
числа п имеет вид
P{S) =
Для того, чтобы придать утверждению теоремы смысл, необходимо
пояснить, что понимается под бесконечным произведением, стоящим
в знаменателе правой части равенства F.1). Это произведение должно
быть формальным степенным рядом
Q(e) = 9о + qis + <fe*2 + . -. = A - s)(l - «2)A - s3)... F.2)
Для того, чтобы сказать, чему равны коэффициенты до, Qi, 42, • ¦ ¦ бес-
бесконечного произведения, посмотрим сначала на конечные произведе-
произведения:
1-s = 1 -8
A-*)A-*2) = 1 -8 -З2 +S3
A -S)(l -S2)(l -S3) = 1-8 —S2 +S4 + S5 -S6
A - s)...(l-s4) = 1 —s —s2 +2s5 + ...
A-S)... A-S5) = 1 -8 -S2 + S5 + ...
Видно, что коэффициенты в этих конечных произведениях «стаби-
«стабилизируются» — начиная с некоторого момента перестают изменять-
изменяться (стабилизирующиеся члены разложения выделены). Это и неудиви-
неудивительно: умножение на 1 - зк не меняет коэффициентов многочлена при
степенях, меньших к. Поэтому мы можем просто положить д* равным
коэффициенту при sk в многочлене A — s)(l — s2)... A — s*).
Теперь мы можем выписать аналогичные бесконечные произведения
и для разбиений с различными ограничениями.
Так, число разбиений на различные слагаемые дается производящей
функцией
производящая функция для разбиений на различные нечетные слагае-
слагаемые имеет вид
а разбиения на произвольные нечетные слагаемые перечисляются про-
производящей функцией
1
90
Глава6. Разбиения и разложения
а) б)
Рис. 6.1. Диаграммы а) Ферре и 6) Юнга
Разбиения тесно связаны с алгеброй многочленов. Рассмотрим коль-
кольцо многочленов С[х\, х%, Хз, ...] от бесконечного числа переменных.
Будем считать, что переменной х% приписан вес i и что при перемно-
перемножении переменных их веса складываются. Подсчитаем число мономов
веса п, т. е. размерность пространства однородных многочленов веса п.
При тг = 1 такой моном всего один — это моном х\. При тг = 2
имеется два монома веса тг — это х\ и хъ. Число мономов веса 3 рав-
равно трем, это х\, х\Х2 и хз- Вообще, число мономов веса тг равно р„.
Действительно, каждому моному веса п можно сопоставить разбиение
числа тг по следующему правилу: число слагаемых i в разбиении равно
степени вхождения переменной х% в моном. Ясно, что это соответствие
взаимно однозначно.
Вот полезная геометрическая интерпретация разбиений. Каждое
разбиение удобно представлять в виде диаграмма Ферре или диаграм-
диаграммы Юнга (см. рис. 6.1). Изображенные на этом рисунке диаграммы
соответствуют разбиению 5 + 4 + 4 + 2+1 числа 16. Каждая строч-
строчка диаграммы содержит столько элементов, каково соответствующее
слагаемое разбиения.
Используя диаграммы Ферре или Юнга, можно доказывать различ-
различные свойства разбиений. Например, на диаграммах Юнга действует
естественная инволюция — отражение относительно диагонали. Неко-
Некоторые диаграммы при таком отражении переходят в себя (см. рис. 6.2).
Такие диаграммы (и соответствующие им разбиения) будем называть
симметричными.
Докажем следующее свойство симметричных разбиений.
Предложение 6.4. Число симметричных разбиений числа п равно
числу его разбиений на различные нечетные слагаемые.
6.2. Тождество Эйлера
91
а) б)
Рис. 6.2. а) симметричная диаграмма Юнга; б) центральные крюки в ней
Доказательство. Для доказательства поставим в соответствие ка-
каждой симметричной диаграмме диаграмму, составленную из ее «цен-
«центральных крюков» (рис. 6.26)). Число клеток в каждом центральном
крюке симметричной диаграммы нечетно, и эти числа попарно различ-
различны. Наоборот, взяв диаграмму, составленную из строк различной не-
нечетной длины, мы можем «сломать» каждую такую строчку посередине
и составить из получившихся крюков симметричную диаграмму.
6.2. Тождество Эйлера
Производящая функция Q, задаваемая равенством F.2), оказывает-
оказывается очень интересной. Эйлер продолжил вычисление ее коэффициентов
и получил
Q(s) = 1 - a - s2 + s5
s7 -
g12_s15+522.
_ ,,
77
,,92
,,100
Видно, что среди коэффициентов в вычисленных членах встречаются
только нули, единицы и минус единицы. Ненулевые коэффициенты сто-
стоят на некоторых вполне определенных местах и знаки при единицах
попарно чередуются. Эти наблюдения привели Эйлера к гипотезе, ко-
которую мы сформулируем в виде теоремы.
Теорема 6.5 (тождество Эйлера).
92
Глава 6. Разбиения и разложения
Ряс. 6.3. Нижняя строчка и боковая диагональ диаграммы Юнга
Доказательство. При раскрытии скобок ряд
содержит те же члены, что и ряд для числа разбиений с различными
слагаемыми
Однако некоторые члены при этом входят со знаком плюс, а некоторые
со знаком минус. Знак плюс имеют члены, соответствующие разбиени-
разбиениям на четное число слагаемых, а знак минус — члены, отвечающие
разбиениям на нечетное число слагаемых. Мы докажем, что число раз-
разбиений числа п на четное и нечетное число слагаемых одинаково для
всех значений п кроме некоторых исключительных.
Представим каждое разбиение в виде диаграммы Юнга. Важную
роль в доказательстве будут играть нижняя строчка диаграммы и ее
«боковая диагональ» (см. рис. 6.3).
Пусть I — длина нижней строчки, d — длина диагонали, к — чи-
число строчек в диаграмме, т. е. число слагаемых в разбиении. Определим
отображение множества диаграмм, все строчки в которых имеют раз-
разную длину, в себя следующим образом:
t> если I <d,io отрежем от диаграммы нижнюю строчку и прикле-
приклеим ее к диагонали;
t> если I = d < к, то проделаем то же самое;
t> если I > d и к > I, то наоборот, отрежем диагональ и приклеим
ее ниже нижней строчки.
С остальными (исключительными) диаграммами не будем делать
ничего.
Наше отображение меняет четность числа строк в диаграмме, т. е.
четность числа слагаемых в разбиении, для всех неисключительных
6.2. Тождество Эйлера 93
диаграмм. Поэтому если неисключительных диаграмм с числом клеток
п нет вообще, то коэффициент при sn в разложении Q(s) равен нулю.
Исключительные диаграммы выделяются условиями
к = I = d или к = d, l = k+l.
В первом случае имеем
во втором —
п = {к + 1) + (к + 2) + ... + 2к = ?1_™.
В каждом из этих случаев исключительная диаграмма единственна. То-
Тождество Эйлера доказано.
Тождество Эйлера дает эффективный способ вычисления числа раз-
разбиений числа п. Именно, справедливо следующее рекуррентное соотно-
соотношение.
Предложение 6.6.
Рп = Рп-1 + Рп-2 - Рп-Ь - Рп-7 + Рп-12 + Рп-15 ~ ¦¦¦
Действительно, это очевидное следствие равенства
P(s)Q(s) = 1.
Полученное рекуррентное соотношение нашло замечательное при-
применение в «линейке Фукса»1'.
«Эта формула позволяет быстро составить довольно длинную табли-
таблицу чисел рп. Вот практический совет, как это сделать. Возьмите лист
клетчатой бумаги — лучше всего двойной тетрадный лист. Отрежьте
вдоль его длинной стороны полоску шириной 3-4 клетки. Положите эту
полоску перед собой вертикально и у левого среза в нижней клетке по-
поставьте какой-нибудь знак, скажем звездочку. Затем, двигаясь вверх,
поставьте в первой клетке +, во второй +, в пятой -, в седьмой -,
в двенадцатой +, в пятнадцатой 4- и т.д., насколько хватит длины
полоски. Оставшуюся часть листа также положите перед собой верти-
вертикально и, отступя 10-15 клеток от ее левого среза, проведите на ней
^Квант. 1981. № 8. с. 15.
94 Глава 6. Разбиения и разложения
вертикальную черту — сверху донизу. В клетки, прилегающие к черте
слева, двигаясь сверху вниз, впишите известные вам числа рп, начиная
с ро: 1, 1, 2, 3, 5, 7. Чтобы найти следующее значение, приложите от-
отрезанную полоску справа к вертикальной черте так, чтобы звездочка
оказалась против первой пустой клетки. Теперь из суммы чисел, сто-
стоящих против плюсов, вычтите сумму чисел, стоящих против минусов.
Что получится — впишите в клетку против звездочки: это следующее
значение функции р„. Опустите полоску на одну клетку вниз и повто-
повторите то же самое. И так далее. Через несколько минут вы получите
колонку чисел рп высотой в ваш лист».
6.3. Разбиения множеств и непрерывные дроби
Так же, как закрепление вершин многоугольника упрощает перечи-
перечисление его триангуляции (см. раздел 2.5), так и разбиения множеств
легче поддаются описанию, чем разбиения чисел.
Рассмотрим множество Nn = {1, 2,..., п} натуральных чисел от 1
до п. Разбиением множества Nn называется его представление в ви-
виде объединения непустых непересекающихся подмножеств. Например,
множество N3 допускает пять разбиений:
{{1,2,3}}, {{1,2},{3}}, {{1,3}, {2}}, {{2,3},{1}}, {{1}, {2}, {3}}.
Число разбиений множества Nn обозначим через рп и займемся изуче-
изучением производящей функции
P(s) =po+P\s+p2S2 + ...
(мы полагаем, по определению, ра = 1).
Каждому разбиению множества Nn можно естественным образом
сопоставить разбиение числа п. Для этого нужно представить п в виде
суммы количеств элементов в каждом из множеств разбиения. Нетруд-
Нетрудно подсчитать и число разбиений множества Nn, отвечающих данному
разбиению
П = П\ +П2+ .-.
числа п. Элементы первого множества можно выбрать (^) способами;
после этого элементы второго множества можно выбрать (n~ni) спо-
способами и т. д. Всего разбить элементы множества Nn по множествам
6-3. Непрерывные дроби 95
с п\, п2, ..., пк элементами можно
"Л п* /
п! {п — t*i)! (п — п\ — ... — Tifc—1)!
7ii -(^ — ^1) ^2-(^ — ^1 — ^2)' ^ifc!0!
- п! _( п \
m!n2!...щ\ \т п2 ... пк)
Полученное выражение называется мультиномиальным коэффициен-
коэффициентом. Оно обобщает биномиальный коэффициент — число сочетаний.
Как нетрудно видеть, мультиномиальный коэффициент представля-
представляет собой коэффициент при х ж22 • • • ^kk B разложении многочлена
(xi + ... + xk)n:
Однако число разбиений множества Nn, отвечающих данному раз-
разбиению числа п, не совпадает в точности с мультиномиальным коэффи-
коэффициентом. Дело в том, что множества разбиения, содержащие одинако-
одинаковое количество элементов, можно переставлять между собой. Поэтому
правильный ответ имеет вид
mi!... mn! \щ ... пк
где т., — это число элементов разбиения, равных г.
Каждому разбиению множества Nn на подмножества сопоставим
путь в треугольнике Моцкина по следующему правилу. Пусть элемент
г € Nn входит в некоторое подмножество разбиения. Тогда г-й отрезок
пути будет горизонтальным, если либо соответствующее подмножество
состоит из одного элемента г, либо элемент i не является в подмноже-
подмножестве ни минимальным, ни максимальным элементом, г-й отрезок пути
будет вектором подъема A, 1), если элемент t — минимальный в своем
подмножестве, и он будет вектором спуска A, -1), если соответствую-
соответствующий элемент максимален. Начальная точка пути находится, как обыч-
обычно, в точке @, 0). На рис. 6.4 изображены разбиение множества Nw
и путь в треугольнике Моцкина, соответствующий этому разбиению.
96 Глава 6. Разбиения и разложения
{1,3,4,8,10}, {2,6,7}, {5}, {9}
123456789 10
Рис. 6.4. Путь в треугольнике Моцкина, отвечающий разбиению множества
Ясно, что для каждого разбиения путь, отвечающий ему, является
правильным: он лежит в положительной полуплоскости и заканчива-
заканчивается на высоте 0. Действительно, среди первых т элементов множе-
множества Nn число максимумов не может превосходить числа минимумов
ни при каком т, а при т = п числа максимумов и минимумов совпа-
совпадают.
Подсчитаем, сколько разбиений соответствует данному пути. Пусть
начальная часть пути, состоящая из г отрезков, заканчивается на вы-
высоте j, и предположим, что первые j элементов уже разбиты на под-
подмножества. Если (j + 1)-й отрезок пути представляет собой вектор
подъема A, 1), то элемент j + 1 является минимумом нового подмно-
подмножества разбиения, никаких других возможностей нет. Поэтому крат-
кратность соответствующего ребра равна 1. Если это горизонтальный
вектор, то отвечающий ему элемент может либо входить в одно из
уже существующих множеств (таких возможностей ровно j, так как
ровно в j имеющихся множествах еще не зафиксирован максималь-
максимальный элемент), либо образовывать одноэлементное множество. Поэто-
Поэтому кратность горизонтального ребра равна j + 1. Кратность вектора
спада A, —1) равна j, так как соответствующий ему элемент может
быть максимальным в одном из j подмножеств. Соответствующая рас-
расстановка кратностей на ребрах в треугольнике Моцкина изображена
на рис. 6.5.
Таким образом, справедлива следующая теорема.
Теорема 6.7. Число р~п разбиений множества Nn на непустые под-
подмножества равно числу правильных путей длины п в треугольнике
Моцкина с кратностями, изображенном на рис. 6.5.
Из доказанной теоремы и теоремы 5.5 немедленно вытекает следу-
следующее утверждение.
6.4. Задачи 97
Рис. 6.5. Расстановка кратностей на ребрах, отвечающая производящей
функции разбиений
Следствие 6.8. Производящая функция Pn(s) для числа разбиений
множества Nn раскладывается в непрерывную дробь
Pn(s) =
l-3s-
З*2
6.4. Задачи
6.1. Сколькими способами можно разменять рубль на монеты в 1, 5,
10 и 50 копеек?
6.2. Сколькими способами можно взвесить 78 г с помощью разнове-
разновесок 1, 1, 2, 5, 10, 10, 20, 50 г на
а) одночашечных весах;
б) двухчашечных весах?
(Применение двух различных разновесок одного веса дает различные
взвешивания.)
98 Глава 6. Разбиения и разложения
6.3. Всякое число может быть единственным образом записано в де-
десятичной системе счисления. Поэтому
(l + s + s + ... + s)(l + s + ... + s).-- T-
х — з
Докажите.
6.4. Докажите, что
+ *2)A
6.5. Докажите, что каждое целое положительное число можно пред-
представить в виде суммы различных целых положительных слагаемых
столькими же способами, сколькими его можно представить в виде
суммы нечетных (может быть и совпадающих) слагаемых.
6.6. Докажите тождества Гаусса:
а)
i}~S)i.1~Sl)[] "'!?'•• =l-2s + 2s4-2s9 + ...;
6)
A—»)A-QA-H)... = ^ ^ 10
A)A3)A5)
6.7. Докажите, что натуральное число п может быть представле-
представлено в виде суммы меньших натуральных слагаемых 2п~1 — 1 способом,
если два представления, отличающиеся порядком слагаемых, считать
различными. Например, у числа 4 семь представлений:
4 = 3 + 1 = 1+3 = 2 + 2 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2=1 + 1 + 1 + 1.
6.8. Найдите производящую функцию для числа симметричных раз-
разбиений.
6.9. Рассмотрим кольцо многочленов от бесконечного набора пере-
переменных, в котором переменным приписан вес, причем число перемен-
переменных веса i конечно для любого г. Обозначим это число через <&. Выпи-
Выпишите производящую функцию для последовательности размерностей
пространств однородных многочленов веса п.
6.10. Обозначим через ап сумму делителей числа п (включая 1 и са-
само п); например, а% = 1 + 2 + 3 + 6 = 12. Пусть ?(s) — производящая
функция для последовательности ап,
?(s) = s + 3s2 + 4s3 + 7s4 + 6s5 + 12s6 + ...
6.4. Задачи 99
а) Докажите, что
?(e)P(e) = sP'(s),
где P(s) — производящая функция для числа разбиений.
б) Выведите отсюда рекуррентное соотношение на числа ап.
6.11. Докажите, что последовательность р„ чисел разбиений растет
монотонно и оцените скорость ее роста.
6.12. Докажите, что производящая функция для числа диаграмм
Юнга по периметру равна хЬц-
6.13. Докажите, что
Ы2 • ¦ -
A - *х)A - *2)... A - **)(! - «i*a -¦-«*)'
Глава 7
Производящие функции Дирихле
и формулы включения-исключения
7.1. Принцип включения-исключения
Обратимся к очень простой общей теореме формальной логики.
Пусть В — какое-либо конечное множество, элементы которого
могут обладать некоторыми из свойств с\, ..., ст. Обозначим через
N(ci), 1 ^ г ^ т число элементов множества В, обладающих свойством
Ci, через N(ci, е,), г / j — число элементов множества В, обладаю-
обладающих одновременно двумя свойствами с<, Cj, и т. п. Пусть также ЛГA) —
общее число элементов в множестве В.
Теорема 7.1 (принцип включения-исключения). Число элементов
в множестве В, не обладающих ни одним из свойств a, i = 1, ..., т,
равно
Доказательство. Разобьем все элементы множества В на группы:
В = Во U B\ U... U Bm, причем подмножество Bt состоит из элементов,
обладающих ровно I свойствами. Рассмотрим последовательно выраже-
выражения
NA),
N(l)-N(Cl)-...-N(cm),
NA) - Ща) - ... - N(cm) + N(CU Сй) + . . . + ЩСт-!, Ст),
Сопоставим каждому из этих выражений расстановку чисел на множе-
множествах Bi. Первое выражение соответствует присвоению каждой группе
кратности 1 — мы учли все элементы по одному разу. Второму выра-
выражению соответствует присвоение множеству J3/ кратности 1 - I, так
как при вычитании мы учли каждый его элемент ровно I раз. Третье
выражение сопоставляет множеству J3/ кратность 1 — I + B), и т. д.
Таким образом, переход от выражения с номером I к выражению с но-
номером I + 1 не меняет кратности множеств Во, ..., J3/. Эти кратности
7.1. Принцип включения-исключения 101
равны
что равно нулю для всех / кроме / = 0, откуда и вытекает теорема.
Принцип включения-исключения легко запомнить с помощью следу-
следующего простого мнемонического правила. Пусть 1 соответствует объ-
объектам, обладающим всеми свойствами, 1 — сг- —• выражение для объ-
объектов, не обладающих свойством с*. Тогда выражение для объектов,
не обладающих ни одним из свойств ci, ..., cm, будет иметь вид
откуда, раскрывая скобки, получаем
A - Ci)(l - С2) . . . A - Cm) = 1 - Ci - . . . - Cm + CiC2 + . . . - C1C2C3 - ...
Применим принцип включения-исключения для нахождения числа
счастливых билетов. Заметим, что число счастливых билетов равно чи-
числу билетов с суммой 27. Действительно, пусть билет aibicia2b2c2 —
счастливый. Сопоставим ему билет ai6iCi(9 — a2)(9 - 62)(9 — с2), сум-
сумма цифр которого равна 27. Это соответствие, очевидно, взаимно-
взаимнооднозначно.
Рассмотрим теперь множество всевозможных расстановок неотри-
неотрицательных целых чисел с суммой 27 в шести позициях и введем шесть
свойств таких расстановок. Свойство с, состоит в том, что число в г-й
позиции не меньше 10. Число счастливых билетов равно числу расста-
расстановок, не обладающих ни одним из свойств сь ..., с$.
Число iV(l) всех расстановок неотрицательных целых чисел с сум-
суммой 27 в шесть позиций равно C52). Число N(ci) расстановок, удовлетво-
удовлетворяющих свойству а, одинаково для всех i и равно B52). Действительно,
мы можем поставить в г-ю позицию число 10, а оставшуюся сумму 17
произвольно распределить по шести позициям.
Аналогично число расстановок, удовлетворяющих одновременно
двум свойствам q и с,, одинаково для любой пары свойств и равно
A82): мы ставим число 10 в г"-ю и j-ю позиции, а оставшуюся сумму 7
произвольным образом распределяем по шести позициям. Число же рас-
расстановок, удовлетворяющих одновременно трем и более свойствам, рав-
равно нулю, так как общая сумма всех чисел меньше 30. Таким образом,
общее число расстановок, не удовлетворяющих ни одному из свойств с,,
а, значит, и общее число счастливых билетов, дается следующим пред-
предложением.
102 Глава 7. Функции Дирихле
Предложение 7.2. Число счастливых билетов равно
C-GD-CD-
Решим с помощью принципа включения-исключения еще одну зада-
задачу, имеющую большое число приложений.
Перестановка ж элементов множества {1, 2, ..., п} называется бес-
беспорядком, если тг(&) ф к ни при каких к = 1, ..., п. Обозначим через dn
число беспорядков на множестве из п элементов. Вот начало таблицы
чисел беспорядков:
п 0 1 2 3 4
dn 1 0 1 2 9
Чтобы подсчитать число беспорядков, введем п свойств перестано-
перестановок на множестве из п элементов. Свойство с, состоит в том, что пере-
перестановка оставляет на месте элемент г. Число всех перестановок рав-
равно п\. Число перестановок, удовлетворяющих свойству с,, равно (п — 1)!:
мы фиксируем г-й элемент перестановки, а остальные переставляются
произвольно. Число перестановок, удовлетворяющих двум свойствам с*
и Cj, равно (я — 2)!: два элемента перестановки фиксируются, остальные
переставляются произвольно. Вообще, число перестановок, удовлетво-
удовлетворяющих т свойствам, равно (п — т)!. Таким образом, мы приходим
к следующей формуле.
Предложение 7.3. Число беспорядков на множестве из п элемен-
элементов равно
При п -» со выражение в скобках стремится, как хорошо извест-
известно, к е~1. Таким образом, беспорядки составляют приблизительно е-ую
часть всех перестановок.
7.2. Производящие функции Дирихле и действия над ними
Рассматривавшиеся нами ранее производящие функции относились
к классу степенных рядов. Однако в мультипликативной теории чисел
7.2. Функции Дирихле 103
большее применение находят производящие функции Дирихле. Самой
известной среди них является дзета функция Римана
C(s) = js+^ + ^ + --- G-1)
Общая же производящая функция Дирихле, отвечающая последова-
последовательности ai, O2, оз, .. •, имеет вид
1* + 2s + 3е + • * •
Дзета функция Римана отвечает последовательности 1,1,1, Она
играет для производящих функций Дирихле такую же роль, как геоме-
геометрическая прогрессия для обыкновенных производящих функций и экс-
экспонента для экспоненциальных производящих функций. Обратите вни-
внимание на то, что нумерация коэффициентов производящих функций
Дирихле начинается с единицы, а не с нуля, как это было в случае
обыкновенных производящих функций.
Причиной, обуславливающей введение производящих функций Ди-
Дирихле, служит их поведение относительно умножения: при перемноже-
перемножении двух функций A(s) = ^2а„п~в и B(s) = ^2bnn~s мы получаем
функцию
At \nt \ °i&i , 0162 + 0261 , 0163 + 0361 0164 +02^2 +0461 .
A(s)B(s) = -р- Н —s + jp + —a 1-
E
Ekl=n
n
где внутреннее суммирование ведется по всем разложениям числа п
в произведение двух сомножителей. Таким образом, использование про-
производящих функций Дирихле позволяет контролировать мультиплика-
мультипликативную структуру натуральных чисел. Отметим, что сложение таких
производящих функций соответствует обычному почленному сложению
последовательностей.
Роль единицы при умножении производящих функций Дирихле иг-
играет функция 1 = 1~*. Любая производящая функция Дирихле A(s)
с ненулевым свободным членом, Oi ф 0, обратима: существует функция
B(s), такая что A(s)B(s) = 1. Построим обратную функцию для дзета
функции Римана.
104 Глава 7. Функции Дирихле
Теорема 7.4. Обратная функция для дзета функции Римана имеет
вид
n=l
где
(—l)tn где tn — число простых делителей числа п,
_ если в разложении п на простые множители
' нет повторяющихся множителей;
О в противном случае.
Последовательность ц„ мы будем называть последовательностью
Мёбиуса, а функцию M(s) — функцией Мёбиуса.
Доказательство. Для доказательства перемножим функции ?(s) и
M(s). Коэффициент при n~s, п > 1 в произведении будет равен
Действительно, пусть разложение п на простые множители имеет вид
п = р*1 ...pt', где t = tn. Тогда коэффициент при т~* функции M(s)
участвует в произведении с ненулевым коэффициентом в том и только
в том случае, если m является произведением некоторого подмножества
множества простых чисел pi, ...,pt- Число таких подмножеств из к
элементов равно (?), а знак соответствующего коэффициента при т~а
равен (-1)*.
Теорема доказана.
Из доказанной теоремы непосредственно вытекает следующее утве-
утверждение.
Следствие 7.5. Пусть /n, gn — две последовательности, такие
что
/п = Х>, G.2)
где суммирование ведется по всем делителям t числа п. Тогда элемен-
элементы последовательности дп выражаются через элементы последова-
последовательности fn no правилу
9п = ]>>«/*/*• G-3)
t|n
7.3. Обращение Мёбиуса ' 105
Доказательство. Действительно, равенство G.2) означает, что
F(s) = C(s)G(s),
где F(s) (соотв., G(s)) — это производящая функция Дирихле для по-
последовательности чисел /„ (соотв., дп). Умножая обе части последнего
равенства на M(s), получаем
M{s)F{s) = M{s)as)G{s) = G(s),
что и составляет содержание равенства G.3). Следствие доказано.
Существование и единственность разложения натурального числа
на простые множители позволяют найти представление дзета функции
в виде произведения (и, соответственно, еще одно представление фун-
функции Мебиуса).
Предложение 7.6.
<•W i _ 2-' 1 - 3~* 1 - 5-* 1 - Тш '' "
M(s) = A - 2-) A - 3"s) A - 5"s) A - 7"s) ...,
где произведения берутся no всем простым числам.
7.3. Обращение Мёбиуса
Формула суммы геометрической прогрессии, формула включения-
исключения 7.1, теорема 7.4 и формула обращения Эйлера F.1) явля-
являются проявлениями одного простого общего принципа, называемого
принципом обращения Мебиуса.
Этот принцип позволяет находить обратную функцию к дзета-
функции в широком классе ситуаций.
А именно, пусть ei, вг, ¦ ¦ • — набор (возможно бесконечный) пере-
переменных, и мы рассматриваем алгебру степенных рядов от этих пере-
переменных. Определим дзета функцию данной алгебры как сумму всех
мономов в этой алгебре, взятых с коэффициентом единица. Так, геоме-
геометрическая прогрессия
1 + s + s2 + s3 +...
является дзета функцией алгебры степенных рядов от одной перемен-
переменной. Функция, обратная дзета функции, является функцией Мебиуса
алгебры. Она представляет собой сумму мономов алгебры, взятых с не-
некоторыми коэффициентами, которые мы фактически уже вычислили в
теореме 7.4.
106 Глава 7. Функции Дирихле
Теорема 7.7. Коэффициент при мономе s"t' ... s"^1 в функции Меби-
Мебиуса алгебры степенных рядов от переменных s1? s-2, ¦¦¦ равен нулю, ес-
если какая-нибудь из переменных входит в моном со степенью, большей
1 (п{ > 1 для какого-нибудь г), и он равен (—1)т, если веет переменных
входят в моном в первой степени.
Доказательство. Можно провести доказательство теоремы, повто-
повторив, практически дословно, доказательство теоремы 7.4. Мы, однако,
предпочтем несколько другой путь. Дело в том, что мы попросту зна-
знаем обратную функцию для дзета функции. Действительно, сама дзета
функция является произведением дзета функций от каждой из пере-
переменных Si, S2, Поэтому она представляет собой произведение гео-
геометрических прогрессий
A + sx + sf + si + ... )A + s2 + si + si + ...)...
(Заметим, что коэффициент при каждом мономе является суммой ко-
конечного числа конечны! произведений.) Поэтому обратная к ней функ-
функция Мебиуса представляет собой не что иное, как произведение
откуда утверждение теоремы следует мгновенно.
Теорема доказана.
Посмотрим, как применяется эта теорема. Чтобы вывести из нее
теорему 7.4, рассмотрим набор переменных S2, S3, s5, S7, . ¦ • (каждому
простому числу отвечает одна переменная, в которой это число слу-
служит индексом). Тогда алгебра функций Дирихле изоморфна алгебре
степенных рядов от указанного набора переменных: элементу п~", где
п = pj1 .. .pjjj" — разложение числа п на простые множители, отвечает
моном Sp| ... Sp™ алгебры степенных рядов. Легко видеть, что это соот-
соответствие действительно задает изоморфизм алгебр. Теорема 7.4 теперь
непосредственно вытекает из теоремы 7.7 (ср. предложение 7.6).
Принцип включения-исключения можно вывести из теоремы 7.7 сле-
следующим способом. Рассмотрим алгебру многочленов, порожденных пе-
переменными si, ..., sn (каждая переменная отвечает одному рассматри-
рассматриваемому свойству), срезанных по степени два. Это означает, что мы
приравниваем нулю всякий моном в алгебре, если какая-нибудь пере-
переменная входит в него в степени выше, чем первая. Моном s^ ...s,m
в такой алгебре отождествляется с подмножеством {ii, ..., im} мно-
множества {1, ..., п}. Формула включения-исключения есть не что иное,
как формула для функции Мебиуса этой алгебры.
7.4. Мультипликативные последовательности 107
Столь же простой оказывается и ситуация с формулой обращения
производящей функции для числа разбиений. Сопоставим каждому раз-
разбиению п = ni + ... + пт моном snisn2... snm (если некоторые части в
разбиении повторяются, то степень соответствующей переменной в мо-
мономе равна числу этих частей). Функция Мебиуса в этой алгебре, как
мы знаем, имеет вид
При подстановке sn = sn дзета функция алгебры превращается в про-
производящую функцию для числа разбиений (действительно, коэффици-
коэффициент при мономе sn в полученной функции равен числу всех разбиений
числа п). Обратная к ней функция Мебиуса переходит при этом в фун-
функцию
(l-s)(l-s2)(l-s3)...,
что и дает равенство F.2).
7.4. Мультипликативные последовательности
Помимо дзета функции и функции Мебиуса в теории чисел боль-
большую роль играют и другие производящие функции Дирихле, отвечаю-
отвечающие другим числовым последовательностям. Наиболее важными из них
оказываются мультипликативные числовые последовательности.
Определение 7.8. Последовательность аь а2, а3, ... называется
мультипликативной, если для всех взаимно простых пар индексов m, n
выполняется равенство атап = ат.п.
Заметим, что если в мультипликативной последовательности Oi = 0,
то эта последовательность состоит из одних нулей. Действительно,
On = ei n = ai°n = 0 для любого числа п. Это же рассуждение показы-
показывает, что если ai ф 0, то а.\ = 1. В дальнейшем мы будем рассматривать
только ненулевые мультипликативные последовательности.
Последовательность 1, 0, 0, 0, ... мультипликативна Последова-
Последовательность, состоящая из одних единиц, тоже, очевидно, мультиплика-
мультипликативна. Последовательность Мебиуса также мультипликативна, что вы-
вытекает, например, из теоремы 7.4. Приведем еще несколько примеров.
Пример 7.9. Обозначим через тп число делителей числа п. Произво-
Производящая функция Дирихле для последовательности г„, очевидно, имеет
вид
108 Глава 7. Функции Дирихле
Если числа тип взаимно просты, то число делителей их произведения
тп равно произведению ттг„: если р — делитель числа тп, a q — дели-
делитель числа п, то pq — делитель их произведения тп, причем каждый
делитель произведения можно представить в таком виде единственным
способом. Поэтому последовательность т„ мультипликативна.
Пример 7.10. Если через ип обозначить число различных простых
множителей числа п, то последовательность ап = а"п оказывается
мультипликативной для любого числа а.
Все мультипликативные последовательности определяются своими
элементами, индексы которых равны степеням простых чисел. Други-
Другими словами, для мультипликативных последовательностей имеет место
аналог утверждения 7.6.
Предложение 7.11. Последовательность {а,} является мультипли-
мультипликативной тогда и только тогда, когда соответствующая ей произ-
производящая функция Дирихле представляется в виде
где произведение берется по всем простым числам.
Из этого утверждения немедленно вытекает замечательное свой-
свойство мультипликативных последовательностей, обобщающее утверж-
утверждение о мультипликативности последовательности Мебиуса.
Следствие 7.12. Если производящие функции Дирихле A(s) и B(s)
отвечают мультипликативным последовательностям, то последо-
последовательности коэффициентов их произведения A(s)B(s) и частного
A(s)/B(s) также мультипликативны. Другими словами, производя-
производящие функции Дирихле, отвечающие ненулевым мультипликативным
числовым последовательностям, образуют группу по умножению.
Действительно, если каждая из функций A(s), B(s) обладает пред-
представлением G.4), то таким же представлением обладают их произведе-
произведение и частное. Само же утверждение 7.11 немедленно следует из опре-
определения мультипликативной последовательности.
7.5. Задачи
7.1. Найдите с помощью формулы включения-исключения площадь
сферического треугольника с углами a, /?, 7 на сфере единичного ра-
радиуса.
7.5. Задачи 109
7.2. Найдите с помощью принципа включения-исключения формулу
для числа счастливых билетов с номерами из 2р цифр, записанными
в системе счисления с основанием q.
7.3. Пусть ai, а.2, ¦ ¦ ¦, ate — различные простые множители числа
п = а^1 ... аркк. Докажите, что число <рп чисел, меньших п и взаимно
простых с ним, равно
7.4. Воспользовавшись предыдущей задачей, докажите, что после-
последовательность (рп мультипликативна.
7.5. Докажите, что число различных правильных замкнутых
n-угольников (в том числе самопересекающихся) вписанных в единич-
единичную окружность равно tpn/2.
7.6. Сколько несократимых дробей имеется среди п2 дробей
1/1, 1/2, 1/3, ..., 1/п
2/1, 2/2, 2/3, .... 2/п
п/1, п/2, п/3, ..., п/п?
7.7. Докажите, что число беспорядков на множестве из п элемен-
элементов — ближайшее целое число к п!/е.
7.8. Пусть диагональные элементы в п х п матрице равны нулю.
Подсчитайте число ненулевых элементов в разложении определителя
этой матрицы.
7.9. Докажите, что экспоненциальная производящая функция для
последовательности чисел беспорядков имеет вид D(s) — e~s/(l — s).
7.10. Пусть цп — последовательность Мебиуса. Тогда
п=0
7.11. Опишите все идеалы в алгебре функпий Дирихле.
7.12. Докажите следующую формулу:
max(ai, ..., ап) = а\ + ... +ап- min(ab a2) - ... - min(an_i, an) +
+ min(ai, a2, a3) + ... + (-1O1 rain(ai, ..., an).
7.13. Положим An = (—l)k, где к — число простых множителей чис-
числа п (считаемых с учетом кратности). Докажите, что последователь-
последовательность Ап мультипликативна.
110 Глава 7. Функции Дирихле
7.14. Найдите функцию Дирихле ?(s)A(s), где коэффициенты функ-
функции A(s) определены в предыдущей задаче.
7.15. Обозначим через аа{п) сумму а-х степеней делителей числа
п, аа(п) = ? *а (а — целое неотрицательное число). Докажите, что
t|n
производящая функция Дирихле для этой последовательности имеет
вид
а\8) — у —j-2- = (,(s)(,(s — а).
п=1
Глава 8
Перечисление вложенных графов
Настоящая глава посвяшена некоторым геометрическим аспектам
комбинаторики, в том числе наиболее активно развивающимся в по-
последние годы. Эти задачи связаны с графами и их вложениями в раз-
различные поверхности. На протяжении всей главы широко использует-
используется обозначение [s*]/(s) для коэффициента Д в производящей функции
2
8.1. Перечисление помеченных деревьев
Ряд трудностей в задачах перечисления обязан своим происхожде-
происхождением тому, что перечисляемые объекты имеют различные симметрии.
Так, например, если бы мы решили считать одинаковыми диагональные
триангуляции правильных многоугольников (см. раздел 2.5), переходя-
переходящие друг в друга при повороте, получение точной формулы превра-
превратилось бы в сложную задачу, да и сама формула вряд ли бы значи-
значительно продвинула нас в понимании природы триангуляции. Причина
такого явления кроется в том, что различные триангуляции допуска-
допускают различные группы симметрии. Все шесть поворотов триангуляции
шестиугольника, изображенной на рис. 8.1 а) дают различный резуль-
результат, в то время как повороты триангуляции, приведенной на рис. 8.1 б),
приводят лишь еще к двум новым триангуляциям, а на рис. 8.1 в) — к
одной.
б) в)
Рис. 8.1. Три диагональные триангуляции шестиугольника с различными
симметриями
В то же время явная формула, сводящая число диагональных три-
триангуляции многоугольника с перенумерованными вершинами к числу
Каталана, дает хорошую оценку на асимптотику числа триангуляции
112 Глава 8. Вложенные графы
многоугольника с ненумерованными вершинами. Действительно, чи-
число триангуляции, рассматриваемых с точностью до поворота (п + 2)-
угольника, не превосходит с„ ~ const • 4" • п/2, и оно не меньше, чем
сп/{п + 2) ~ const • 4" • п~5/2. Таким образом нарушение симметрии —
перенумерация вершин многоугольника — привело к серьезному упро-
упрощению задачи и лишь незначительно повлияло на точность ответа. Тот
же прием — маркировка — оказывается весьма эффективным и во
многих других перечислительных задачах. Мы увидим сейчас, как он
используется при перечислении деревьев.
Определение 8.1. Графом будем называть тройку Г = {V, Е, I}, со-
состоящую из конечного множества вершин V, конечного множества ре-
ребер Е и отображения инцидентности I: Е —> V х V, сопоставляющего
каждому ребру пару вершин (концы ребра), которые это ребро соеди-
соединяет. Ребро называется петлей, если его концы совпадают. Валент-
Валентностью вершины графа называется число ребер, для которых данная
вершина является концом (при подсчете валентности петля считается
за два ребра).
Граф обычно изображается на плоскости; вершинам графа соответ-
соответствуют точки на плоскости, ребрам — отрезки дуг, соединяющие эти
точки (см. рис. 8.2).
Рис. 8.2. Изображение графа на плоскости. Жирными точками обозначе-
обозначены вершины графа, дугами — его ребра. Не выделенные точки пересечения
ребер не являются вершинами
Замечание 8.2. 1. На самом деле, графом естественно считать не
определенный выше объект, а класс эквивалентности таких объек-
объектов. Две тройки Ti = {Vi, Ei, Ii} и Г2 = {V2, Ei, /2} называются
эквивалентными, если существуют взаимно однозначные отображения
v: Vi -» V2 и е: Ei -? Е2, такие что h ° е = (« х v) о /ь В дальнейшем
мы фактически будем использовать именно это определение.
2. У приведенного определения имеются варианты. Например, ино-
иногда естественно требовать, чтобы через каждую пару вершин графа
8.1. Перечисление помеченных деревьев 113
проходило не более одного ребра, т. е. чтобы отображение инцидентно-
инцидентности было инъективным. Иногда в графе запрещаются петли и т. д. Мы
будем всякий раз оговаривать подобные ограничения.
3. С топологической точки зрения граф представляет собой одно-
одномерный комплекс. Если на каждом ребре графа ввести ориентацию
(т. е. указать направление этого ребра), то граница ребра —¦ это раз-
разность конечной и начальной вершин.
Определение 8.3. Две вершины графа называются соседними, если
существует ребро, которое их соединяет. Граф называется связным,
если для любой пары и, v E V его вершин существует последователь-
последовательность vo = и, «1, ..., Vk = v E V вершин графа, в которой вершины
Vi-i и V{ соседние для всех i — 1, 2, ..., к. Циклом называется после-
последовательность vo, V\, ..., Vk G V вершин графа, в которой вершины
Vi-i и Vi соседние для всех i = 1, 2, ..., к, все вершины vo, v\, ..., Vk-\
попарно различны и vq = Vk- Деревом называется связный граф без цик-
циклов.
На рис. 8.3 приведены все деревья с п вершинами (n ^ 5).
Рис. 8.3. Деревья с п вершинами (п ^ 5)
Задача перечисления деревьев с п вершинами — сложная перечисли-
перечислительная задача, поскольку различные деревья имеют различную симме-
симметрию. Мы займемся более простой задачей — перечислением деревьев
с помеченными вершинами. Сопоставим каждой вершине дерева одно
из чисел {1, 2, ..., п} так, чтобы разным вершинам соответствовали
разные числа. На рис. 8.4 изображены все помеченные деревья сп^4
вершин. Последовательность чисел помеченных деревьев с п вершинами
начинается так: 1, 1, 3, 16, ...
Обозначим через Тп число корневых помеченных деревьев с п вер-
вершинами, т.е. число помеченных деревьев, в которых одна из вершин
выделена и названа корнем. Ясно, что число корневых помеченных де-
деревьев с п вершинами в п раз больше числа помеченных деревьев с п
114 Глава 8. Вложенные графы
1 12 3 4 13 2 4 2 1 3
I
1 2 12 4 3 14 2 3 I4
1 2 3 13 4 2 14 3 2 } ?
1 3 2 2 13 4 2 3 14
.—_ .—,—.—. ,—,—,—.
2 1 3 2 14 3 2 4 13 •—1 •
3 12 4 3 2 1 4 ,4
»¦¦ » ¦ « Y . « > 14 2
Рис. 8.4. Помеченные деревья с п вершинами (п < 4)
вершинами: в качестве корня можно выбрать любую из п различных
вершин.
Попробуем найти экспоненциальную производящую функцию
п=1
для числа корневых помеченных деревьев. Выкинем из дерева корень.
Тогда оно распадется на несколько деревьев, число которых равно ва-
валентности корня. Новые деревья тоже можно считать помеченными:
требуется лишь заменить пометки {/ь ..., /j}, ^ < ... < lit на пометки
{1, ...,»}, сохраняя их относительный порядок. Корнем нового дерева
будем считать вершину, соединенную с корнем исходного дерева. Тем
самым каждому корневому помеченному дереву с корнем валентности к
сопоставлено (мульти)множество из к корневых помеченных деревьев.
Мы говорим о мультимножествах, так как среди вновь образованных
деревьев могут встречаться одинаковые.
Из приведенного описания вытекает, что деревья с корнем валентно-
валентности к перечисляются экспоненциальной производящей функцией sTk(s).
Действительно, вклад в коэффициент при s"+1 в функции sTk(s) дают
в точности элементы вида
h\— lk\S
для которых /i + .. . + lk = п. Множество пометок п вершин к деревьев
можно разбить на к подмножеств из h, ..., L пометок -.———г спосо-
Ji!...lfc!
сами. Поэтому число помеченных корневых деревьев из п + 1 вершины
8.1. Перечисление помеченных деревьев 115
с корнем валентности к равно
Суммируя функции ^дТк по всем к, получаем следующее утверждение.
Теорема 8.4. Экспоненциальная производящая функцияТ(з) для чи-
числа помеченных корневых деревьев, перечисляющая их по числу вершин,
удовлетворяет уравнению Лагранжа
T(s) = seT{a). (8.1)
Теорема Лагранжа теперь позволяет нам легко вычислить коэффи-
коэффициенты функции T(s). Можно, например, подсчитать, что Г5 = 625,
Те = 7776. Однако нам хотелось бы иметь явную формулу для их вы-
вычисления. Для получения этой формулы нам понадобится следующее
уточнение теоремы Лагранжа.
Теорема 8.5. Пусть функции(р = (p(s) (<р@) = 0) игр = ip(t) связаны
между собой уравнением Лагранжа
ф) = зф(ф)). (8.2)
Тогда коэффициент при s" в функции ip равен
Применим это уточнение к уравнению (8.1) на функцию Т(з). По-
Получим
Т„ = n\[sn]T(s) = n\-[t"-l]ent = (n- 1)!^
"-1
Таким образом, мы доказали следующий результат.
Теорема 8.6 (Кали). Число помеченных корневых деревьев с п вер-
вершинами равно Т„ = п"".
п
Следствие 8.7. Число помеченных деревьев с п вершинами равно
п-2
116 Глава 8. Вложенные графы
Доказательство теоремы 8.5.
Лемма 8.8 (преобразование вычета при замене переменной).
Пусть функция g(t) такова, что д@) = 0, д'@) Ф 0. Тогда
[з-ЧДз) = [t-l]f{g{t))g'{t).
Действительно, пусть f(s) = f-iys~N + f-N+is~N+1 + ..., g{t) =
)' = о,
так как вычет производной любой функции равен нулю. При п = — 1
что и требовалось.
Коэффициент при зп в производящей функции ср равен
Вычислим последний вычет с помощью леммы 8.8. Для этого перепишем
уравнение Лагранжа (8.2) в виде подстановки
где t = tp(s). Тогда, согласно лемме,
= [гч (« -
Доказательство теоремы закончено.
8.2. Производящие функции 117
8.2. Производящие функции для непомеченных,
помеченных, упорядоченных и циклически
упорядоченных объектов
Мы видели выше, что некоторые последовательности лучше описываются
обыкновенными производящими функциями, а некоторые — экспоненциаль-
экспоненциальными. Впрочем, бывают и исключения. Так, экспоненциальная производя-
производящая функция для числа пилообразных перестановок имеет вид тангенса или
секанса (в зависимости от четности числа элементов в перестановке, раз-
раздел 5.4), а соответствующие обыкновенные производящие функции имеют
замечательное представление в виде непрерывных дробей (раздел 5.5).
Однако общее правило гласит, что экспоненциальные производящие фун-
функции хорошо описывают помеченные объекты, тогда как непомеченным луч-
лучше сопоставлять обыкновенные производящие функции. Объяснение этому
состоит в следующем наблюдении. Пусть у нас имеется какой-то класс объек-
объектов, и мы рассматриваем конечные упорядоченные последовательности объ-
объектов этого класса, а также циклически упорядоченные последовательности
таких объектов.
Предложение 8.9. Если объекты класса помечены и A(s) = $2 ansn/n\ —
экспоненциальная производящая функция для них, то экспоненциальная про-
производящая функция для последовательностей таких объектов имеет вид
1/A — A(s)), а экспоненциальная производящая функция для циклических по-
последовательностей имеет вид 1пA/A — A(s))).
Если объекты класса не помечены и B(s) = ^lbnsn ¦— производящал
функция для ншг, то производящая функция для последовательностей таких
объектов имеет вид 1/A — B(s)), а производящая функция, для циклических
последовательностей имеет вид J2 -^г- 1пA/A — B(s )), где tfk — функция
Эйлера, число чисел от 1 до к взаимно простых с к.
Здесь предполагается, что у объектов имеется какой-то вес (например,
число вершин в графе), по которому происходит перечисление, и вес совокуп-
совокупности объектов равен суммарному весу всех объектов в этой совокупности.
Таким образом, именно при сопоставлении помеченным объектам экспо-
экспоненциальных производящих функций, а непомеченным — обыкновенных, мы
приходим к естественным формулам перечисления производных объектов.
8.3. Перечисление плоских и бинарных деревьев
Очевидно, что всякое дерево можно нарисовать на плоскости так,
чтобы его ребра не имели точек пересечения и самопересечения, от-
отличных от вершин. (При этом ребра можно изображать даже в виде
отрезков прямой, что нам, впрочем, не понадобится в дальнейшем.) Од-
Однако одно и то же дерево можно изображать на плоскости по-разному
118
Глава 8. Вложенные графы
Рис. 8.5. Различные вложения одного дерева в плоскость
(см. рис. 8.5). Формализация понятия различных вложений в плоскость
дается следующим определением.
Определение 8.10. Два вложения дерева в плоскость называются
эквивалентными, если существует гомеоморфизм плоскости, сохраня-
сохраняющий ее ориентацию и переводящий образ первого дерева в образ вто-
второго. Класс эквивалентности вложений деревьев называется плоским
деревом.
Таким образом, одному дереву могут соответствовать несколько
различных плоских деревьев.
Рис. 8.6. Плоские корневые деревья с висячим корнем, имеющие п ребер
A < п < 4)
Перечисление плоских деревьев остается по-прежнему сложной за-
задачей — различные плоские деревья могут иметь различные порядки
симметрии. Для разрушения этой симметрии выберем в дереве вися-
висячий корень (т.е. вершину валентности 1, лист). Ясно, что перевести
данное плоское дерево с фиксированным висячим корнем в себя мож-
можно только тождественным преобразованием. На рис. 8.6 изображены
плоские деревья с висячим корнем с п вершинами B ^ п ^ 5). Деревья
8.3. Плоские и бинарные деревья 119
изображаются растущими от корня вниз. Начало последовательности
1, 1, 2, 5, ... заставляет подозревать, что плоские деревья с висячим
корнем перечисляются числами Каталана.
Отметим, что все деревья сп^б вершинами допускают единствен-
единственное вложение в плоскость,
Теорема 8.11. Число плоских корневых деревьев с висячим корнем,
имеющих п + 2 вершин, равно п-му числу Каталана сп.
Доказательство. В корневом дереве каждой вершине можно сопо-
сопоставить целое число, равное расстоянию (числу ребер) между этой вер-
вершиной и корнем — уровень этой вершины. Сам корень имеет уровень О,
ближайшие к нему вершины — уровень 1 и т. д.
Обозначим число плоских деревьев с висячим корнем (в процессе до-
доказательства такой объект мы будем называть просто деревом), имею-
имеющих п + 2 вершины, через р„. Тогда ро = Pi = 1- Для п > 1 сопоставим
каждому дереву сп+3 вершинами два дерева, первое из которых явля-
является поддеревом исходного, растущим из самого левого ребра, выходя-
выходящего из вершины первого уровня, а второе — оставшимся поддеревом
исходного дерева (см. рис. 8.7). Копия вершины первого уровня исход-
исходного дерева становится корнем первого дерева пары. Если в первом
дереве к + 2 вершин, то во втором дереве п — к + 2 вершин. Наоборот,
имея два дерева с к + 2 тл сп— к+ 2 вершинами, мы можем сопоставить
им дерево сп + 3 вершинами, подклеив корень первого дерева слева
к вершине первого уровня исходного дерева.
Таким образом,
Рп+1 = РоРп + PlPn-1 + ¦¦¦+ РпРО,
и плоские деревья с висячим корнем перечисляются числами Каталана.
Рис. 8.7. Сопоставление плоскому дереву с висячим корнем пары таких же
деревьев
120 Глава 8. Вложенные графы
8.4. Вложение графа в поверхность
Плоские деревья являют собой пример вложения графа в плоскость.
Одно и то же дерево может допускать различные вложения. В то же
время, не каждый граф, как мы увидим ниже, допускает вложение
в плоскость. Мы коснемся и вопроса о вложении графа в произволь-
произвольную двумерную поверхность.
Не вдаваясь в строгое определение двумерной поверхности, мы вос-
воспользуемся классификационной теоремой для таких поверхностей, до-
доказываемой в стандартных начальных курсах топологии.
Теорема 8.12. Всякая (замкнутая ориентируемая двумерная) по-
поверхность гомеоморфна сфере, к которой приклеено конечное число
ручек.
Описание, даваемое этой теоремой, мы и будем считать определе-
определением поверхности.
Определение 8.13. Поверхностью рода g называется двумерная сфе-
сфера с приклеенными к ней g ручками.
В частности, поверхность рода 0 — это просто сфера, поверхность
рода 1 — это тор (см. рис. 8.8).
Рис. 8.8. Поверхности рода g при g = 0, 1, 2
Под графом мы будем понимать граф, содержащий, возможно, пе-
петли и кратные ребра (т.е. две вершины могут быть соединены несколь-
несколькими ребрами). Графы, допускающие вложение в плоскость (планарные
графы), — это в точности те же графы, которые допускают вложение
в сферу. Действительно, если из сферы выколоть точку, то получится
поверхность, гомеоморфная плоскости.
Определение 8.14. Вложением связного графа Г в поверхность М
называется такое изображение графа на поверхности, что
1) каждой вершине графа сопоставлена точка поверхности М, при-
причем различным вершинам сопоставлены различные точки;
8.4. Вложение графа 121
2) каждому ребру графа сопоставлен отрезок несамопересекающей-
ся непрерывной кривой на поверхности М, причем концы этого отрезка
совпадают с вершинами, соединяемыми данным ребром, и отрезки, со-
соответствующие различным ребрам, не пересекаются;
3) дополнение к образу графа Г в М представляет собой несвязное
объединение клеток: двумерных областей, гомеоморфных кругу.
Образ графа при вложении называется вложенным графом (кар-
(картой).
Первые два требования в определении совпадают с требованиями в
определении вложения графа в плоскость. Третье требование является
новым. На самом деле, для изображений графа на сфере оно выпол-
выполняется автоматически: связный граф может разрезать сферу только
на куски, каждый из которых гомеоморфен диску. Для поверхностей
большего рода это уже не так: дополнение к образу графа может иметь
ручки (см. рис. 8.9). Третье требование призвано исключить подобные
вложения из рассмотрения. Мы стремимся к тому, чтобы образ графа
разрезал все ручки поверхности.
Рис. 8.9. Изображения графа на торе, не являющиеся вложениями
В дальнейшем, допуская некоторую нестрогость языка, образ графа
на поверхности мы будем называть просто графом, образы его вершин
(соотв., ребер) — вершинами (соотв., ребрами) графа.
На рис. 8.10 приведены примеры графов, вложенных в тор и поверх-
поверхность рода 2. Уже из этих примеров видно, что один и тот же граф
может быть вложен в различные поверхности. Так, например, граф
«восьмерка», состоящий из одной вершины и двух петель, допускает
вложение и в сферу, и в тор.
Пусть граф Г с У вершинами и Е ребрами вложен в поверхность М
рода д. Обозначим через F число клеток в дополнении к графу Г на
этой поверхности. Тогда числа V, Е, F и д связаны между собой зна-
знаменитым соотношением Эйлера.
122 Глава 8. Вложенные графы
Рис. 8.10. Вложения графов в тор (д = 1) и крендель (д = 2)
Теорема 8.15 (Эйлер).
Величина \д = 2 — 2д называется эйлеровой характеристикой по-
поверхности М.
Соотношение Эйлера позволяет немедленно сформулировать про-
простое ограничение на максимальный род поверхности, в которую можно
вложить данный граф.
Следствие 8.16. Граф с V вершинами и Е ребрами нельзя вложить
в поверхность, род которой превышает (Е - V + 1)/2.
Действительно, согласно соотношению Эйлера
g = (E-V-F + 2)/2 ^ (Е - V + 1)/2,
так как F ^ 1.
Так, например, граф восьмерка нельзя вложить в поверхность рода
больше, чем B - 1 + 1)/2 = 1.
Наша ближайшая цель состоит в том, чтобы показать, что лю-
любой граф можно вложить в некоторую поверхность. Предположим, что
граф Г уже вложен в поверхность М. Рассмотрим окрестность какой-
нибудь его вершины v и отобразим эту окрестность гомеоморфно на
плоскость с сохранением ориентации. Образ такой окрестности пред-
представляет собой круг, в котором выделена вершина графа и конечный
набор выходящих из нее полуребер (см. рис. 8.11). (Некоторые иэ этих
полуребер могут находиться на противоположных концах одного и то-
того же ребра, если в графе имеются петли, примыкающие к выбранной
вершине. Число полуребер, примыкающих к вершине, совпадает с ее ва-
валентностью.) Зададим на множестве полуребер, исходящих из данной
вершины циклический порядок: мы скажем, что полуребро Ь непосред-
непосредственно следует за полуребром а, если оно непосредственно следует за
8.4. Вложение графа
123
/
/
t
1
1
\
\
\
4
ч
с
•ч
Ч
\
\
\
\
1
1
у
Рис. 8.11. Окрестность вершины валентности 4 вложенного графа
полуребром а при движении вдоль границы окрестности против ча-
часовой стрелки. На рис. 8.11 полуребра имеют следующий циклический
порядок:
... У аУ by cydy аУ ....
Таким образом, вложение графа в двумерную поверхность задает
циклический порядок на каждом из множеств полуребер, выходящих
из каждой из его вершин.
Определение 8.17. Графом с вращениями называется граф, в ка-
каждой вершине которого задан циклический порядок выходящих из нее
полуребер.
Пример 8.18. В графе восьмерка из единственной вершины выходят
четыре полуребра. На рис. 8.12 приведены два различных способа за-
задать циклический порядок на этой четверке полуребер (определяемый
ориентацией плоскости). Других способов нет. Как мы видели, пер-
первый способ реализуется вложением восьмерки в плоскость, второй —
ее вложением в тор.
Рис. 8.12. Два различных циклических порядка на множестве полуребер,
выходящих из вершины восьмерки
124
Глава 8. Вложенные графы
Определение 8.19. Вложением графа с вращениями в поверхность
называется вложение графа, задающее тот же самый циклический по-
порядок на каждом из множеств полуребер, выходящих из каждой вер-
вершины, что и в исходном графе.
Оказывается, что не только вложение графа в поверхность опреде-
определяет соответствующий граф с вращениями, но и по графу с вращениями
однозначно восстанавливается поверхность, в которую он вложен.
Теорема 8.20. Для всякого графа с вращениями существует един-
единственная двумерная замкнутая поверхность, в которую его можно
вложить с сохранением вращений.
Рис. 8.13. Два гомеоморфных, но не изотопных вложения восьмерки в тор
Замечание 8.21. Прежде чем доказывать теорему, заметим, что са-
само вложение графа также определено однозначно, если рассматривать
его с точностью до гомеоморфизма поверхности. Можно, однако, при-
привлечь и более тонкую классификацию вложений: с точностью до изото-
изотопии. Два изображенных на рис. 8.13 вложения восьмерки в тор нельзя
перевести друг в друга изотопией тора, хотя они и гомеоморфны. Для
сферы отношения эквивалентности, определенные гомеоморфизмом и
изотопией,совпадают.
Рис. 8.14. Два различных плоских графа, задающие один и тот же сфери-
сферический граф
8.4. Вложение графа
125
Замечание 8.22. Планарные графы и графы, допускающие вложения
в сферу, — это одно и то же. Однако два различных вложения графа
в плоскость могут оказаться одинаковыми как вложения графа в сферу.
Простой пример таких вложений приведен на рис. 8.14. Петля делит
плоскость на две области — внешнюю и внутреннюю, которые нельзя
перевести друг в друга гомеоморфизмом плоскости. На сфере внешняя
и внутренняя области неразличимы.
X
Рис. 8.15. Граф, полученный соединением полуребер ежей (вверху), имею-
имеющих заданные циклические порядки
Доказательство теоремы 8.20. Изобразим вершины и выходящие
из них полуребра графа Г в виде набора «ежей» на плоскости (см.
рис. 8.15). Соединим теперь концы полуребер так, чтобы получить тре-
требуемый граф Г. При соединении некоторые из ребер могут, конечно,
пересечься. Однако мы потребуем, чтобы они не проходили через вер-
вершины графа, и вновь полученные точки пересечения не будут считаться
вершинами. Расставим на ребрах произвольным образом стрелки («ори-
(«ориентируем» их) и обозначим каждое ребро некоторой буквой так, что-
чтобы различные ребра были обозначены различными буквами. По этим
данным мы построим поверхность М, которая не будет зависеть ни
от способа расстановки стрелок, ни от обозначения ребер графа бук-
буквами.
126 Глава 8. Вложенные графы
Построение поверхности М разбивается на два шага. Сначала бу-
будет определен набор клеток, а затем из этих клеток будет склеена сама
поверхность. Мы опишем построение набора клеток для графа с вра-
вращениями, изображенного на рис. 8.15. В общем случае построение пол-
полностью аналогично.
Клетки набора определяются так. Рассмотрим ребро графа Г, обо-
обозначенное буквой а\. Двигаясь по направлению этого ребра, мы прихо-
приходим в вершину 1. В вершине 1 задан циклический порядок полуребер,
и мы выходим из нее, двигаясь по полуребру, непосредственно следую-
следующему за полуребром, по которому мы в нее пришли. Значит, мы выхо-
выходим по полуребру ав и попадаем в вершину 3. Из вершины 3 мы должны
выйти по полуребру аз, следующему за полуребром а%. Петля аз воз-
возвращает нас в вершину 3. На этот раз мы должны выйти из вершины 3
вдоль ребра а% но в направлении, противоположном указанному стрел-
стрелкой. Движение по такому ребру будем обозначать буквой а,. На сей
раз мы возвращаемся в вершину 1, из которой должны уйти по реб-
ребру а4.
Этот процесс продолжается до тех пор, пока наш путь не должен бу-
будет пройти по тому же самому ребру и в том же самом направлении,
в котором мы уже проходили.
Запишем пройденный путь в виде слова, в котором каждое ребро
обозначено соответствующей ему буквой. Получится слово
^ j j
а1аваза6 п4п2п3 а2 .
На следующем шаге путь зацикливается — он должен снова пройти
через ребро oi. Докажем, что это общая ситуация.
Лемма 8.23. Первым повторившимся ребром пути является на-
начальное ребро этого пути.
Действительно, предположим, что это не так, и первым должно по-
повториться ребро х, отличное от начального. Посмотрим на ребро пути,
предшествующее ребру х. Это ребро определено однозначно вращени-
вращением полуребер в начальной точке ребра х. Поэтому предыдущее ребро
должно было повториться раньше ребра х, и мы пришли к противоре-
противоречию.
Сопоставим построенному пути клетку — восьмиугольник, сторо-
стороны которого поименованы буквами пути в том же циклическом по-
порядке. Для построения очередной клетки возьмем какую-нибудь букву
of, ? = 1, ..., 6, а ? { —1, +1}, не вошедшую в уже построенные ци-
8.4. Вложение графа
а4
127
г'
О
а?
Рис. 8.16. Три клетки с поименованными ребрами, из которых склеивается
поверхность вложения графа с рис. 8.15
клы, и построим цикл, проходящий через соответствующее ребро. В на-
нашем примере можно начать, скажем, с буквы as- Тем же способом, что
и в лемме, доказывается, что любые два построенные подобным обра-
образом цикла либо не пересекаются (не имеют общего ребра, пройденного
в одном и том же направлении), либо совпадают. Поэтому все ребра
в графе разбиваются на циклы. Результатом этого разбиения является
набор слов, в котором каждая из букв а\ встречается ровно по одному
разу.
В рассматриваемом примере набор путей имеет вид
-v,
Этому набору путей соответствует набор клеток (см. рис. 8.16), из ко-
которых склеивается требуемая двумерная поверхность. Склейка проис-
происходит по ребрам, обозначенным буквами, отличающимися лишь пока-
показателями степени. Ясно, что вращения, задаваемые построенным вло-
вложением, совпадают с исходными.
Замечание 8.24. Из приведенного построения видно, как строить
гомеоморфизм поверхности, переводящий одно вложение данного гра-
графа с вращениями, в другое. При выбрасывании графа из поверхности
вложения она распадается на клетки. Каждую клетку можно считать
многоугольником, стороны которого занумерованы ребрами графа
(с учетом ориентации). Набор многоугольников не зависит от вложения
128
Глава 8. Вложенные графы
и строится по графу с вращениями, как показано в доказательстве те-
теоремы. Для построения искомого гомеоморфизма его достаточно скле-
склеить из гомеоморфизмов соответствующих клеток, сохраняющих нуме-
нумерацию ребер.
Замечание 8.25. Можно изучать и вложения графов в неориентиру-
емые поверхности. Такое вложение определяет в окрестности каждой
вершины не один циклический порядок на множестве выходящих из
нее полуребер, а пару таких порядков, обратных друг к другу. Указан-
Указанное соответствие не является взаимно однозначным. Граф, для каждой
вершины которого задана пара взаимно обратных вращений на мно-
множестве выходящих из нее полуребер, может быть вложен в различные
неориентируемые поверхности.
Для графа, вложенного в поверхность, определено понятие двой-
двойственного графа, который вложен в ту же самую поверхность. На
рис. 8.17 приведены две пары двойственных графов.
Рис. 8.17. Пары двойственных графов на сфере и торе
Определение 8.26. Пусть граф Г вложен в поверхность М. Двой-
Двойственным графом называется вложенный в М граф Г, вершины ко-
которого находятся во взаимно однозначном соответствии с клетками
графа Г, ребра — во взаимно однозначном соответствии с ребрами
графа Г, причем циклический порядок полуребер, выходящих из дан-
данной вершины двойственного графа, совпадает с циклическим порядком
ребер, ограничивающих соответствующую клетку исходного графа.
Пример 8.27. В качестве примера двойственного графа опишем вло-
вложение графа К7 — полного графа с семью вершинами — в тор. С по-
помощью этого вложения доказывается, что не у всякого графа на торе
8.5. О ЧИСЛЕ СКЛЕЕК МНОГОУГОЛЬНИКА 129
ь
a
Рис. 8.18. Вложение в тор графа, двойственным к которому является
графК7
вершины можно раскрасить в шесть цветов так, чтобы соседние вер-
вершины были раскрашены в различные цвета. Вложение двойственного
графа изображено на рис. 8.18. Тор получается склеиванием противо-
противоположных сторон шестиугольника. Каждая из семи клеток полученного
в результате разбиения граничит со всеми остальными.
8.5. О числе склеек многоугольника
Замкнутые ориентируемые поверхности можно изготавливать из
многоугольников, склеивая их стороны попарно. Например, склеивание
противоположных сторон квадрата дает тор (см. рис. 8.19).
- (} О
Рис. 8.19. Склеивание тора из квадрата
Рассмотрим правильный 2п-угольник и разобьем его стороны на
пары всеми возможными способами. Для каждого такого разбиения
на пары склеим стороны, принадлежащие одной паре (с сохранением
ориентируемости поверхности). Получится замкнутая ориентирован-
ориентированная поверхность. Нас будет интересовать, при скольких способах склей-
склейки полученная поверхность будет иметь род 0, род 1, ..., род д.
Начнем, как обычно, с примеров.
Пусть п = 2 и мы изучаем склейки квадрата. Стороны квадрата
можно разбить на пары тремя способами. Два первых способа при
склейке дают сферу; третье разбиение дает тор (см. рис. 8.20). При
п = 3 имеется 15 способов разбить на пары стороны шестиугольника.
130
Глава 8. Вложенные графы
а
Ь Ь
а
Рис. 8.20. Все возможные склейки сторон квадрата и шестиугольника. Скле-
Склеиваемые стороны помечены одинаковыми буквами
Нетрудно видеть, что пять разбиений в первой строке на рис. 8.20 дают
при склейке сферу, а 10 остальных — тор.
Заметим, что мы считаем различными склейки, переходящие одна
в другую при повороте (или отражении) многоугольника. Это означа-
означает, что мы применили один из способов разрушения симметрии. Можно
считать, например, что стороны (или вершины) многоугольника пере-
перенумерованы. Или, что в многоугольнике выделена начальная сторона
(вершина). Соответствующие пометки не изображаются на рисунке,
чтобы его не загромождать.
Оказывается, что определить род поверхности по склейке несложно.
Образ границы многоугольника при склейке задает вложенный граф
на поверхности. Действительно, дополнение к нему — это одна клет-
клетка, внутренность многоугольника. Тем самым мы знаем число клеток.
Число ребер нам тоже известно: оно равно половине числа сторон 2п-
угольника, т. е. оно равно п. Осталось определить число вершин графа.
Для этого можно, скажем, пометить одинаковыми числами вершины
многоугольника, которые при склейке переходят в одну вершину графа
(см. рис. 8.21). Число различных пометок и будет равно числу вершин
вложенного графа. Так, например, для склейки на рис. 8.21 мы можем
вычислить эйлерову характеристику результирующей поверхности:
и поэтому поверхность является тором.
8.5. О ЧИСЛЕ СКЛЕЕК МНОГОУГОЛЬНИКА
з, ь з
131
Рис. 8.21. Пометка вершин многоугольника. Вершины, переходящие при
склейке в одну вершину вложенного графа, помечены одинаковыми номерами
Таким образом, род результирующей поверхности определяется чи-
числом вершин в графе, склеенном из сторон многоугольника.
Наша задача состоит в том, чтобы перечислить склейки 2п-угольни-
ка, приводящие к поверхности рода д. Эта задача имеет естественную
переформулировку в терминах двойственных графов. Рассмотрим 2п-
ежа на плоскости. Всевозможные разбиения концов этого ежа на пары
определяют различные графы с вращениями, имеющие одну вершину.
Спрашивается, сколько из этих графов имеют род д.
Сопоставим каждому числу п многочлен Т„ = Tn(N) — произво-
производящий многочлен для числа способов склейки сторон 2п-угольника.
Коэффициент при Nv в многочлене Г„ равен числу способов склейки
сторон 2п-угольника, при которых склеенный граф имеет в точности
V вершин. Род поверхности по этим данным определяется однознач-
однозначно. Таким, образом, число способов склейки поверхности рода д из 2п-
угольника равно
[Nn-2°+1]Tn(N).
Выпишем несколько первых многочленов Тп. Положим для удобства
То(ЛГ) = N. Далее, Ti(N) = TV2: единственная возможная склейка «пра-
«правильного двуугольника» дает граф с двумя вершинами и одним ребром
на сфере. Следующие два многочлена были нами фактически посчи-
посчитаны:
T3(N) = 5ЛГ4 + 10ЛГ2.
132 Глава 8. Вложенные графы
Выписывая все возможные склейки правильных 8-ми и 10-угольника,
можно вычислить еще пару многочленов:
T4(N) = UN5 + 70ЛГ3 + 21N,
T5{N) = 42N6 + 420ЛГ4 + 483ЛГ2,
однако уже эти вычисления становятся чрезвычайно трудоемкими.
Нетрудно видеть, что сумма всех коэффициентов многочлена Тп,
т.е. его значение при N — 1, Т„A), равна Bп — 1)!! = 1-3-5-. ..Bп —1).
Действительно, сумма всех коэффициентов многочлена Тп равна числу
всех разбиений на пары сторон 2п-угольника. Число таких разбиений
нетрудно сосчитать. В самом деле, возьмем какую-либо сторону много-
многоугольника. Парную ей сторону можно выбрать 2п — 1 различными спо-
способами. Бели зафиксировать какую-либо из оставшихся 2п — 2 сторон,
то парную ей сторону можно выбрать 2п — 3 различными способами,
и т.д.
Выпишем производящую функцию двух переменных — обычную по
аргументу N и экспоненциальную по аргументу s:
T(N; s) = 1 + 2sT0(N) + 2s2^ + 2S3^ 4-... =
oo
n=0
.n Tn(N)
Bп-1)!Г
В 1986 году было найдено удивительно простое и изящное выраже-
выражение для этой производящей функции.
Теорема 8.28 (Харер, Загир).
Доказательству (к сожалению, неполному) этой теоремы посвящен
следующий раздел.
Замечание 8.29. Вывод производящей функции T(N; s) не был глав-
главной целью работы Харера и Загира. Сформулированная выше теорема
послужила основным техническим результатом при вычислении вир-
виртуальной эйлеровой характеристики пространства модулей гладких
комплексных кривых фиксированного рода д.
8.6. Теорема Харера-Загира 133
Проверим, что приведенная в теореме формула действительно пра-
правильно дает первые коэффициенты производящей функции. Имеем,
/ЛГ(ЛГ-1)(ЛГ-2) N(N-1)N NN(N
\ 3! + 2! 1! + 1! 2!
JV(iV+l)(JV+2) я
| s
= 1 + 2ЛГ5 + 2ЛГ252 + 2^
и по крайней мере начальные члены разложения совпадают с уже вы-
вычисленными нами ранее.
8.6. Доказательство теоремы Харера-Загира
Обратим внимание, во-первых, на последовательность коэффициен-
коэффициентов при старших степенях многочленов Тп. Эта последовательность на-
начинается так: 1, 1, 2, 5, 14, ..., и у нас есть основания предположить,
что она совпадает с последовательностью чисел Каталана.
Лемма 8.30. Степень многочлена Тп равна п+1. Коэффициент при
Nn+1 в многочлене Tn(N) равен сп, п-му числу Каталана.
Доказательство. По формуле Эйлера число вершин в графе на скле-
склеенной поверхности рода д определяется иэ равенства
откуда
V=n + l-2g^n + l,
так как род д неотрицателен. Последнее неравенство превращается
в равенство тогда и только тогда, когда д = 0, т. е. склеенная поверх-
поверхность — сфера.
134
Глава 8. Вложенные графы
Рис. 8.22. Склейка ручки из перемежающихся пар сторон
Назовем две пары сторон многоугольника перемежающимися, ес-
если между двумя сторонами из первой пары есть сторона из второй
пары, в каком бы направлении мы ни обходили границу многоуголь-
многоугольника. Другими словами, две пары сторон перемежаются, если отрезки,
соединяющие середины каждой пары сторон, пересекаются. Если в раз-
разбиении сторон на пары есть перемежающиеся пары, то их склейка дает
ручку (см. рис. 8.22), и результирующая поверхность не может являть-
являться сферой. Наоборот, если в разбиении нет перемежающихся пар, то
результирующая поверхность — сфера. Действительно, в таком раз-
разбиении можно выбрать пару смежных склеивающихся друг с другом
сторон. Их склейка дает многоугольник с меньшим числом сторон, ко-
которые разбиты на неперемежающиеся пары, и мы можем действовать
по индукции.
Разбиения сторон 2п-угольника на пары, в которых нет перемежа-
перемежающихся пар, находятся во взаимно однозначном соответствии с мно-
множеством правильных скобочных структур из п пар скобок. Действи-
Действительно, зафиксируем какую-либо начальную вершину многоугольника
и будем двигаться от нее вдоль границы многоугольника против ча-
часовой стрелки. Каждой проходимой стороне многоугольника сопоста-
сопоставим левую или правую скобку по следующему правилу: если проходи-
проходимая сторона — первая из пары, то мы сопоставляем ей левую скобку,
в противном случае — правую (см. рис. 8.23). Ясно, что получивша-
получившаяся скобочная структура будет правильной, и что любую правильную
скобочную структуру можно получить ровно один раз.
•.6. Теорема Харера-Загира.
а
135
а.
)
bddccbaa
Рис. 8.23. Разбиение сторон 8-угольника на пары без перемежающихся пар
и соответствующая скобочная структура
Лемма доказана.
Дальнейшее доказательство теоремы Харера-Загира разбивается
на две части. Первую его часть составляет следующая лемма.
Лемма 8.31. Рассмотрим выражение t(N, n) — 12„^и\\ как функ-
функцию от п при фиксированном N. Тогда t(N, п) — многочлен от п
степени N — 1.
Первое доказательство этого факта, хотя и не очень сложное, ис-
использует нетривиальную технику интегрирования по пространству эр-
эрмитовых матриц. Недавно появилось чисто комбинаторное доказатель-
доказательство, принадлежащее Бодо Лассу. Оно, однако, тоже довольно трудо-
трудоемкое. Я отсылаю заинтересовавшегося читателя к оригинальным ра-
работам.
Оставшаяся часть доказательства носит вполне комбинаторный ха-
характер.
Предположим, что вершины 2п-угольника раскрашены в несколько
цветов. Будем говорить, что склейка сторон многоугольника согласо-
согласована с раскраской, если она склеивает только вершины одинакового
цвета.
Лемма 8.32. Число Tn{N) есть в точности число склеек сторон
2п-угольника, согласованных с раскраской его вершин в {не более, чем)
N цветов.
136 Глава 8. Вложенные графы
Доказательство. Действительно, пусть в результате склейки гра-
граница многоугольника переходит в граф с V вершинами. Раскрасим ка-
каждую вершину графа в один из N цветов. Каждая такая раскраска
задает раскраску вершин исходного многоугольника, согласованную
с выбранной склейкой. Всего же раскрасить V вершин графа в N цве-
цветов можно в точности Nv способами. Поэтому общее число склеек,
согласованных с раскрасками, есть сумма чисел Nv по всем склейкам,
что в точности совпадает с определением многочлена Tn(N).
Введем функцию Tn(N) — число склеек 2п-уголышка, согласован-
согласованных с раскраской его вершин в точности в N цветов. Тогда
Тп(Ю = ? ( , )Tn{L). (8.3)
Действительно, L цветов могут быть выбраны из N цветов в точности
A) способами. При этом T0(N) = T1(N) = ... = TN-2(N) = 0, так
как, в силу леммы 8.30, склеек, согласованных с раскраской вершин
2п-угольника более чем вп + 1 цвет, не существует.
Функция t(N, п) — . "_ .([ является многочленом по п степени
N - 1, причем мы знаем N — 1 корень этого многочлена: п = 0, 1, 2,
..., N -2. Поэтому существует такая постоянная А^, что
i(N, п) = ANn(n - 1)... (п - N + 2) =
Подставляя полученное выражение в формулу (8.3), мы получаем
В частности, старший коэффициент по N этого многочлена равен
С другой стороны, по лемме 8.30, этот коэффициент равен n-му числу
Каталана:
8.7. Задачи " 137
2n
Отсюда Л„+1 = —, и поэтому
Эта формула в точности совпадает с формулой для разложения фун-
Y^jj j по степеням s:
N
00 N <ы
Теорема Харера - Загира доказана.
8.7. Задачи
8.1. Докажите, что число различных нумераций вершин данного де-
дерева с п ребрами числами {1,2, ...,п+1}вп раз больше числа раз-
различных нумераций его ребер числами {1, 2, ..., п}.
8.2. Бинарным деревом называется дерево, в котором валентность
каждой вершины равна 1 или 3. Докажите, что число вершин в би-
бинарном дереве четно. Докажите, что число плоских бинарных деревьев
с висячим корнем, имеющих 2п вершин, равно (п— 1)-му числу Каталана
Сп-1-
8.3. Докажите, что производящая функция для числа тернарных
(т.е. таких, в которых валентность каждой вершины равна единице
или четырем) плоских деревьев с 2(п + 1) листьями и висячим корнем
удовлетворяет уравнению Т(х, у, z) = xTyTzT + 1. Выведите отсюда,
что это число равно tn = 2n1+1 ( *).
8.4. Установите взаимно однозначное соответствие между плоскими
бинарными деревьями с In вершинами и плоскими корневыми деревья-
деревьями с п + 1 вершиной.
8.5. Перечислите корневые помеченные леса. (Лес — это граф, ка-
каждая связная компонента которого — дерево.)
8.6. Оцените минимальный и максимальный род поверхности, в ко-
которую можно вложить граф Кп — полный граф с п вершинами. (Пол-
(Полным называется граф, в котором любые две вершины соединены в точ-
точности одним ребром.)
138 Глава 8. Вложенные графы
8.7. Существуют ли вложения графа Петерсена (см. рис. 8.24) в а)
тор; б) поверхность рода два?
Рис. 8.24. Граф Петерсена
8.8. Можно ли вложить в тор граф К%, составленный из ребер че-
четырехмерного куба?
8.9. С помощью формулы Эйлера докажите простую часть теоремы
Куратовского: графы К5 и Кэ,з нельзя вложить в сферу.
8.10. Можно ли вложить в проективную плоскость графы а) К5;
б) К3:3'? Если да, то приведите соответствующие вложения.
8.11. Пусть Г — это граф, образованный ребрами икосаэдра. Из ка-
каждой вершины икосаэдра выходит 5 ребер в естественном цикличе-
циклическом порядке ...1!^2>-3>-4>-5!>- 1... Заменим естественный
циклический порядок выходящих ребер в каждой вершине на порядок
...1 >-3>-5>-2>-4>- 1... («звездчатый икосаэдр»). Вычислите род
поверхности, в которую вкладывается звездчатый икосаэдр.
8.12. Докажите, что склейка сторон многоугольника дает сферу
в том и только в том случае, если граф, образованный сторонами мно-
многоугольника на склеенной поверхности, является деревом.
8.13. Докажите, что род поверхности, которую можно склеить из
2п-угольника, не превосходит [^-].
8.14. Выпишите производящую функцию для числа склеек 2п-уголь-
ника, дающих тор.
8.15. Докажите, что при четном п многочлен Tn(N) нечетен и нао-
наоборот.
8.16. Опишите все попарно неизотопные вложения восьмерки в тор.
Заключительные замечания и указания
к библиографии
На русском языке имеется несколько монографий, в которых изло-
изложение метода производящих функций занимает одно из центральных
мест. В первую очередь следует отметить две книги [3] и [7] под оди-
одинаковым названием «Перечислительная комбинаторика». Помимо бога-
богатого материала (который частично перекрывается с изложенным в на-
настоящей книге и в значительной степени дополняет его) там приведено
большое количество исторических сведений и обширная библиография.
Поэтому мы позволили себе не сопровождать изложение исторически-
историческими замечаниями, чтобы не отвлекать внимание читателя. Приводимый
ниже список литературы также не претендует на полноту и предна-
предназначен, в первую очередь, для отсылки к публикациям, не входившим
ранее в монографии.
Несмотря на то, что с момента первого издания книги Полна и Се-
ге [4] прошло уже три четверти века, она по-прежнему остается одной
из лучших книг по комбинаторике и, в том числе, по методу произ-
производящих функций. В настоящую книгу включено много задач из этого
сборника. Частично задачи взяты также из уже упоминавшихся книг [3]
и [7], других источников, а также придуманы мной самостоятельно.
Перечислительные аспекты теории графов описаны в [8]. Из других
изданий на русском языке отметим книгу Сачкова [6] и уже несколько
устаревшую книгу Риордана [5].
Вывод уравнений на производящие функции для языков, порожден-
порожденных контекстно-свободными грамматиками, следует подходу, изложен-
изложенному в [11] (см. также ссылки там). Связь этого подхода с уравнением
Лагранжа подробно описана в [16, 17]. Треугольник Бернулли-Эйлера
введен и подробно изучен В. И. Арнольдом [9, 10, 1, 2] в связи с иссле-
исследованием различных функциональных топологических пространств.
Все, что связано с представлением производящих функций в виде
непрерывных дробей, я взял из работ Флажоле [12, 13]. Изложение во-
вопросов асимптотики коэффициентов и ее связи с характером особен-
особенностей функций следует [14]. Доказательство теоремы Харера-Загира
воспроизводит — с существенными купюрами — исходное доказатель-
доказательство [15]. Чисто комбинаторное доказательство см. в [18].
СПИСОК ЛИТЕРАТУРЫ
[1] Арнольд В. И. Исчисление змей и комбинаторика чисел Бернулли,
Эйлера и Спрингера групп Кокстера // УМН. 1992. т. 47, вып. 1.
С. 3-45.
[2] Арнольд В. И. Сравнения для чисел Эйлера, Бернулли и Спринге-
Спрингера групп Кокстера // Изв. РАН. Сер. матем. 1992. Т. 56, вып. 5.
С. 1129-1133.
[3] Гульден Я., Джексон Д. Перечислительная комбинаторика. М.:
Наука, 1990.
[4] Полна Г., СегеГ. Задачи и теоремы из анализа: В 2 т. М.: Наука,
1978.
[5] РиорданДж. Введение в комбинаторный анализ. М.: ИЛ, 1963.
[6] Сачков В. Н. Введение в комбинаторные методы дискретной ма-
математики. М.: Наука, 1982.
[7] Стэнли Р. Перечислительная комбинаторика. М.: Мир, 1990.
[8] ХарариФ., ПалмерЭ. Перечисление графов. М.: Мир, 1976.
[9] Arnold V. I. Bernoulli - Euler updown numbers of functions singulari-
singularities, their arithmetics and combinatorics // Duke Math. J. 1991. V. 63.
P. 537-555.
[10] Arnold V. I. Springer numbers and modification spaces // J. Algebraic
Geometry. 1992. V. 1. P. 197-214. [Русский перевод: Числа Сприн-
Спрингера и пространства морсификаций. В книге В. И. Арнольда Из-
Избранное (М.: Фазис, 1997. С. 505-524).]
[11] Delest M.-P., Viennot G. Algebraic languages and polyminoes enumer-
enumeration I/ Theoretical Computer Science. 1984. V. 34. P. 169-206. [Рус-
[Русский перевод: ДелестМ.-П., ВьенноЖ. Алгебраические языки и
перечисление полимино // Киб. сборник, нов. серия. Вып. 26. М.:
Мир, 1989. С. 113-156.]
[12] Flajolet P. Combinatorial aspects of continued fractions // Discrete
Mathematics. 1980. V.32. P. 125-161.
[13] Flajolet P. On congruences and continued fractions for some classical
combinatorial quantities // Discrete Mathematics. 1982. V. 41. P. 145-
153.
[14] Flajolet P., Oldyzko A. Singularity Analysis of Generating Functions
II SIAM J. Disc. Math. (May 1990). V. 3, 2. P. 216-240.
[15] Harer J., ZagierD. The Euler Characteristic of the Moduli Space of
Curves I/ Inv. Math. 1986. V. 85. P. 457-485.
СПИСОК ЛИТЕРАТУРЫ - 141
[16] LandoS. К., Zvonkin А. К. Meanders // Selecta Mathematica Soviet-
ica 1992. V. 11, 2. P. 117-144.
[17] LandoS. K., Zvonkin A. K. Plane and protective meanders // Theo-
Theoretical Computer Science. 1993. V. 117. P. 227-241.
[18] Lass B. Demonstration combinatoire de la formule de Harer-Zagier I I
С R. Acd. Sci. Paris. Serie I. 2001. V. 333, no. 3. P. 155-160.
Предметный указатель
Алгебро-логарифмическая особая
точка 57
Асимптотика 49
Бернулли - Эйлера треугольник 64
Беспорядок 102
Бинарное дерево 137
Бином Ньютона 18
Валентность 112
Вершина графа 112
Вложение графа 120
Вложенный граф 121
Гипергеометрическая последова-
последовательность 51
Грамматика контекстно-свободная
44
- с однозначным выводом 45
Граф 112
- вложенный 121
- двойственный 128
-полный 137
-с вращениями 123
-связный 113
Гурвица функция 62
Двойственный граф 128
Дерево 113
- бинарное 137
-плоское 118
Дзета функция Римана 102
Диагональная триангуляция 33
Диаграмма Ферре 90
- Юнга 90
Дика путь 35
-треугольник 63
-язык 40
- - второго порядка 48
Дирихле производящая функ-
функция 103
Длина слова 40
Интеграл производящей функции
19
Инцидентности отображение 112
Каталана число 31
Квазимногочлен 29
Критическая точка 66
Критическое значение 66
Лагранжа теорема 46
- уравнение 43, 46
Лес 137
Лист дерева 118
Метод стационарной фазы 12
Мёбиуса последовательность 104
- функция 104
Морсовский многочлен 66
Моцкина путь 37
- число 37
-язык 48
Мультиномиальный коэффициент
95
Мультипликативная последова-
последовательность 107
Непрерывная дробь 73
Неразложимое слово 43
Обратная функция 21
Особая точка алгебро-логарифми-
ческая 57
Отображение инцидентности 112
Палиндром 48
Паскаля треугольник 60
Перестановка пилообразная 67
Петля 112
Предметный указатель
143
Пилообразная перестановка 67
Плоское дерево 118
Полный граф 137
Последовательность Мёбиуса 104
- мультипликативная 107
Правила вывода в языке Дика 41
Правило вывода 44
Правильная скобочная структура
31
Произведение Адамара 29
Производная производящей функ-
функции 19
Производящая функция 14
-Дирихле 103
-экспоненциальная 62
- языка 41
Производящий многочлен 15
Производящий ряд 14
Пустое слово 40
Путь Дика 35
- Моцкина 37
Разбиение 87
- множества 94
-симметричное 90
Разложение 87
Ребро графа 112
Римана дзета функция 102
Связный граф 113
Симметричные разбиения 90
Система меандров 58
Скобочная структура правильная
31
Слово 40
- пустое 40
Счастливый билет 9
Тангенциальные числа 70
Теорема Лагранжа 46
-Харера-Загира 132
-Эйлера 121
Треугольник Бернулли - Эйлера 64
- Дика 63
- Паскаля 60
Уравнение Лагранжа 43, 46
Ферре диаграмма 90
Функция Гурвица 62
- Мёбиуса 104
Харера-Загира теорема 132
Цикл в графе 113
Числа Эйлера 71
Число Кат алана 31
- Моцкина 37
-сочетаний 18
Эйлера теорема 121
Эйлера числа 71
Эйлерова характеристика 122
Экспоненциальная производящая
функция 62
Юнга диаграмма 90
Язык 40
- Дика 40
- - второго порядка 48
- правила вывода 41
- Моцкина 48