Правило суммы и правило произведения — Основные принципы комбинаторного подсчёта
Зачем изучать это в алгебре? Принципы подсчёта — это мост между алгеброй и комбинаторикой. Они позволяют вычислить общее количество исходов в различных ситуациях — пароли, номерные знаки, рассадка гостей — используя лишь сложение и умножение. Эти идеи встречаются повсюду: в теории вероятностей, функциях и даже в анализе алгоритмов.
1. Правило произведения (Принцип умножения)
Интуитивная идея
Если вам нужно выполнить задачу, которая разбивается на последовательность шагов, и шаги не зависят друг от друга, вы умножаете количество вариантов на каждом шаге.
Правило произведения: Если процедуру можно разбить на последовательность из $k$ шагов, причём шаг 1 можно выполнить $n_1$ способами, шаг 2 — $n_2$ способами, …, шаг $k$ — $n_k$ способами, то общее количество способов выполнить процедуру равно:
$$ n_1 \cdot n_2 \cdot n_3 \cdots n_k $$
Теоретико-множественная форма
Для конечных множеств $A_1, A_2, \ldots, A_k$ мощность их декартова произведения равна:
$$ |A_1 \times A_2 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k| $$Простой пример
Допустим, вы выбираете наряд. У вас есть 4 рубашки и 3 пары брюк. Выбор наряда — это задача из двух шагов (выбрать рубашку И выбрать брюки), поэтому общее количество нарядов = $4 \times 3 = 12$.
Интерактивная визуализация — доступна в полном уроке
Ключевое слово: Правило произведения применяется, когда вы выполняете шаг 1 И шаг 2 И шаг 3 …