8.3. Решение комбинаторных задач методом перебора

Метод перебора — выписать в определённом порядке все возможные варианты и сосчитать их. Чтобы ни один вариант не потерять и ни один не посчитать дважды, варианты выписываем систематически.

Дерево возможных вариантов — схема перебора. Корень дерева обозначается знаком $*$, каждый уровень — один шаг выбора, каждый путь от корня до конечной точки (ветка) — один вариант. Число конечных точек равно числу вариантов.

1. Объекты обозначаем коротко: имена — заглавными буквами, предметы или цвета — цифрами.

2. Варианты выписываем по порядку: ставим на первое место первый элемент и перечисляем все его продолжения, затем переходим к следующему элементу (в алфавитном порядке или по возрастанию).

3. Сначала выясняем, важен ли порядок. В задачах о дежурствах, составлении чисел, рассадке порядок важен ($15$ и $51$ — разные числа). В задачах об отрезках, рукопожатиях, выборе двух человек порядок не важен ($AB$ и $BA$ — один отрезок), поэтому каждую пару пишем один раз, в алфавитном порядке, — получается «треугольная таблица».

4. Если в каждой ветви дерева одинаковое число ответвлений, число вариантов находим умножением: если на первом шаге $3$ возможности, а на втором $2$, то всего $3 \cdot 2 = 6$.

Пример 1: сколько двузначных чисел с неповторяющимися цифрами можно записать из цифр $1$, $5$, $8$? Цифра десятков — $1$, $5$ или $8$ ($3$ ветки), цифра единиц — одна из двух оставшихся (из каждой по ветки). Числа: , , , , , — всего .

На рисунке показано дерево возможных вариантов для этого примера: $6$ веток — $6$ чисел.

Пример 2: четыре друга $A$, $B$, $C$, $D$ по одному разу пожали друг другу руки. Порядок не важен, поэтому: $AB$, $AC$, ; , ; . Всего рукопожатий.

На рисунке каждое рукопожатие показано отрезком, соединяющим две точки: всего $6$ отрезков.

Частая ошибка: когда порядок не важен, считать $AB$ и $BA$ двумя вариантами (ответ получается вдвое больше); при составлении чисел ставить цифру $0$ на первое место; выписывать варианты беспорядочно и пропускать один из них.