Комбинаторика
Комбинаторика отвечает на главный вопрос: «сколько способов?»
То есть сколько разных вариантов можно получить, если выбирать, располагать или составлять объекты по правилам.
Сколькими способами можно выбрать три яблока из корзины?
Сколько вариантов школьного расписания существует?
Сколько разных маршрутов ведёт из дома в школу?
Такими задачами занимается комбинаторика.
В комбинаторных задачах нас интересует число вариантов, которые можно составить из заданного набора объектов и которые удовлетворяют условиям задачи.
В простых задачах варианты можно выписать вручную.
Но если делать это без системы, легко:
- пропустить вариант;
- посчитать один и тот же дважды.
Поэтому при переборе полезно придерживаться двух правил.
1) Сначала договоримся, что считается одним вариантом и как мы его записываем.
Запись должна быть однозначной: одному варианту — одна запись.
2) Выписываем варианты в строгом порядке:
по алфавиту (для букв) или по возрастанию (для чисел).
Если вариант — цепочка шагов, используем лексикографический порядок (как в словаре):
сначала сравниваем первый элемент;
если он одинаковый — сравниваем второй;
если и он одинаковый — третий и т.д.
Задача:
Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой последовательности. Сколькими способами Маша может выбрать эту последовательность?
Решение:
Обозначим:
- \(\text{Я}\) – яблоко,
- \(\text{С}\) – слива,
- \(\text{М}\) – мандарин.
Тогда, например, \(\text{СМЯ}\) – это вариант, когда Маша сначала съест сливу, потом – мандарин, потом – яблоко.
Выпишем варианты в лексикографическом порядке:
Получилось 6 вариантов.
Цепочки
Очень часто «один вариант» – это цепочка (упорядоченный набор). Тогда порядок элементов важен.
Цепочка – это упорядоченный набор (последовательность): в ней важен порядок элементов.
Цепочку обычно обозначают в круглых скобках: \((\text{М},\ \text{С},\ \text{Я})\) или \((\text{Я},\ \text{М},\ \text{С})\).
Иногда для простоты записывают слитно, если каждый элемент – один символ: \(\text{МСЯ}\), \(\text{ЯМС}\), \(\text{СЯМ}\).
Множество и цепочка – это разные вещи
В множестве порядок элементов не важен, а в цепочке – важен.
- \(\{\text{М},\ \text{С},\ \text{Я}\}\) = \(\{\text{Я},\ \text{М},\ \text{С}\}\);
- \((\text{М},\ \text{С},\ \text{Я})\) \(\neq\) \((\text{Я},\ \text{М},\ \text{С})\).
Множество отвечает на вопрос «какие элементы взяли», а цепочка – на вопрос «в каком порядке их взяли».
В примере про Машу:
- каждый вариант (\(\text{МСЯ}\), \(\text{СМЯ}\) и т.д.) – это цепочка из трёх букв, потому что порядок важен;
- ответ задачи – это множество цепочек (его можно записать в любом порядке):
Дерево вариантов
Ещё один удобный способ перечислять цепочки так, чтобы не пропустить ни один вариант и не ошибиться, – построить дерево вариантов.
Идея простая: если цепочка строится по шагам, то на каждом шаге мы рисуем развилку со всеми возможными выборами.
В дереве вариантов:
- каждая «развилка» – это выбор на очередном шаге;
- путь от корня до листа задаёт одну цепочку (один вариант);
- листья (концы ветвей) – это все получившиеся цепочки.
Если обходить дерево слева направо и на каждом шаге располагать ветви в алфавитном порядке
(\(\text{М}\), затем \(\text{С}\), затем \(\text{Я}\)), то цепочки автоматически получаются в лексикографическом порядке.
Задача:
На рисунке показаны дороги между пунктами \(A\), \(B\), \(C\). Из \(A\) в \(B\) можно попасть двумя способами, а из \(B\) в \(C\) – тремя.
Сколькими способами можно попасть из \(A\) в \(C\) за два перехода?
Решение:
Обозначим дороги из \(A\) в \(B\) строчными буквами: \(a\), \(b\).
Обозначим дороги из \(B\) в \(C\) числами: \(1\), \(2\), \(3\).
Тогда каждый маршрут из \(A\) в \(C\) ровно за два перехода задаётся цепочкой из двух шагов: сначала выбираем букву
(\(a\) или \(b\)), затем число (\(1\), \(2\) или \(3\)).
Построим дерево вариантов. Каждый путь от корня к листьям – это один маршрут (одна цепочка), например \(a2\) или \(b3\).
Выпишем все цепочки в лексикографическом порядке: сначала \(a\), потом \(b\); при одинаковой первой букве – по возрастанию второй позиции.
Итого 6 способов.
Цепочки удобно использовать для описания маршрутов, последовательностей действий и «выбора по шагам». А чтобы такие цепочки перечислить аккуратно и ничего не пропустить, часто строят дерево вариантов: каждый путь от корня до листа даёт одну цепочку.
В задачах на подсчёт часто нужно узнать число вариантов, не выписывая их по одному, а сводя задачу к нескольким стандартным приёмам. Дальше мы будем использовать:
- правило суммы и правило произведения – как считать, когда варианты разбиваются на непересекающиеся случаи или когда выбор делается по шагам (часто это видно по дереву вариантов);
- перестановки и размещения – как считать цепочки, когда порядок выбранных элементов важен (перестановки – используем все элементы, размещения – выбираем только часть);
- сочетания – как считать, когда порядок не важен и нас интересует только набор выбранных элементов.