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