На главную страницу НМУ

С.К.Ландо

Комбинаторика (весна 1993 года)

Записки лекций (Lecture notes)

Gzipped postscript (289K)
Zipped postscript (289 K)

Программа курса

1. Формальные степенные ряды и производящие функции.
2. Действия над формальными степенными рядами: сложение, умножение, деление, подстановка формального степенного ряда в формальный степенной ряд.
3. Производящие функции для элементарных последовательностей (числа Фибоначчи, Каталана,...).
4. Рекуррентные соотношения и производящие функции.
5. Дифференцирование и интегрирование формальных рядов.
6. Число разбиений числа n; теорема Эйлера и диаграммы Юнга.
7. Формулы включения-исключения.
8. Формальные грамматики с однозначным выводом; производящая функция для числа слов в языке, порожденном формальной грамматикой с однозначным выводом.
9. Теорема Лагранжа.
10. Аналитические свойства функций, представляемых степенными рядами, и асимптотика коэффициентов.
11. Производящие функции двух переменных.
12. Деревья; производящая функция для числа деревьев.
13. Плоские деревья и производящая функция для них.
14. Плоские графы; теорема Куратовского; теорема Эйлера.
15. Хроматические многочлены.
16. Графы на поверхностях (эскизы); эйлерова характеристика.