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

Правило суммы и правило произведения - два фундаментальных принципа комбинаторики, с которых начинается любой раздел о подсчёте количества исходов. Понять их несложно, но студенты стабильно путают, какое правило когда применять: суммировать варианты или перемножать? Эта путаница обходится дорого - результат может отличаться в разы. В статье разберём оба правила строго, с примерами и типовыми ошибками, а калькулятор ниже покажет геометрический смысл каждого.

Правило суммы: выбор из несовместных вариантов

Правило суммы формулируется так: если некоторое событие A можно осуществить $a$ способами, а другое событие B, несовместное с A, можно осуществить $b$ способами, то выбрать хотя бы одно из этих событий (A или B) можно $a + b$ способами.

$|A \cup B| = |A| + |B|, \quad \text{если } A \cap B = \varnothing.$

Ключевое слово здесь - «несовместные», то есть A и B не могут произойти одновременно. В задачах признак применения правила суммы - союз «или»: выбирается что-то одно из нескольких альтернатив.

Пример. В меню 5 горячих блюд и 4 холодных закуски. Сколькими способами можно выбрать одно блюдо?

Выбор горячего и выбор закуски - несовместные события (одновременно не берём). Поэтому: $5 + 4 = 9 \text{ способов.}$

Рассчитать для своей задачи

Если же события не являются несовместными (пересекаются), применяется формула включений-исключений:

$|A \cup B| = |A| + |B| - |A \cap B|.$

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

Правило произведения: последовательные независимые выборы

Правило произведения: если первый выбор можно сделать $m$ способами, а при каждом из них второй выбор - независимо - $n$ способами, то совместный выбор (первое и второе) можно осуществить $m \cdot n$ способами.

$|A \times B| = |A| \cdot |B|.$

Признак применения - союз «и»: нужно сделать несколько последовательных выборов. Множество всех исходов образует декартово произведение, которое удобно представить прямоугольной таблицей $m \times n$.

Пример. Из города A в город B ведут 3 дороги, из B в C - 5. Сколькими способами можно проехать из A в C через B?

Каждый маршрут - пара (дорога из A в B, дорога из B в C). Выборы независимы: $3 \cdot 5 = 15 \text{ маршрутов.}$

Рассчитать для своей задачи

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

Как различать правила: главный вопрос

Самый надёжный способ не ошибиться - ответить на вопрос: выбирается одна вещь или несколько?

• Выбирается одна вещь из нескольких групп (купить кофту или брюки) - правило суммы.
• Выбирается несколько вещей последовательно (купить кофту и брюки) - правило произведения.

Другой проверочный вопрос: «Влияет ли первый выбор на количество вариантов второго?» Если нет - это независимые выборы, правило произведения. Если первый выбор исключает второй полностью - это несовместные события, правило суммы.

Обобщение на несколько шагов

Оба правила легко обобщаются на произвольное число вариантов.

Обобщённое правило суммы: если попарно несовместные события $A_1, A_2, \ldots, A_k$ можно осуществить соответственно $n_1, n_2, \ldots, n_k$ способами, то одно из них осуществимо $n_1 + n_2 + \cdots + n_k$ способами.

Обобщённое правило произведения: если последовательный выбор состоит из $k$ шагов с $n_1, n_2, \ldots, n_k$ независимыми вариантами на каждом, то всего исходов: $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k.$

Пример (произведение трёх). Кодовый замок имеет три диска по 10 цифр каждый. Сколько кодов возможно? $10 \cdot 10 \cdot 10 = 1000.$

Пример (смесь правил). На олимпиаде три секции: математика (5 задач), физика (4 задачи) и информатика (3 задачи). Участнику нужно выбрать одну секцию и в ней - одну задачу. Сколько выборов?

Сначала выбирается задача внутри секции, затем применяется правило суммы по секциям: $5 + 4 + 3 = 12.$

Если бы нужно было выбрать по одной задаче из каждой секции, ответ был бы $5 \cdot 4 \cdot 3 = 60$.

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

