Перебор вариантов. Комбинаторные правила

Комбинаторика изучает задачи выбора и расположения элементов некоторого (обычно конечного) множества по заданным правилам.

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

1. Из каждой из $5$ точек выходит $4$ отрезка: $4 \cdot 5 = 20$.
2. Но каждый отрезок посчитан дважды — от одного конца и от другого. Делим на $2$: $\ 10$.
3. Другой способ: из первой точки $4$ новых отрезка, из второй $3$, затем $2$ и $1$: $4 + 3 + 2 + 1 = 10$.

В классе $12$ мальчиков и $15$ девочек: выбрать одного человека можно $12 + 15 = 27$ способами.

Для нескольких групп: $3$ яблока, $4$ апельсина и $6$ мандаринов — один плод выбирается $3 + 4 + 6 = 13$ способами.

Пару «мальчик и девочка» из $12$ мальчиков и $15$ девочек выбирают $12 \cdot 15 = 180$ способами.

Для наборов: яблоко, апельсин и мандарин — $3 \cdot 4 \cdot 6 = 72$ способа.

Запомнить: «или» — складываем, «и» — умножаем.

1. а) Старосту — любой из $25$, заместителя — любой из $24$ оставшихся: $25 \cdot 24 = 600$.
2. б) Маршрут — тройка дорог: $2 \cdot 3 \cdot 2 = 12$.

1. На каждое буквенное место — $30$ вариантов, на каждое цифровое — $10$.
2. По правилу умножения: $30 \cdot 30 \cdot 30 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 270\,000\,000$.

• Перебор: выписываем варианты по порядку или строим дерево.
• Правило сложения — «или»: $m + n$.
• Правило умножения — «и», пара или набор: $m \cdot n \cdot \ldots$
• Если каждый вариант посчитан дважды (отрезок, рукопожатие) — делим на $2$.