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