Правила суммы и произведения лежат в основе всей комбинаторики. Формулы перестановок, размещений и сочетаний получаются именно из многократного применения правила произведения.

Например, количество размещений из $n$ по $k$ (упорядоченные выборки без повторений): $A_n^k = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1).$

Это цепочка из $k$ последовательных выборов: на первом шаге $n$ вариантов, на втором $n-1$ (один уже выбран), и так далее - типичное применение правила произведения.

Количество сочетаний $C_n^k$ - сколько способов выбрать $k$ элементов из $n$ без учёта порядка - вводится через деление числа размещений: $C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}.$

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

Решение смешанных задач

В реальных задачах правила суммы и произведения часто применяются вместе. Общая стратегия решения:

1. Разбить задачу на независимые шаги (если нужно сделать несколько последовательных выборов).
2. Для каждого шага подсчитать количество вариантов.
3. Если шаги последовательные - перемножить.
4. Если задача распадается на несовместные случаи - просуммировать.

Пример. Сколько двузначных чисел начинается на чётную цифру?

• Первая цифра (чётная, не ноль): 2, 4, 6, 8 - 4 варианта.
• Вторая цифра (любая): 0, 1, ..., 9 - 10 вариантов.
• Правило произведения: $4 \cdot 10 = 40$.

Пример сложнее. Сколько трёхзначных чисел, в которых ровно одна цифра равна 7?

Разбиваем на несовместные случаи по позиции семёрки:

• 7 на сотнях: $1 \cdot 9 \cdot 9 = 81$ (единицы и десятки - не 7, десятки могут быть 0).
• 7 на десятках: $8 \cdot 1 \cdot 9 = 72$ (сотни - не 0 и не 7, единицы - не 7).
• 7 на единицах: $8 \cdot 9 \cdot 1 = 72$.

Правило суммы: $81 + 72 + 72 = 225$.

Частые ошибки

• Складывают вместо умножения. Если задача требует последовательного выбора («и то, и другое»), нужно перемножать, а не складывать. «Выбрать рубашку и галстук» - не 5+4=9, а $5 \cdot 4 = 20$.
• Умножают вместо сложения. Если нужно выбрать что-то одно из нескольких групп («одно или другое»), нужно складывать, а не умножать.
• Не замечают несовместность. Если события пересекаются, нельзя просто сложить - нужно вычесть пересечение.
• Игнорируют ограничения. В задачах на числа первая цифра не может быть нулём, что уменьшает число вариантов на первом шаге.
• Путают упорядоченный и неупорядоченный выбор. Правило произведения даёт упорядоченные пары; для неупорядоченных нужно дополнительно делить на $k!$.

FAQ

Как быстро понять, какое правило применять? Обратите внимание на союзы в условии задачи. «Или» обычно указывает на правило суммы (выбор одного из вариантов), «и» - на правило произведения (выбор нескольких вещей последовательно). Если оба союза присутствуют, задача комбинированная: разбивайте её на шаги.

Можно ли применять правила произведения и суммы вместе в одной задаче? Да, это стандартная практика. Разбейте задачу на несовместные случаи (это суммируется), а внутри каждого случая считайте количество последовательных выборов (это умножается). Итог - сумма произведений по случаям.

Правило произведения работает только для двух шагов? Нет, оно обобщается на любое число шагов: $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$. Главное условие - число вариантов на каждом шаге не зависит от того, что выбрано на предыдущих (или эта зависимость учтена явно).

Коротко

Правило суммы применяется, когда из нескольких несовместных вариантов выбирается один ($|A \cup B| = |A| + |B|$); правило произведения - когда делается несколько последовательных независимых выборов ($|A \times B| = |A| \cdot |B|$). Союзы «или» и «и» в условии задачи - главные подсказки. Вместе эти два принципа служат фундаментом всей комбинаторики: из них выводятся формулы перестановок, размещений и сочетаний.