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

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

Статья

Конспект

Задачи

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

Если объект из группы 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 букв!

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

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

Источники7

Список внешних источников, которые использовались при написании этого материала. Если рядом с названием стоит звездочка, то это избранный источник и с ним стоит ознакомиться, если вы хотите глубже погрузиться в материал.

Комбинаторика

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 7-е издание, МЦНМО, 2019

Почти идеальная подача теории через жизненные примеры. Интересные задачи. Широчайший охват тем, в том числе и из высшей математики.

1. Суеверный председатель

2. Лото

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

Brilliant

Образовательная платформа по математике и IT

Прекрасный сайт с наглядными пояснениями, хорошими примерами и упражнениями.

Rule of Product

Википедия

Свободная энциклопедия