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

Зачем это нужно

Сколькими способами можно составить обед из одного супа и одного второго, если в меню 3 супа и 4 вторых? Сколько трёхзначных чисел можно записать цифрами 1, 2, 3? Сколько вариантов пароля из 4 цифр? Задачи вида «сколькими способами» называют комбинаторными.

Комбинаторика нужна, чтобы считать варианты, не выписывая их все: при составлении расписаний, в шифровании, в генетике, в теории вероятностей. В 7–9 классах вы узнаете о перестановках, размещениях и сочетаниях, а начинается всё с аккуратного перебора и одного правила.

Систематический перебор

Если вариантов немного, их можно перечислить. Главное — делать это по системе, чтобы ничего не пропустить и ничего не повторить.

Пример. Сколько двузначных чисел можно составить из цифр 1, 2, 3 (цифры могут повторяться)?

Перебираем по первой цифре:

• начинаются с 1: 11, 12, 13;
• с 2: 21, 22, 23;
• с 3: 31, 32, 33.

Всего 9 чисел. Порядок «сначала первая цифра, потом вторая» гарантирует, что ничего не потеряно.

Таблица вариантов

Когда выбор состоит из двух шагов, удобна таблица: строки — варианты первого шага, столбцы — второго.

Каждая клетка — один обед. Клеток $3 \cdot 4 = 12$.

Дерево вариантов

Когда шагов больше двух, рисуют дерево вариантов: от «корня» отходят ветки — варианты первого шага, от каждой ветки — варианты второго, и так далее. Число «листьев» на концах — число всех вариантов.

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

Заметили закономерность? Если первый выбор можно сделать $m$ способами, а после него второй — $n$ способами, то пару выборов можно сделать $m \cdot n$ способами. Для трёх шагов — $m \cdot n \cdot k$, и так далее.

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

Разобранный пример 1

Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры могут повторяться?

1. Первая цифра — 5 вариантов, вторая — 5, третья — 5.
2. По правилу умножения: $5 \cdot 5 \cdot 5 = 125$.

Ответ: 125.

Разобранный пример 2

А если цифры не должны повторяться?

1. Первая цифра — 5 вариантов.
2. Вторая — любая, кроме уже взятой: 4 варианта.
3. Третья — 3 варианта.
4. $5 \cdot 4 \cdot 3 = 60$.
5. Проверка на маленьком случае: из цифр 1, 2, 3 без повторений двузначных чисел должно быть $3 \cdot 2 = 6$: 12, 13, 21, 23, 31, 32. Сходится.

Ответ: 60.

Осторожно с нулём

Если среди цифр есть 0, первой цифрой он быть не может. Сколько трёхзначных чисел можно составить из цифр 0, 1, 2 (с повторениями)? Первая цифра — только 1 или 2 (2 варианта), вторая и третья — по 3: $2 \cdot 3 \cdot 3 = 18$.

Перестановки

Сколькими способами можно расставить на полке 4 разные книги? На первое место — 4 варианта, на второе — 3, на третье — 2, на последнее — 1: $4 \cdot 3 \cdot 2 \cdot 1 = 24$. Такие расстановки называют перестановками. Произведение $1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ обозначают $n!$ («эн факториал»): $4! = 24$, $5! = 120$.

Правило сложения

Кроме правила умножения, есть правило сложения: если выбор можно сделать или одним из $m$ способов, или одним из $n$ других способов (и эти способы не пересекаются), то всего способов $m + n$. Например, на десерт можно взять или одно из 3 пирожных, или одно из 2 мороженых — всего $3 + 2 = 5$ вариантов. Запомните: «и то, и другое» — умножаем; «или то, или другое» — складываем.

Типичные ошибки

• Перебирать варианты хаотично и терять часть из них.
• Складывать числа вариантов вместо умножения (3 супа и 4 вторых — это не 7 обедов, а 12).
• Не учитывать, что выбранный элемент нельзя использовать повторно, когда повторения запрещены.
• Ставить 0 на первое место в числе.
• Считать одинаковыми варианты, которые отличаются порядком, когда порядок важен (12 и 21 — разные числа).

Что дальше

• Множества и операции над ними — в курсе вероятности и статистики изучим множества и операции над ними, а затем — классическую вероятность, где правило умножения помогает считать исходы.