Основы комбинаторики

Современная комбинаторика, таким образом, это своего рода основа основ: это и красивейшая теория с массой нетривиальных задач и методов, но это и прекрасная база для приложений в computer science, в анализе сложных сетей, в теории кодирования и криптографии, в биоинформатике и др. В курсе мы познакомим слушателей с наиболее важными областями и инструментами современной комбинаторики, причем многие темы курса по сути уникальны: здесь не только классические комбинаторные величины и тождества, но также и общая теория обращения Мебиуса, и диаграммы Юнга, и рекурсия, и производящие функции. Это позволит нам в дальнейших курсах выйти на реальные приложения в анализе таких сложных сетей, как Интернет, социальные, биологические сети, сети межбанковских взаимодействий и др.

Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.

Курс состоит из 11 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания (тесты и задачи с ответом). Экзамен также состоит из теста и задач с ответом. Для успешного прохождения курса необходимо в каждом задании набрать не менее 50% от общего числа баллов.

1. Н.Я. Виленкин. Комбинаторика. – М.: Наука, 1969.
2. Н.Б. Алфутова, А.В. Устинов. Алгебра и теория чисел (сборник задач). – М.: МЦНМО, 2002.
3. М. Холл. Комбинаторика. – М.: Мир, 1970.
4. М.Айгнер Комбинаторная теория. - М.: Мир, 1982
5. А.М. Райгородский Комбинаторика и теория вероятностей. - МФТИ, 2012 - 109 c.
6. Г. Эндрюс Теория разбиений, М.: Наука, 1982
7. Д. Кнут, Р. Грэхем, О. Паташник. Конкретная математика. Математические основы информатики. М.: Мир, 1998

Для участия в курсе слушателю необходимо иметь базовые представления о теории множеств и началах анализа. Все остальные понятия будут введены в ходе курса.

1. Правило сложения. Правило умножения. Принцип Дирихле.
2. Основные комбинаторные величины и их свойства. Размещения.
3. Сочетания с повторениями и без.
4. Комбинаторные тождества. Биномиальные коэффициенты. Тождества с биномиальными коэффициентами.
5. Полиномиальный коэффициент. Полиномиальная формула.
6. Формула включений и исключений. Применение формулы включений и исключений.
7. Выравнивания. Пример вычисления выравниваний.
8. Формула обращения Мёбиуса.
9. Циклические последовательности.
10. Разбиения чисел на слагаемые. Диаграмма Юнга.
11. Линейные рекуррентные соотношения. Формальные степенные ряды.
12. Производящие функции. Числа Фибоначчи и Каталана.

Базовые знания:

1. основные правила и принципы комбинаторики,
2. основные комбинаторные величины и тождества с ними,
3. основы теории обращения Мёбиуса,
4. основы теории разбиений,
5. основы метода производящих функций, линейных рекуррентных соотношений и их решений.

Умения:

1. решать простейшие комбинаторные задачи,
2. доказывать тождества,
3. упрощать выражения, содержащие биномиальные коэффициенты,
4. вычислять количества упорядоченных и неупорядоченных разбиений,
5. находить формулы для линейных рекуррентных соотношений,
6. вычислять производящие функции