Комбинаторика
Комбинаторика отвечает на вопрос: «Сколько существует вариантов?»
Сколько маршрутов ведёт из одного пункта в другой?
Сколькими способами можно выбрать команду? сколько способов выбрать призеров турнипа?
Сколько разных расписаний можно составить из заданных уроков?
Это задачи комбинаторики.
Комбинаторика - раздел математики, который изучает количество вариантов при заданных правилах.
Задача:
Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой последовательности. Сколькими способами это можно сделать?
Решение:
Обозначим:
• Я - яблоко • С - слива • М - мандарин
Тогда СМЯ - это вариант, где сначала съедают сливу, потом мандарин, потом яблоко.
Выпишем все варианты в лексикографическом порядке:
Итого 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