Лекции о производящих функциях [С. А. Ландо] (pdf) читать постранично

УДК 519.1
ББК 22.176
Л22

Л22

Ландо С. К.
Лекции о производящих функциях. — 3-е изд., испр. — М.:
МЦНМО, 2007. — 144 с.
ISBN 978-5-94057-042-4
Настоящая книга посвящена производящим функциям — языку, на котором говорит современная перечислительная комбинаторика. Этот язык
используется и во многих других областях математики и математической
физики. Книга предназначена, в первую очередь, для студентов младших
курсов физико-математических специальностей. В ней разобрано много
примеров и содержится большое количество задач для самостоятельного
решения.
Предыдущее издание книги вышло в 2004 г.

ББК 22.176
Учебное издание
Ландо Сергей Константинович
Лекции о производящих функциях
Иллюстрации М. Н. Вялый
Подписано в печать 28.06.2007 г. Формат 60 × 90 1/16. Бумага офсетная № 1.
Печать офсетная. Печ. л. 9. Тираж 1000 экз. Заказ №
.
Издательство Московского центра непрерывного
математического образования
119002, Москва, Большой Власьевский пер., 11. Тел. (495)-241-74-83.
Отпечатано с готовых диапозитивов
в ФГУП «Полиграфические ресурсы».
Книги издательства МЦНМО можно приобрести
в магазине «Математическая книга», Большой Власьевский пер., д. 11.
Тел. (495) 241-72-85. E-mail: biblio@mccme.ru

ISBN 978-5-94057-042-4

c Ландо С. К., 2007.
c МЦНМО, 2007.

Оглавление
Предисловие

5

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

6

Глава 1. Формальные степенные ряды и производящие функции. Действия над формальными степенными рядами. Элементарные производящие функции
1.1 Счастливые билеты . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Производящие функции . . . . . . . . . . . . . . . . . . . . . .
1.4 Элементарные производящие функции . . . . . . . . . . . . .
1.5 Дифференцирование и интегрирование . . . . . . . . . . . . .
1.6 Алгебра и топология формальных степенных рядов . . . . . .
1.7 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
12
13
16
17
18
19

Глава 2. Производящие функции для
тельностей
2.1 Геометрическая прогрессия . . . . .
2.2 Последовательность Фибоначчи . .
2.3 Рекуррентные соотношения . . . . .
2.4 Произведение Адамара . . . . . . . .
2.5 Числа Каталана . . . . . . . . . . . .
2.6 Задачи . . . . . . . . . . . . . . . . .

21
21
22
24
26
28
33

Глава 3. Формальные грамматики с
Теорема Лагранжа
3.1 Язык Дика . . . . . . . . . . . . . .
3.2 Правила вывода . . . . . . . . . . .
3.3 Формальные грамматики . . . . .
3.4 Уравнение Лагранжа . . . . . . . .
3.5 Задачи . . . . . . . . . . . . . . . .

известных последова.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

однозначным выводом.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

Глава 4. Аналитические свойства функций, представляемых
степенными рядами, и асимптотика их коэффициентов
4.1 Степенные оценки . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Асимптотика гипергеометрических последовательностей . . .
4.3 Асимптотика и уравнение Лагранжа . . . . . . . . . . . . . . .
4.4 Асимптотика и характер особенностей . . . . . . . . . . . . . .
4.5 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37
37
38
40
43
44

46
46
48
53
54
55

4

Оглавление

Глава 5. Производящие функции нескольких переменных
5.1 Треугольник Паскаля . . . . . . . . . . . . . . . . . . . . .
5.2 Экспоненциальные производящие функции . . . . . . . . .
5.3 Треугольник Дика . . . . . . . . . . . . . . . . . . . . . . .
5.4 Треугольник Бернулли—Эйлера . . . . . . . . . . . . . . .
5.5 Многочлены Бернулли . . . . . . . . . . . . . . . . . . . . .
5.6 Непрерывные дроби . . . . . . . . . . . . . . . . . . . . . .
5.7 Числа Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8 Сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9 Обыкновенные дифференциальные уравнения . . . . . . .
5.10 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

57
57
59
61
62
69
71
76
77
80
82

Глава 6. Разбиения и разложения
6.1 Разбиения и разложения . . . .
6.2 Тождество Эйлера . . . . . . .
6.3 Непрерывные дроби . . . . . .
6.4 Задачи . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

86
86
90
93
96

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Глава 7. Производящие функции Дирихле
чения-исключения
7.1 Принцип включения-исключения . . . . .
7.2 Функции Дирихле . . . . . . . . . . . . . .
7.3 Обращение Мёбиуса . . . . . . . . . . . .
7.4 Мультипликативные последовательности
7.5 Задачи . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

и формулы