Stepik Комбинаторика для продолжающих — курс А.М. Райгородского (МФТИ)
О курсе
Подробнее
Маткульт-привет! 🎓
Базовая комбинаторика учит считать напрямую: разбивать задачу на случаи, выбирать и переставлять объекты, применять правила сложения и умножения, бином Ньютона и формулу включений–исключений.
Но что делать, если нужное количество спрятано внутри других подсчётов? Если объекты повторяются с некоторым периодом? Если каждый следующий результат зависит от предыдущих, а явной формулы нет?
Здесь начинается комбинаторика для продолжающих.
На этом курсе мы выйдем за пределы привычных формул для перестановок и сочетаний и освоим три больших математических хода:
научимся восстанавливать точные количества с помощью функции и формулы обращения Мёбиуса;
будем описывать структуры через частичные порядки, разбиения чисел и диаграммы Юнга;
превратим рекуррентные последовательности в алгебраические объекты с помощью формальных рядов и производящих функций.
По пути разберём периодические и циклические последовательности, линейные рекуррентные соотношения, числа Фибоначчи и Каталана.
Как устроен маршрут
Курс начинается с входной разминки по базовой комбинаторике. Это не вступительный экзамен: она поможет проверить фундамент и заметить темы, которые стоит освежить.
Дальше сложность растёт постепенно:
арифметический фундамент и функция Мёбиуса;
периодические последовательности и частичные порядки;
разбиения чисел и диаграммы Юнга;
рекуррентные соотношения;
формальные степенные ряды и производящие функции;
числа Фибоначчи, Каталана и итоговые задачи.
Курс заметно сложнее вводной комбинаторики. Здесь больше абстракций, доказательств и многошаговых рассуждений. Формулы придётся не только применять, но и понимать: откуда они берутся и почему работают.
При этом начинать можно без предварительного знакомства с теорией чисел, функцией Мёбиуса или производящими функциями — необходимые понятия вводятся по ходу курса.
Если вы проходили «Комбинаторику для начинающих», необходимый фундамент у вас уже есть. Если изучали базовую комбинаторику в другом месте, тоже можно начинать: входная разминка покажет, готовы ли вы двигаться дальше.
Об авторе
👨🏫 Курс ведёт Андрей Михайлович Райгородский — директор Физтех-школы прикладной математики и информатики МФТИ, математик и популяризатор науки, лауреат премии Президента России для молодых учёных.
В его лекциях важна не только готовая формула, но и путь к ней: от конкретной задачи и первых наблюдений — к общей конструкции и доказательству.
Вводный курс Андрея Михайловича по комбинаторике был номинирован на Stepik Awards 2024, а «Экстремальная комбинаторика» получила Stepik Awards 2025.
Если нужно укрепить фундамент
Математика с полного нуля — дроби, проценты и уравнения;
Школьная математика до уровня МФТИ — от алгебры до тригонометрии;
Введение в высшую математику — математический анализ, линейная алгебра и аналитическая геометрия;
Комбинаторика для начинающих — рекомендуемая непосредственная подготовка к этому курсу.
Другие курсы Андрея Райгородского и Алексея Савватеева собраны в профиле Клуба любителей математики.
Чтобы не потеряться
Telegram — анонсы, разборы и опыт учеников;
YouTube — лекции и стримы с авторами;
ВКонтакте — записи лекций и новости;
Хармфульский клуб — для тех, кто хочет ботать математику в общем ритме, с разборами и поддержкой.
Готовы увидеть, что ещё умеет комбинаторика?
Sapere Aude! ✨
Требования
Что нужно для старта
- Перед началом желательно знать:
- правила сложения и умножения;
- перестановки, размещения и сочетания;
- факториал и биномиальные коэффициенты;
- бином Ньютона;
- формулу включений–исключений;
- школьную алгебру: степени, многочлены, уравнения, последовательности и преобразование выражений.
- Не требуется заранее знать теорию чисел, рекуррентные соотношения, функцию Мёбиуса или производящие функции — они вводятся в курсе.
- Основной маршрут доступен без математического анализа. Для отдельных углублённых фрагментов о сходимости рядов будет полезно знакомство с пределами.
- Если базовые темы пока незнакомы или успели забыться, начните с «Комбинаторики для начинающих».
Результат
Что вы получите
- Применять формулу обращения Мёбиуса к суммам по делителям и задачам о периодических объектах
- Различать и считать периодические и циклические последовательности
- Распознавать частичные порядки и разбирать их основные свойства
- Представлять разбиения чисел с помощью диаграмм Юнга
- Составлять рекуррентные соотношения по условию комбинаторной задачи
- Решать основные типы линейных рекуррентных соотношений
- Выполнять операции с формальными степенными рядами
- Строить производящие функции и использовать их для решения рекуррентностей
- Понимать, как числа Фибоначчи и Каталана возникают в комбинаторных задачах
Аудитория
Для кого этот курс
- Для тех, кто знает основы комбинаторики и хочет перейти к более сильным методам
- Для выпускников курса «Комбинаторика для начинающих»
- Для старшеклассников с хорошей математической подготовкой
- Для студентов математических, технических и IT-направлений
- Для участников олимпиад и математических кружков
- Для программистов и аналитиков, укрепляющих фундамент в дискретной математике
- Для взрослых любителей математики, которым базовых задач уже мало
- Это не курс с полного нуля. При этом прохождение именно нашего вводного курса не обязательно: важны знания, а не формальный порядок курсов.
Содержание
8 занятийПрограмма курса
№ТемаЧто внутри
01Организационная информация и промежуточное тестирование
- Организационная информация
- Промежуточное тестирование
02Формулировка проблемы. Основная теорема арифметики.
- Циклические слова
- Простые числа
- Основная теорема арифметики
- Исторический анекдот(**)
- Задача 1. Количество циклических последовательностей длины 2
- Задача 2. Существование разложение в произведение простых чисел
- Задача 3. Вспомогательное утверждение для основной теоремы арифм
- Задача 4. Д-во единственности разложения в произведения простых
- Конспект. Формулировка проблемы. Основная теорема арифметики.
- Функция Мёбиуса
- Сумма по делителям числа
- Сумма функции Мебиуса по делителям числа
- Формула обращения Мебиуса. Формулировка
- Формула обращения Мебиуса. Доказательство
- Задача 5. Пример применения формулы обращения Мёбиуса -1
- Задача 6. Пример применения формулы обращения Мёбиуса - 2
- Задача 7. Пример применения формулы обращения Мёбиуса -3
- Конспект. Формула обращения Мёбиуса.
- Тест
- Задачи
- Ответы
03Формула для количества циклических последовательностей.
- Частично упорядоченное множество
- Линейные и циклические последовательности
- Период линейной последовательности
- Биекция между множествами последовательностей одного периода
- Количество линейных последовательностей
- Количество циклических последовательностей длины n и периода n
- Задача 1. Пример вычисления количества циклических последов.
- Задача 2. Пример вычисления количества циклических послед -2
- Конспект. Формула для количества циклических последовательностей
- Функция Мебиуса для ЧУМа
- Количество циклических последовательностей
- Связь с обычной функцией Мебиуса
- Совпадение функций Мебиуса для произведения различных простых ч
- Совпадение функций Мебиуса для остальных чисел
- Формула обращения Мебиуса на ЧУМе
- Задача 3
- Задача 4
- Конспект. Формула обращения Мёбиуса на частично упоряд мн-ве
- Определение множества.(*)
- Определение частичного порядка (*)
- Функция Мёбиуса (*)
- Дополнительные материалы. Конспект
- Тест
- Задачи
- Ответы
04Разбиения чисел на слагаемые. Диаграмма Юнга.
- Разбиения чисел на слагаемые
- "Карнавальная" формулировка задач о разбиениях (**)
- Задача о "попойке"
- Задача о "капусте"
- Формула Харди-Рамануджана (*), (**)
- Задача 1
- Конспект. Разбиения чисел на слагаемые
- Диаграмма Юнга
- Теоремы о количестве неупорядоченных разбиений
- Двойственная диаграмма Юнга
- Условия задач. Диаграмма Юнга
- Задача 2
- Задача 3
- Задача 4
- Конспект. Диаграмма Юнга
- Дополнительные материалы. Обобщенная формула обращения Мебиуса
- Дополнительные материалы. Вывод формулы включений и исключений(*
- Дополнительные материалы. Конспект
- Тест
- Задачи
- Ответы
05Линейные рекуррентные соотношения. Формальные степенные ряды
- Линейные рекуррентные соотношения
- Числа Фибоначчи
- Характеристическое уравнение
- Теорема 1. Формулировка
- Теорема 1. Пункт 1. Доказательство
- Теорема 1. Пункт 2. Доказательство
- Теорема 2
- Линейные рекуррентные соотношения k порядка (*)
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Конспект. Линейные рекуррентные соотношения
- Формальные степенные ряды
- Деление степенных рядов
- Вывод комбинаторного тождества при помощи формальных степен ряд
- Условия задач. Формальные степенные ряды
- Задача 5
- Задача 6
- Конспект. Формальные степенные ряды
- Тест
- Задачи
- Ответы
06Производящие функции. Числа Фибоначчи и Каталана.
- Производящая функция
- Теорема о сходимости рядов
- Примеры, иллюстрирующие теорему
- Сходимость на границе круга
- Пример вычисления производящей функции
- Замечание к видео
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Конспект. Производящие функции
- Пример с числами Фибоначчи
- Производящая функция чисел Фибоначчи
- Числа Каталана
- Производящая функция чисел Каталана
- Извлечение корня из формального степенного ряда
- Формула для чисел Каталана
- Задача 5
- Задача 6
- Замечание к видео
- Задача 7
- Конспект. Числа Фибоначчи и Каталана
- Тест
- Задачи
- Ответы
07Итоговый тест
- Тест
- Задачи
- Ответы
08🎁 One more thing
- Что дальше и подарок напоследок!
01Организационная информация и промежуточное тестирование
- Организационная информация
- Промежуточное тестирование
02Формулировка проблемы. Основная теорема арифметики.
- Циклические слова
- Простые числа
- Основная теорема арифметики
- Исторический анекдот(**)
- Задача 1. Количество циклических последовательностей длины 2
- Задача 2. Существование разложение в произведение простых чисел
- Задача 3. Вспомогательное утверждение для основной теоремы арифм
- Задача 4. Д-во единственности разложения в произведения простых
- Конспект. Формулировка проблемы. Основная теорема арифметики.
- Функция Мёбиуса
- Сумма по делителям числа
- Сумма функции Мебиуса по делителям числа
- Формула обращения Мебиуса. Формулировка
- Формула обращения Мебиуса. Доказательство
- Задача 5. Пример применения формулы обращения Мёбиуса -1
- Задача 6. Пример применения формулы обращения Мёбиуса - 2
- Задача 7. Пример применения формулы обращения Мёбиуса -3
- Конспект. Формула обращения Мёбиуса.
- Тест
- Задачи
- Ответы
03Формула для количества циклических последовательностей.
- Частично упорядоченное множество
- Линейные и циклические последовательности
- Период линейной последовательности
- Биекция между множествами последовательностей одного периода
- Количество линейных последовательностей
- Количество циклических последовательностей длины n и периода n
- Задача 1. Пример вычисления количества циклических последов.
- Задача 2. Пример вычисления количества циклических послед -2
- Конспект. Формула для количества циклических последовательностей
- Функция Мебиуса для ЧУМа
- Количество циклических последовательностей
- Связь с обычной функцией Мебиуса
- Совпадение функций Мебиуса для произведения различных простых ч
- Совпадение функций Мебиуса для остальных чисел
- Формула обращения Мебиуса на ЧУМе
- Задача 3
- Задача 4
- Конспект. Формула обращения Мёбиуса на частично упоряд мн-ве
- Определение множества.(*)
- Определение частичного порядка (*)
- Функция Мёбиуса (*)
- Дополнительные материалы. Конспект
- Тест
- Задачи
- Ответы
04Разбиения чисел на слагаемые. Диаграмма Юнга.
- Разбиения чисел на слагаемые
- "Карнавальная" формулировка задач о разбиениях (**)
- Задача о "попойке"
- Задача о "капусте"
- Формула Харди-Рамануджана (*), (**)
- Задача 1
- Конспект. Разбиения чисел на слагаемые
- Диаграмма Юнга
- Теоремы о количестве неупорядоченных разбиений
- Двойственная диаграмма Юнга
- Условия задач. Диаграмма Юнга
- Задача 2
- Задача 3
- Задача 4
- Конспект. Диаграмма Юнга
- Дополнительные материалы. Обобщенная формула обращения Мебиуса
- Дополнительные материалы. Вывод формулы включений и исключений(*
- Дополнительные материалы. Конспект
- Тест
- Задачи
- Ответы
05Линейные рекуррентные соотношения. Формальные степенные ряды
- Линейные рекуррентные соотношения
- Числа Фибоначчи
- Характеристическое уравнение
- Теорема 1. Формулировка
- Теорема 1. Пункт 1. Доказательство
- Теорема 1. Пункт 2. Доказательство
- Теорема 2
- Линейные рекуррентные соотношения k порядка (*)
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Конспект. Линейные рекуррентные соотношения
- Формальные степенные ряды
- Деление степенных рядов
- Вывод комбинаторного тождества при помощи формальных степен ряд
- Условия задач. Формальные степенные ряды
- Задача 5
- Задача 6
- Конспект. Формальные степенные ряды
- Тест
- Задачи
- Ответы
06Производящие функции. Числа Фибоначчи и Каталана.
- Производящая функция
- Теорема о сходимости рядов
- Примеры, иллюстрирующие теорему
- Сходимость на границе круга
- Пример вычисления производящей функции
- Замечание к видео
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Конспект. Производящие функции
- Пример с числами Фибоначчи
- Производящая функция чисел Фибоначчи
- Числа Каталана
- Производящая функция чисел Каталана
- Извлечение корня из формального степенного ряда
- Формула для чисел Каталана
- Задача 5
- Задача 6
- Замечание к видео
- Задача 7
- Конспект. Числа Фибоначчи и Каталана
- Тест
- Задачи
- Ответы
07Итоговый тест
- Тест
- Задачи
- Ответы
08🎁 One more thing
- Что дальше и подарок напоследок!
Организатор
Автор курса
Мнения учеников
Отзывы о курсе
Оставьте отзыв
Расскажите о качестве обучения, поддержке и результате. Это поможет другим выбрать организацию осознанно.
Оставьте заявку
Консультант ответит на вопросы о курсе «Комбинаторика для продолжающих — курс А.М. Райгородского (МФТИ)» и поможет разобраться в деталях обучения.
Нажимая кнопку, вы даете согласие на обработку персональных данных
Направления:Математика
Информация обновлена 7 сентября 2026 г.
Продолжить выбор
Похожие курсы
Начать без затрат
