Как считать варианты и не путать правила суммы и произведения?

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

Правило произведения

Если объект строится в несколько этапов и после каждого допустимого предыдущего выбора имеется известное число продолжений, количества перемножают. Для пароля из четырёх цифр без ограничений получается 10⁴ вариантов. Если первая цифра не может быть нулём, первый множитель равен девяти, а остальные остаются десятью.

Правило суммы

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

Перестановки, размещения и сочетания

Перестановка учитывает порядок всех n различных элементов. Размещение выбирает k элементов с учётом порядка, сочетание — без учёта. Перед применением формулы задайте вопрос: изменится ли объект, если выбранные элементы поменять местами? Ответ определяет, нужно ли делить на число перестановок внутри набора.

Повторы и ограничения

Разрешённый повтор превращает последовательность длины k над алфавитом мощности m в mᵏ вариантов. Запрет соседних одинаковых символов меняет множители: первый выбирается m способами, каждый следующий — m − 1. Более сложные условия удобно разбивать по первому символу или состоянию уже построенного префикса.

Надёжная проверка

Для маленьких параметров перечислите варианты вручную или напишите короткий генератор и сравните с формулой. Проверьте, что случаи покрывают всё пространство и не пересекаются. На экзамене полезно сопровождать произведение словами «выбираем сначала…, затем…», чтобы структура решения была видна без догадок.

Формула должна следовать из модели выбора

Перестановка отвечает на вопрос, как упорядочить все n различных объектов; размещение — как выбрать и упорядочить k; сочетание — как выбрать k без порядка. Перед формулой полезно проговорить, считаются ли выборы различными после перестановки и можно ли повторять объект. Это предотвращает применение знакомого выражения к другой модели.

from itertools import combinations, permutations, product

items = "ABCD"
print(len(list(combinations(items, 2))))   # 6: порядок не важен
print(len(list(permutations(items, 2))))   # 12: порядок важен
print(len(list(product(items, repeat=2)))) # 16: повторы разрешены

Программа перебора полезна для проверки маленьких n, но не заменяет вывода. Для больших значений перечисление экспоненциально или факториально растёт, тогда как формула вычисляет число без генерации всех объектов.

Практика: пароль с ограничениями

Посчитайте шестизначные строки из цифр 0…9, в которых первая цифра не ноль, цифры не повторяются и присутствует ровно одна чётная цифра. Сначала разложите выбор на непересекающиеся случаи и получите формулу. Затем напишите полный перебор для проверки ответа. Отдельно измените условие: порядок цифр не важен. Объясните, какая часть прежней модели перестала работать и почему новый ответ нельзя получить простой заменой одного множителя.