Правила суммы и произведения

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

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

Зачем учиться считать варианты

«Сколько паролей длины 8?», «Сколько IP-адресов в подсети?», «Сколько раз выполнится вложенный цикл?», «Какова вероятность угадать?» — за всеми этими вопросами стоит комбинаторика. Оценка числа вариантов — это и анализ сложности алгоритмов (перебор всех перестановок — это факториал вариантов, отсюда «комбинаторный взрыв»), и криптография (стойкость пароля — это число его вариантов), и проектирование. Всё начинается с двух простых правил.

Правило суммы: выбор «или»

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

Пример: в меню 4 первых блюда и 3 десерта. Если хочется заказать одно блюдо (или первое, или десерт), вариантов 4 + 3 = 7. Ключевое слово — «или» и «не пересекаются». Это та же логика, что объединение непересекающихся множеств: |A ∪ B| = |A| + |B|. Если наборы пересекаются, надо вычесть пересечение (вспоминаем включение-исключение — к нему вернёмся).

Правило произведения: выбор «и»

Правило произведения: если выбор состоит из двух независимых шагов, и первый можно сделать m способами, а второй (при любом исходе первого) n способами, то всю пару шагов можно выполнить m · n способами.

Пример: 4 первых блюда и 3 десерта — на обед берём и то, и другое. Тогда обедов 4 · 3 = 12. Ключевое слово — «и», последовательные независимые шаги. Это в точности мощность декартова произведения: |A × B| = |A| · |B|. Каждый обед — пара (первое, десерт).

Как не перепутать

Простое правило: «или» → складываем, «и» → умножаем. Делаем один выбор из нескольких возможностей — сумма. Делаем несколько выборов подряд — произведение. Это различие — самое частое место ошибок у новичков, поэтому всегда спрашивай себя: «я выбираю одно из, или составляю из нескольких частей?».

Считаем пароли: правило произведения в деле

Сколько паролей длины 3 из строчных латинских букв (26 штук)? На каждую позицию — 26 вариантов, позиций три, выборы независимы: 26 · 26 · 26 = 26³. Проверим перебором на маленьком алфавите, чтобы увидеть правило произведения вживую.

from itertools import product

alphabet = ['a', 'b', 'c']     # маленький алфавит из 3 букв
length = 3

# Перебираем все строки длины 3 из этого алфавита
all_passwords = list(product(alphabet, repeat=length))
print("Всего вариантов перебором:", len(all_passwords))
print("По правилу произведения 3^3 =", 3 ** length)
print("Первые пять:", [''.join(p) for p in all_passwords[:5]])

# Правило суммы: выбрать ОДИН символ — букву (3) или цифру (2)
letters = ['a', 'b', 'c']
digits = ['0', '1']
print("Один символ (буква ИЛИ цифра):", len(letters) + len(digits))

Вывод:

Всего вариантов перебором: 27
По правилу произведения 3^3 = 27
Первые пять: ['aaa', 'aab', 'aac', 'aba', 'abb']
Один символ (буква ИЛИ цифра): 5

Перебор дал ровно 27 = 3³ — правило произведения подтвердилось. А для «одного символа из букв или цифр» сработало правило суммы: 3 + 2 = 5. Заметь, как itertools.product прямо реализует декартово произведение — отсюда и название.

Комбинируем правила

Реальные задачи сочетают оба правила. Сколько автомобильных номеров вида «буква-три цифры-буква», если букв 12, а цифр 10? Это последовательность шагов (правило произведения): 12 · 10 · 10 · 10 · 12 = 12² · 10³ = 144000. А если номер может быть либо такого формата, либо другого — форматы складываются по правилу суммы. Разбивай сложную задачу на шаги (умножаем) и альтернативы (складываем) — и считай по частям.

Дерево вариантов

Наглядная модель правила произведения — дерево вариантов. Корень — старт, из него выходит m ветвей (первый выбор), из каждой — ещё n ветвей (второй выбор). Число «листьев» внизу — это m · n, все возможные исходы. Дерево помогает не запутаться в сложных задачах: рисуешь уровни выборов и считаешь листья. Этот же образ — основа алгоритмов перебора с возвратом (backtracking).

Рекурсия против итерации: одно и то же разными словами

Любую рекурсию можно переписать циклом, и наоборот — это важный практический факт. Рекурсия часто короче и яснее выражает идею (особенно для деревьев и «разделяй и властвуй»), но у неё есть цена: каждый вложенный вызов занимает место в стеке вызовов, и при слишком глубокой рекурсии программа падает с переполнением стека. Python, например, по умолчанию ограничивает глубину примерно тысячей вызовов.

def fact_rec(n):
    return 1 if n == 0 else n * fact_rec(n - 1)   # рекурсивно

def fact_iter(n):
    res = 1
    for k in range(2, n + 1):                      # итеративно
        res *= k
    return res

print("Рекурсия:", fact_rec(6), "| Итерация:", fact_iter(6))

Вывод:

Рекурсия: 720 | Итерация: 720

Обе версии дают одно и то же. Выбор — вопрос вкуса и ограничений: для глубокой рекурсии (обход огромного дерева) безопаснее итеративная версия с явным стеком, а для неглубокой и «древовидной» логики рекурсия читается лучше. Понимание их эквивалентности освобождает: вы выбираете форму записи под задачу, зная, что вычислительно это одно и то же.

Правила в реальных подсчётах: адреса и номера

Закрепим правила на «инженерных» примерах, которые программист встречает напрямую. Сколько устройств можно адресовать в подсети /24 (где под номер хоста отведено 8 бит)? Каждый бит — независимый выбор из двух значений, итого по правилу произведения 2⁸. А сколько коротких артикулов вида «буква-цифра-цифра», если букв 10, а цифр 10?

# Подсеть /24: 8 свободных бит, каждый бит независим (правило произведения)
print("Адресов в подсети /24:", 2 ** 8)

# Артикул вида буква-цифра-цифра: 3 независимых выбора
letters, digits = 10, 10
print("Артикулов «буква-цифра-цифра»:", letters * digits * digits)

# А если артикул — это ЛИБО такой формат, ЛИБО просто 4 цифры (правило суммы)
four_digits = 10 ** 4
print("Всего форматов (правило суммы):", letters * digits * digits + four_digits)

Вывод:

Адресов в подсети /24: 256
Артикулов «буква-цифра-цифра»: 1000
Всего форматов (правило суммы): 11000

Здесь работают оба правила: внутри одного формата перемножаем независимые позиции (произведение), а складывая два альтернативных формата — суммируем (правило суммы). Именно так инженеры заранее оценивают, хватит ли адресного пространства или диапазона артикулов. Понимание этих правил спасает от ситуаций вроде «закончились IP-адреса» — классической проблемы, породившей переход с IPv4 на IPv6.

Типичные ошибки

• Складывать там, где надо умножать. «Рубашка и брюки» — это произведение (рубашки · брюки), а не сумма. Складываем только взаимоисключающие альтернативы.
• Применять правило суммы к пересекающимся наборам. Если что-то попадает в оба набора, простое сложение посчитает его дважды — нужно включение-исключение.
• Забывать про зависимость шагов. Правило произведения требует, чтобы число вариантов второго шага не зависело от исхода первого. Если зависит (например, «без повторов»), считаем аккуратнее — это уже размещения.

Итог

• Правило суммы: один выбор из непересекающихся наборов — складываем («или»).
• Правило произведения: несколько независимых шагов — умножаем («и»).
• Сумма соответствует объединению множеств, произведение — декартову произведению.
• Сложные задачи разбивают на шаги (умножение) и альтернативы (сложение); помогает дерево вариантов.