Во многих задачах нужно найти все возможные комбинации — чтобы узнать, сколько их, или выбрать из них лучшую. Перебирать варианты наугад нельзя: легко что-то пропустить или записать дважды. Перебор ведут систематически, по правилу, а записать его помогают таблица и схема-«дерево».
Пример 1 (таблица). Двузначный код составляют из букв К, Л, М, Н, О, У, Ы так, что на первом месте стоит гласная, а на втором — согласная. Строки таблицы — гласные, столбцы — согласные, в каждой клетке — свой код:
| К | Л | М | Н | |
|---|---|---|---|---|
| О | ОК | ОЛ | ОМ | ОН |
| У | УК | УЛ | УМ | УН |
| Ы | ЫК | ЫЛ | ЫМ | ЫН |
Ни один код не пропущен и не повторён: кодов 3 · 4 = 12.
Когда мест в комбинации больше двух, таблицы не хватает — рисуют дерево: от первого символа ведут ветви ко всем возможным вторым, от каждого второго — ко всем возможным третьим и т. д. Каждая ветвь сверху вниз — один вариант.
Пример 2 (дерево). Сколько «слов» из трёх разных букв можно составить из букв П, Р, С, Т? Закрепим на первом месте букву П. Вторая буква — Р, С или Т (три ветви), третья — одна из двух оставшихся (по две ветви): ПРС, ПРТ, ПСР, ПСТ, ПТР, ПТС — шесть слов. Любая из четырёх букв может стоять первой, и для каждой слов столько же: 6 · 4 = 24.
Метод систематического перебора (подсчёт комбинаций из различных символов)
- Закрепить на первом месте один из данных символов.
- Для этого случая выписать все варианты с помощью таблицы, дерева или иначе и сосчитать их.
- Если любой символ может стоять на любом месте, умножить полученное число на количество символов.
- Если на символы наложены ограничения, сосчитать варианты отдельно для символов с разными свойствами и сложить результаты.
Пример 3 (ограничение). Сколько двузначных чисел с различными цифрами можно составить из цифр 0, 3, 5, 8? Ноль не может стоять первым — у него свойство не такое, как у остальных цифр. Для первой цифры 3 вторая — 0, 5 или 8 (три числа), так же для 5 и для 8, а для 0 — ни одного: 3 + 3 + 3 + 0 = 9 чисел.