Комбинаторика

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

Результаты обучения
Базовые знания:

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

Умения:

• решать простейшие комбинаторные задачи,
• доказывать тождества,
• упрощать выражения, содержащие биномиальные коэффициенты,
• вычислять количества упорядоченных и неупорядоченных разбиений,
• находить формулы для линейных рекуррентных соотношений,
• вычислять производящие функции

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

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

Сертификат
Сертификат участника обычно выдается при достижении 50% от общего рейтинга при условии сдачи работ до дедлайна. Сертификат с отличием, как правило, выдается при достижении 75% от общего рейтинга при условии сдачи работ до дедлайна