Итак, завтра у нас вебинар про функцию Эйлера, и на этом мы заканчиваем наш курс по теории чисел. А у меня уже готовы все идеи следующего мини-курса 🙂

Олимпиадная комбинаторика: от правил подсчёта до формулы Бернсайда

В этот раз попробуем пройти довольно большой путь: от самых первых правил комбинаторики до симметрий, орбит и формулы Бернсайда.

И мне очень хочется, чтобы новый курс содержательно перекликался с курсом «Олимпиадная теория чисел: от сравнений до функции Эйлера».

Потому что комбинаторика и теория чисел на олимпиадах постоянно и довольно неожиданно встречаются друг с другом 🙂

Планируется шесть вебинаров.

1. Комбинаторный подсчёт: от правил суммы и произведения до сочетаний

Большой, фундаментальный, основополагающий вебинар: правила суммы и произведения, перестановки, размещения, сочетания, в том числе с повторениями. Поговорим о подсчёте через дополнение, разных способах считать одни и те же объекты и о двойном подсчёте.

Главная цель — научиться не вспоминать готовую формулу, а понимать, что именно и каким способом нужно считать.

2. Комбинаторика делителей: от разложения на простые множители до функций делителей

Посмотрим на привычные задачи теории чисел глазами комбинаторики.

Почему формула для числа делителей устроена именно так? Как считать сумму и произведение делителей? Как разложение числа на простые множители превращается в задачу о независимом выборе?

Здесь уже начнут появляться прямые мостики к курсу по теории чисел.

3. Включения и исключения: от подсчёта с ограничениями до функции Эйлера

Научимся считать объекты, которые одновременно удовлетворяют нескольким условиям, и разбираться с неизбежными пересечениями.

А затем из чисто комбинаторного рассуждения неожиданно снова появится функция Эйлера.

То есть формулу, знакомую по курсу теории чисел, мы получим совсем другим способом.

4. Бином Ньютона и полиномиальная формула: от треугольника Паскаля до малой теоремы Ферма

Биномиальные коэффициенты, треугольник Паскаля, комбинаторные тождества, бином Ньютона и полиномиальная формула.

А в финале — ещё один мост к теории чисел: доказательство малой теоремы Ферма с помощью полиномиальной формулы.

На курсе по теории чисел мы использовали МТФ как рабочий инструмент. Здесь посмотрим, откуда она может возникнуть с совершенно неожиданной стороны.

5. Рекурсии в комбинаторике: от разбиения на случаи до чисел Фибоначчи и Каталана

Будем учиться не считать всё сразу, а сводить большую задачу к нескольким меньшим.

Замощения, строки, перестановки, последовательности, числа Фибоначчи — и дальше, насколько позволит время, дойдём до чисел Каталана.

Это тот самый класс задач, где главное — увидеть правильное рекуррентное соотношение.

6. Симметрия в комбинаторике: от циклических сдвигов до формулы Бернсайда

Ожерелья, раскраски, циклические сдвиги, группы симметрий, орбиты — и в конце формула Бернсайда.

А по дороге мы ещё раз докажем малую теорему Ферма, теперь уже через симметрию и орбиты.

Удивительно, что один и тот же арифметический факт возникнет в нашем курсе дважды — из совершенно разных комбинаторных идей!

Весь курс хочется построить вокруг одной мысли:

Комбинаторика — это не набор формул для «C из n по k», а искусство видеть, что именно и каким способом мы вычисляем.

Ну и, конечно, задач будет много 🙂