Discrete mathematics, 1st year, 2009 (Spring)

Дискретная математика. 2008/2009 учебный год.

Лектор: С.К.Ландо.
Упражнения проводят: С.К.Ландо, П.Н.Пятов, Г.Л.Рыбников.
Программа курса. Записки лекций. Задачи семинаров. Контрольные и экзамен.

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

Элементы перечислительной комбинаторики.
1. Элементарные производящие функции. Перестановки и сочетания. Бином Ньютона. Экспонента. Производящие функции и действия над ними. Дифференцирование и интегрирование производящих функций. Алгебра и топология формальных степенных рядов.
2. Рациональные производящие функции. Геометрическая прогрессия. Последовательность Фибоначчи. Рекуррентные соотношения и рациональные производящие функции. Произведение Адамара рациональных производящих функций. Асимптотика коэффициентов рациональных производящих функций.
3. Производящие функции путей на графах. Пути в графах. Пути, перечисляемые рациональными производящими функциями. Числа Каталана.
4. Производящие функции нескольких переменных. Треугольник Паскаля. Экспоненциальные производящие функции. Треугольник Дика. Треугольник Бернулли-Эйлера и перечисление up-down перестановок. Числа Эйлера в треугольнике Дика с кратностями. Производящая функция для треугольника Дика с кратностями.
5. Теневое исчисление. Биномиальные последовательности и их применение. Биномиальные последовательности и сдвиги. Явное построение биномиальных последовательностей. Последовательности Шеффер. Коалгебра многочленов.
Графы, их перечисление и инварианты.
1. Перечисление деревьев и числа Гурвица. Перечисление помеченных деревьев. Леса и многочлены Абеля. Графы и перестановки. Числа Гурвица. Уравнение транспозиции. Перечисление посаженных лесов.
2. Соотношение удаление-стягивание и теорема Татта. Графы, изоморфизм и инварианты. Хроматический многочлен. Топология графов. Многочлен Пенроуза. Соотношение Татта. Теорема Татта. Примеры инвариантов Татта.
3. Алгебра Хопфа графов. Структура алгебры и коалгебры на пространстве графов. Примитивные элементы. Факторбиалгебры.
Языки, автоматы, грамматики.
1. Языки и конечные автоматы. Язык Дика. Конечные автоматы. Автоматы со стеком.
2. Формальные грамматики с однозначным выводом. Правила вывода в языке Дика. Формальные грамматики с однозначным выводом. Представление производящих функций в виде непрерывных дробей.