Курс идет по средам в 18.30 в ИППИ.

Лекция 1. Множества, основные операция над множествами. Круги Эйлера. Комбинаторные объекты и комбинаторные числа. Основные правила комбинаторики: правило суммы и правило произведения. Факториал и убывающая факториальная степень. Базовые комбинаторные объекты: размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями.
Литература: [1, §2.1, 2.2, 2.3], [2, гл. 1, 2], [5, §1.1, 1.4, 2.1] [8, гл. 1].
Лекция
Семинар задачи
Решения задач
Видео (1, 2, 3)

Лекция 2. Биномиальные коэффициенты: основные свойства и отношения. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи. Неравенство Бонферрони (б/д).
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция
Семинар
Домашнее задание по лекциям 1-2

Лекция 3. Разбиение натуральных чисел на слагаемые. Примеры задач. Рекуррентные соотношения для количества разбиений. Диаграммная техника. Формула Харди-Рамануджана (б/д). Количество разбиений конечного множества. Числа Стирлинга и Белла.
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция
Семинар
Видео

Лекция 4. Выравнивание последовательностей. Рекуррентные соотношения для числа выравниваний и . Решение задачи о выравнивании последовательностей при помощи динамического программирования.
Литература: [5, §7.1, 13.1].
Лекция

Лекция 5. Числа Фибоначчи: пример возникновения задачи, рекуррентное соотношение. Последовательности, задаваемые линейными рекуррентными соотношениями с постоянными коэффициентами (ЛРСПК). Частное решение ЛРСПК, лемма о линейной комбинации частных решений ЛРСПК. Общее решение ЛРСПК. Характеристический многочлен ЛРСПК. Теоремы об общем решении ЛРСПК. Линейные неоднородные рекуррентные соотношения с постоянными коэффициентами (ЛНРСПК), их частные и общие решения. Теорема об общем решении ЛНРСПК. Теорема о частном решении ЛНРСПК.
Литература: [2, гл. 7], [5, §6.1, 6.2].
Видео
Лекция
Домашнее задание по занятиям 3-5

Лекция 6. Графы: формальное определение и примеры. Основные подструктуры в графах (подграфы, порожденные подграфы, клики, независимые и доминирующие множества, паросочетания, цепи, циклы) и некоторые специальных классы графов (двудольные графы, полные графы, деревья). Изоморфизм графов. Связность графов, компоненты связности. Формула Кэли. Кодирование Прюфера. Теорема Рамсея (для графов для случая двух цветов). Числа Рамсея.
Видео
Лекция
Семинар

Лекция 7. Предмет теории вероятностей. Краткий повтор основных определений и концепций. Вероятностный метод в комбинаторике. Простая вероятностная нижняя оценка чисел Рамсея. Случайные графы. Понятие о «почти всех» объектах.
Видео (часть 1, 2)

Лекция 8. Применение вероятностного метода. Теорема Эрдёша о существовании графов с большим обхватом и одновременно большим хроматическим числом. Теорема о нижней оценке числа скрещиваний графа с большим числом рёбер.

Лекция 9. Локальная лемма Ловаса: общий и симметричный случаи. Применение для получения оценки диагональных чисел Рамсея.

[1] Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел. Сборник задач для математических школ. — М.: МЦНМО, 2009.
[2] Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.
[3] В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. — М.: Либроком, 2009.
[4] Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
[5] А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ). — М.: Макс-пресс, 2005.
[6] Б. А.Севастьянов Курс теории вероятностей и математической статистики. М.: Наука. Гл. ред. физ.-мат. лит., 1982.— 256 с.
[7] Ф. Харари, Теория графов. — М.: Либроком, 2009.
[8] А. Х. Шахмейстер, Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
[9] Г. Эндрюс, Теория разбиений. — М.: Наука. 1982.