Читать онлайн «Лекции по комбинаторике, 1-й курс»
Автор С. К. Ландо
Оглавление
Программа курса 5
ЛЕКЦИЯ 1. 7
1. 1. Задача о числе счастливых билетов 7
1. 2. Общие положения 10
1. 3. Производящие функции и действия над ними 11
1. 4. Элементарные производящие функции 12
ЛЕКЦИЯ 2. 14
2. 1. Деление производящих функций 14
2. 2. Производящая функция для последовательности Фибоначчи. 15
2. 3. Числа Каталана 15
2. 3. 1. Производящая функция для последовательности
Каталана 15
2. 3. 2. Правильные скобочные структуры 16
2. 3. 3. Диагональные триангуляции многоугольников. ... 17
2. 3. 4. Арифметические свойства чисел Каталана 18
2. 4. Рациональные производящие функции 19
2. 5. Дифференцирование и интегрирование производящих
функций 20
Задачи 21
ЛЕКЦИЯ 3. Число разбиений числа п. Теорема Эйлера и
диаграммы Юнга. 22
Задачи 27
ЛЕКЦИЯ 4. Формальные грамматики с однозначным
выводом. Теорема Лагранжа 29
Задачи 35
ЛЕКЦИЯ 5. 37
5. 1. Формулы включения-исключения 37
5. 2. Аналитические свойства функций, представляемых
степенными рядами, и асимптотика коэффициентов 39
Задачи 43
ЛЕКЦИЯ 6. Производящие функции нескольких
переменных. 45
6. 1. Треугольник Паскаля 45
6. 2. Экспоненциальные производящие функции 46
3
6. 3. Экспоненциальная производящая функция для
треугольника Паскаля 46
6. 4. Треугольник Бернулли-Эйлера 47
6. 5. Еще одна интерпретация треугольника Бернулли-Эйлера:
морсовские многочлены и up-down перестановки 48
6. 6. Вывод производящих функций для сторон Бернулли и
Эйлера 50
Задачи 51
ЛЕКЦИЯ 7. Графы и хроматические функции 53
7.
1. Раскраски графов 53
7. 2. Хроматическая функция 54
7. 3. Теорема о хроматическом многочлене 57
7. 4. Планарные и плоские графы 59
ЛЕКЦИЯ 8. Перечисление деревьев. 60
8. 1. Корневые и отмеченные деревья 60
8. 2. Уточнение теоремы Лагранжа 62
Задачи 64
ЛЕКЦИЯ 9. Вложенные графы 65
9. 1. Вложение графа в поверхность 65
9. 2. Теорема о вложении 67
Задачи 71
ЛЕКЦИЯ 10. 0 числе склеек многоугольника. 72
10. 1. Примеры склеек 72
10. 2. Производящая функция для склеек 73
10. 3. Теорема Харера-Загира 74
Задачи экзамена 77
4
Программа курса
1. Формальные степенные ряды и производящие функции.
2. Действия над формальными степенными рядами: сложение,
умножение, деление, подстановка формального степенного ряда в
формальный степенной ряд.
3. Производящие функции для элементарных последовательностей
(числа Фибоначчи, Каталана,... ).
4. Рекуррентные соотношения и производящие функции.
5. Дифференцирование и интегрирование формальных рядов.
6. Число разбиений числа п; теорема Эйлера и диаграммы Юнга.
7. Формулы включения-исключения.
8. Формальные грамматики с однозначным выводом; производящая
функция для числа слов в языке, порожденном формальной
грамматикой с однозначным выводом.
9. Теорема Лагранжа.
10. Аналитические свойства функций, представляемых степенными
рядами, и асимптотика коэффициентов.
11. Производящие функции двух переменных.
12. Деревья; производящая функция для числа деревьев.
13. Плоские деревья и производящая функция для них.
14. Плоские графы; теорема Куратовского; теорема Эйлера.
15. Хроматические многочлены.
16.
