Математика · учебный маршрут

Счёт через устройство объектов

Сложный конечный набор раскладывается по двум описаниям, симметрии или рекурсии.

Синяя и оранжевая половины складываются в целый круг.

Чему научитесь

Выбирать двойной счёт, включение-исключение и порождающее разбиение для конкретной комбинаторной конструкции.

Что пригодится

  • Сочетания
  • Факториал
  • Сумма конечного ряда

10 тем по порядку

Читайте объяснение или сразу переходите к заданию

  1. Как один набор пар даёт два способа подсчёта

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

    Практика
  2. Как выбор из двух групп объясняет тождество Вандермонда

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

    Практика
  3. Почему диагональная сумма сочетаний даёт следующее сочетание

    Как сумма сочетаний вдоль диагонали треугольника Паскаля превращается в одно сочетание, если классифицировать выбранные наборы по максимальному элементу.

    Практика
  4. Как распределить одинаковые предметы с нижними границами

    Как учесть разные минимальные количества в распределении одинаковых предметов, снять нижние границы заменой переменных и проверить невозможный остаток.

    Практика
  5. Почему разбиения числа отличаются от упорядоченных сумм

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

    Практика
  6. Как посчитать допустимые порядки при заданных зависимостях

    Как посчитать все линейные порядки выполнения зависимых задач, а не только найти один допустимый порядок, и почему выбирать доступные шаги нужно с разными продолжениями.

    Практика
  7. Почему число раскрасок с точностью до поворота нельзя всегда делить на число поворотов

    Как считать раскраски кольца с точностью до поворота, почему симметричные узоры мешают простому делению и как среднее число неподвижных раскрасок исправляет подсчёт.

    Практика
  8. Как отражение плохого пути считает допустимые скобочные структуры

    Как префиксное условие правильных скобок превращается в ограничение пути, а отражение первого плохого участка даёт формулу числа Каталана.

    Практика
  9. Как коэффициент произведения кодирует набор допустимых выборов

    Как степени переменной кодируют разрешённые количества, а коэффициент произведения считает сочетания с фиксированной суммой без перебора всех полных распределений.

    Практика
  10. Как запрещённые позиции превращают перестановку в задачу включения-исключения

    Как посчитать перестановки с произвольными запрещёнными позициями, учесть невозможные пересечения запретов и использовать совместимые клетки как ладейные числа.

    Практика

Как заниматься

Нужно проходить все темы подряд?

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

Что делать, если ответ оказался неверным?

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

Все темы: Математика