Итак, завтра у нас вебинар про функцию Эйлера, и на этом мы заканчиваем наш курс по тео...
Итак, завтра у нас вебинар про функцию Эйлера, и на этом мы заканчиваем наш курс по теории чисел. А у меня уже готовы все идеи следующего мини-курса 🙂 Олимпиадная комбинаторика: от правил подсчёта до формулы Бернсайда В этот раз попробуем пройти довольно большой путь: от самых первых правил комбинаторики до симметрий, орбит и формулы Бернсайда. И мне очень хочется, чтобы новый курс содержательно перекликался с курсом «Олимпиадная теория чисел: от сравнений до функции Эйлера». Потому что комбинаторика и теория чисел на олимпиадах постоянно и довольно неожиданно встречаются друг с другом 🙂 Планируется шесть вебинаров. ••• 🔹 1. Комбинаторный подсчёт: от правил суммы и произведения до сочетаний Большой, фундаментальный, основополагающий вебинар: правила суммы и произведения, перестановки, размещения, сочетания, в том числе с повторениями. Поговорим о подсчёте через дополнение, разных способах считать одни и те же объекты и о двойном подсчёте. Главная цель — научиться не вспоминать готовую формулу, а понимать, что именно и каким способом нужно считать. ••• 🔹 2. Комбинаторика делителей: от разложения на простые множители до функций делителей Посмотрим на привычные задачи теории чисел глазами комбинаторики. Почему формула для числа делителей устроена именно так? Как считать сумму и произведение делителей? Как разложение числа на простые множители превращается в задачу о независимом выборе? Здесь уже начнут появляться прямые мостики к курсу по теории чисел. ••• 🔹 3. Включения и исключения: от подсчёта с ограничениями до функции Эйлера Научимся считать объекты, которые одновременно удовлетворяют нескольким условиям, и разбираться с неизбежными пересечениями. А затем из чисто комбинаторного рассуждения неожиданно снова появится функция Эйлера — знакомую по курсу теории чисел формулу мы получим совсем другим способом. ••• 🔹 4. Бином Ньютона и полиномиальная формула: от треугольника Паскаля до малой теоремы Ферма Биномиальные коэффициенты, треугольник Паскаля, комбинаторные тождества, бином Ньютона и полиномиальная формула. А в финале — ещё один мост к теории чисел: доказательство малой теоремы Ферма с помощью полиномиальной формулы. На курсе по теории чисел мы использовали МТФ как рабочий инструмент, а здесь посмотрим, откуда она может возникнуть с совершенно неожиданной стороны. ••• 🔹 5. Рекурсии в комбинаторике: от разбиения на случаи до чисел Фибоначчи и Каталана Будем учиться не считать всё сразу, а сводить большую задачу к нескольким меньшим. Замощения, строки, перестановки, последовательности, числа Фибоначчи — и дальше, насколько позволит время, дойдём до чисел Каталана. Это тот самый класс задач, где главное — увидеть правильное рекуррентное соотношение. ••• 🔹 6. Симметрия в комбинаторике: от циклических сдвигов до формулы Бернсайда Ожерелья, раскраски, циклические сдвиги, группы симметрий, орбиты — и в конце формула Бернсайда. А по дороге мы ещё раз докажем малую теорему Ферма, теперь уже через симметрию и орбиты. Удивительно, что один и тот же арифметический факт возникнет в нашем курсе дважды — из совершенно разных комбинаторных идей! ••• 🔸 Весь курс хочется построить вокруг одной мысли: Комбинаторика — это не набор формул для «C из n по k», а искусство видеть, что именно и каким способом мы вычисляем. Ну и, конечно, задач будет много 🙂