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

Комбинаторика начинается с вопроса «сколько всего вариантов?». Перебирать варианты по одному долго и ненадёжно: легко что-нибудь пропустить или посчитать дважды. Правило умножения позволяет назвать ответ, не выписывая перебор целиком.

Задача о делегациях. На переговоры приехали две делегации: в первой 3 дипломата, во второй 4. Каждый здоровается за руку с каждым дипломатом чужой делегации, а внутри своей делегации руки не жмут. Сколько случилось рукопожатий? Изобразим происходящее графом (рис. 1): слева три вершины первой делегации, справа четыре вершины второй, а рукопожатие — ребро между ними. Пересчитывать рёбра по одному не нужно. Из каждой левой вершины выходит ровно 4 ребра, по одному к каждой правой; левых вершин 3, поэтому рёбер 3 · 4 = 12.

Правило умножения. Если в множестве A ровно n элементов, а в множестве B ровно k элементов, то различных упорядоченных пар (a; b), где a — элемент A, а b — элемент B, всего nk.

Например, для A = {a, b, c} и B = {r, q, s, t} пары выписываются подряд: сначала четыре пары, начинающиеся с a, затем такие же четыре с b, затем четыре с c. Получаются три четвёрки, то есть те же 12 пар, что и рёбер на рисунке 1.

Слово «упорядоченная» здесь главное: в паре сначала стоит элемент первого множества, потом второго, и менять их местами нельзя. Пары (a; b) и (b; a) считаются разными, даже когда оба элемента взяты из одного и того же множества.

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

Пример 1. Дано: игральную кость бросают два раза, результат опыта — пара выпавших чисел, записанная по порядку. Сколько всего результатов? Решение. Первое число можно получить шестью способами, второе — тоже шестью, и от первого броска второй никак не зависит. По правилу умножения получаем 6 · 6 = 36. Все результаты видны в таблице (рис. 2): строка — первый бросок, столбец — второй, клеток ровно 36. Результаты «сначала 2, потом 5» и «сначала 5, потом 2» стоят в разных клетках, потому что порядок здесь важен. Ответ: 36.

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