§ 24. Комбинаторные задачи

Ты забыл последнюю цифру кода от домофона. Сколько кнопок придётся нажать в самом неудачном случае? Последней может оказаться любая цифра от 0 до 9, значит, попыток будет не больше десяти. Ты перебрал все варианты и сосчитал их.

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

Пример 1. У Даши три флажка: красный, синий и жёлтый. Она вешает их в ряд на верёвочку. Сколькими способами это можно сделать?

Решение. Обозначим флажки первыми буквами: К, С, Ж, и разберём случаи по порядку. Если первым висит красный, то синий и жёлтый становятся за ним двумя способами: КСЖ и КЖС. Если первым висит синий — получаем СКЖ и СЖК. Если жёлтый — ЖКС и ЖСК. Других начал у ряда нет, значит, перебор окончен.

Ответ: 6 способов.

Этот перебор удобно нарисовать (рис. 1). Из общей точки вниз идут три ветки — по числу флажков, которые могут оказаться первыми. От каждой ветки отходят ещё по две — по числу оставшихся флажков. Третьему флажку выбора уже нет. Дорожек сверху донизу шесть, и каждая дорожка — это один способ.

Схема похожа на перевёрнутое дерево, поэтому её и называют деревом возможных вариантов. Дерево тем и хорошо, что по нему сразу видно: ни один вариант не потерян и ни один не записан дважды.

Тот же перебор можно записать таблицей (рис. 2). Три строки — это первое, второе и третье места в ряду, а столбцов ровно столько, сколько способов: каждый столбец читается сверху вниз и даёт один вариант.

Запомни: варианты перебирают по порядку — сначала все, что начинаются одинаково, потом следующие.