Правило умножения

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

    graph TD
        root[Базовый подсчет комбинаций]:::featured -->|Разбить на группы и сложить| sumRule[Правило суммы]
        root -->|Последовательно выбирать элементы| productRule[Правило произведения]

Правило умножения

Если объект из группы A можно выбрать a разными способами, и при любом сделанном выборе объект из группы B можно выбрать b способами, то есть всего $a\cdot b$ вариантов выбрать пару объектов (один из A, второй из B).

Другими словами, выбор «A и B» можно сделать $a\cdot b$ способами.

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

Красивый забор

Строительная фирма специализируется на изготовлении красивых заборов. Она предлагает на выбор 5 расцветок и 6 узоров. Сколько разных видов заборов может построить эта фирма?

Решение

На выбор есть 5 цветов. Любой из 5 выбранных цветов приводит к выбору из 6 узоров. По правилу умножения получаем $5\cdot 6 = 30$ видов заборов.

Обобщенное правило умножения

Если элемент $a_1$ можно выбрать $n_1$ способами, после любого выбора элемент $a_2$ можно выбрать $n_2$ способами, $\ldots$ после любого выбора предыдущих $k-1$ элементов элемент $a_k$ можно выбрать $n_k$ способами, то все эти k элементов можно выбрать $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ способами.

Стань кем угодно...

В ролевой компьютерной игре есть редактор, в котором игрок создает главного героя. Можно выбрать пол и одну из 4 рас: человек, эльф, дворф или орк. Еще можно выбрать один из 8 оттенков кожи, 5 вариантов лица, 20 типов причесок. Сколько разных персонажей можно создать с помощью такого редактора?

Решение

2 варианта выбрать пол, 4 расы, 8 оттенков кожи, 5 вариантов лица и 20 причесок. Применяем правило умножения:

2 \cdot 4 \cdot 8 \cdot 5 \cdot 20 = 6 \ 400

Итак, в игре можно создать 6400 разных персонажей.

Поиграем в слова!

Сколько любых (даже бессмысленных) слов содержащих 5 букв можно составить из 33 букв русского алфавита так, чтобы любые две соседние буквы были различны?

Решение

На место первой буквы в слове годится любая из 33 букв алфавита. Вне зависимости от выбранной первой буквы, дальше может быть любая буква алфавита кроме той, что мы использовали для первого места. Поэтому есть 32 варианта выбрать букву для второго места в слове. Третья буква опять же может быть любой, кроме той, что стоит на втором месте в слове, то есть снова 32 варианта. И так далее.

По правилу умножения версии получаем:

33 \cdot 32 \cdot 32 \cdot 32 \cdot 32 = 34 \ 603 \ 008

Итак, используя 33 буквы без повторения соседних можно выписать почти 35 миллионов слов содержащих 5 букв!

Применимость правила умножения

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