Комбинаторика
Комбинаторика отвечает на вопрос: сколько разных вариантов можно получить по заданным правилам.
Типичные вопросы:
- Сколько маршрутов ведет из одного пункта в другой?
- Сколькими способами можно выбрать команду?
- Сколькими способами можно распределить призовые места?
- Сколько расписаний можно составить из заданных уроков?
Комбинаторика изучает, как:
- перечислять все допустимые варианты;
- находить их количество, не выписывая каждый вариант вручную.
Задача:
Маша собирается съесть яблоко, сливу и мандарин, но порядок еще не выбрала. Сколькими способами это можно сделать?
Решение:
Обозначим:
- Я — яблоко
- С — слива
- М — мандарин
Например, СМЯ означает: сначала слива, потом мандарин, потом яблоко.
Выпишем варианты в лексикографическом порядке:
Получаем \(6\) вариантов.
В простых задачах варианты можно выписать вручную. Если делать это бессистемно, легко:
- пропустить часть случаев;
- дважды посчитать один и тот же вариант.
Чтобы перебор был корректным, заранее фиксируйте порядок записи и не меняйте его по ходу решения.
- Для чисел используйте порядок по возрастанию.
- Для слов используйте лексикографический порядок.
Лексикографический порядок — это порядок «как в словаре»: сначала сравнивают первые буквы, при равенстве — вторые, затем третьи и так далее.
Те же варианты можно записать и в случайном порядке, например:
СЯМ, МСЯ, ЯМС, СМЯ, ЯСМ, МЯС.
Но в лексикографическом порядке работать проще: сразу видно, какой вариант идет следующим.
Сначала идут варианты на М..., затем на С..., затем на Я....
Ниже — сравнение случайного и лексикографического порядка.
Цепочки
Один вариант удобно записывать как цепочку.
В цепочке порядок элементов важен.
Цепочку можно записывать:
- в круглых скобках: \((\text{М},\ \text{С},\ \text{Я})\);
- слитно (если элементы односимвольные): \(\text{МСЯ}\).
Множество и цепочка — разные объекты:
- \(\{\text{М},\ \text{С},\ \text{Я}\} = \{\text{Я},\ \text{М},\ \text{С}\}\);
- \((\text{М},\ \text{С},\ \text{Я}) \neq (\text{Я},\ \text{М},\ \text{С})\).
Множество отвечает на вопрос «какие элементы выбрали», а цепочка — «в каком порядке выбрали».
Дерево вариантов
Если вариант строится по шагам, удобно использовать дерево вариантов.
Дерево вариантов — схема пошагового выбора.
- каждая развилка показывает выбор на очередном шаге;
- каждый путь от начала до конца задает один вариант;
- все конечные пути вместе дают полный список вариантов.
Если обходить дерево слева направо и располагать ветви по алфавиту, цепочки автоматически получаются в лексикографическом порядке.
Задача:
На рисунке показаны дороги между пунктами \(A\), \(B\), \(C\). Из \(A\) в \(B\) можно попасть двумя способами, а из \(B\) в \(C\) — тремя.
Сколькими способами можно попасть из \(A\) в \(C\) за два перехода?
Решение:
Обозначим дороги:
- из \(A\) в \(B\): \(a, b\);
- из \(B\) в \(C\): \(1, 2, 3\).
Каждый маршрут — цепочка из двух шагов: сначала выбираем букву (\(a\) или \(b\)), затем число (\(1\), \(2\) или \(3\)).
Построим дерево вариантов. Каждый путь от начала до конца — один маршрут.
Выпишем маршруты в лексикографическом порядке:
Получаем \(6\) способов.
Задачи для тренировки
1. Из букв \(A, B, C\) составьте все цепочки длины 2 без повторений в лексикографическом порядке и укажите их количество.
Ответ
\(AB, AC, BA, BC, CA, CB\). Всего \(6\).
2. Из пункта \(X\) в \(Y\) есть 3 дороги (\(a, b, c\)), а из \(Y\) в \(Z\) есть 2 дороги (\(1, 2\)). Выпишите все маршруты из \(X\) в \(Z\) за два перехода и найдите их количество.
Ответ
\(a1, a2, b1, b2, c1, c2\). Всего \(6\).
3. Какие утверждения верны?
i) \(\{A, B, C\} = \{C, B, A\}\)
ii) \((A, B, C) = (C, B, A)\)
iii) Если обходить дерево вариантов слева направо, можно получить лексикографический порядок.
Ответ
Верны i) и iii). Утверждение ii) неверно, потому что в цепочке порядок важен.
4. Упорядочите слова в лексикографическом порядке:
Ответ
Сначала сравниваем первые буквы (они одинаковые), затем вторые (тоже одинаковые), потом третьи: \(\text{л} < \text{м} < \text{с} < \text{х}\).
По материалам:
1. И. В. Яковлев. Материалы по математике: подготовка к олимпиадам и ЕГЭ. mathus.ru
2. IBDP Mathematics - Core Topics HL 1