Комбинаторика

В задании 8 обычно нужно посчитать кодовые слова, числа или другие последовательности, которые удовлетворяют условиям.

Для таких задач важно не заучить все формулы, а научиться видеть, как устроен перебор: сколько есть позиций и сколько вариантов для каждой из них.

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

Главная цель этой статьи — научиться выбирать нужный способ подсчёта исходя из формулировки задачи.

Что такое комбинаторика

Комбинаторика — раздел математики, в котором изучают способы выбора и расположения объектов, а также подсчитывают число возможных вариантов.

Объектами могут быть буквы, цифры, фрукты или люди. Они не обязаны быть уникальными: задача может разрешать или запрещать повторения.

В задании 8 обычно работаем с алфавитом — набором разрешённых символов. Из них составляются слова заданной длины.

Перед подсчётом ответьте на четыре вопроса:

1. Сколько позиций нужно заполнить?
2. Сколько символов можно поставить на каждую позицию?
3. Важен ли порядок символов?
4. Могут ли символы повторяться?

Например, из букв A, B и C можно составить 3³ = 27 трёхбуквенных слов, если повторения разрешены.

Если буквы не должны повторяться, на первую позицию есть 3 варианта, на вторую — 2, на третью — 1. Получаем 3 · 2 · 1 = 6 слов.

В обоих примерах порядок важен: ABC и BAC — разные слова. Именно такие упорядоченные последовательности чаще всего встречаются в задании 8.

Основные понятия комбинаторики

Для начала закрепим термины, которые понадобятся дальше.

Множество — это набор различимых объектов. Например, {A, B, C} — множество из трёх букв.

В задачах про слова такое множество букв называют алфавитом.

Выбор — это отбор нескольких элементов из множества. Но по одному слову «выбор» нельзя решить, важен ли порядок. Это всегда нужно уточнить по условию.

Например, из {A, B, C} можно выбрать A и B.

Если порядок не важен, пары AB и BA считаются одним вариантом.

Если порядок важен, AB и BA считаются двумя разными вариантами.

В задании 8 мы обычно составляем слова или числа, поэтому порядок почти всегда важен.

Расположение — это упорядоченная последовательность. При его подсчёте разные порядки считаются разными вариантами.

Если из букв A, B и C составляем двухбуквенные слова без повторов, получаем:

AB, AC, BA, BC, CA, CB

Факториал (n!) — произведение всех целых чисел от 1 до n: n! = 1 · 2 · … · n. Отдельно принято, что 0! = 1.

Большая часть подсчётов строится на двух правилах: суммы и произведения.

Правило суммы используем для непересекающихся вариантов: если A можно выбрать m способами, а B — n способами, то A или B можно выбрать m + n способами.

Главное слово здесь — «или». Один и тот же вариант не должен попасть сразу в обе группы, иначе мы посчитаем его дважды.

В магазине есть 3 вида яблок и 5 видов груш. Один фрукт можно купить 3 + 5 = 8 способами.

Правило произведения используем, когда нужно выполнить несколько последовательных шагов. Если первый шаг можно выполнить m способами, а второй — n, всего получим m · n вариантов.

Главное слово здесь — «и»: мы делаем и первый, и второй шаг.

Если в ресторане 4 основных блюда и 5 напитков, то обед из блюда и напитка можно составить 4 · 5 = 20 способами.

Для задания 8 правило произведения особенно важно. Мы последовательно выбираем символ для каждой позиции.

Запомнить легко: «или» — складываем, «и» — умножаем, всё прямо как в логических операциях (дизъюнкция и конъюнкция).

Теперь разберём, как из этих правил получаются основные комбинаторные формулы.

Перестановки

Перестановка — упорядочивание всех n элементов. Каждый элемент используется ровно один раз, а порядок важен.

Возьмём три различных фрукта: яблоко, банан и вишню.

На первое место можно положить любой из 3 фруктов, на второе — любой из 2 оставшихся, а на третье — последний. Получаем 3 · 2 · 1 = 6 вариантов.

1. Яблоко, банан, вишня
2. Яблоко, вишня, банан
3. Банан, яблоко, вишня
4. Банан, вишня, яблоко
5. Вишня, яблоко, банан
6. Вишня, банан, яблоко

Для n различных элементов получаем n · (n − 1) · … · 1 = n! перестановок.

Для трёх фруктов: P₃ = 3! = 3 · 2 · 1 = 6.

Если среди n объектов есть одинаковые, получаем перестановки с повторениями.

Пусть есть 10 фруктов: 5 яблок, 2 банана, 2 вишни и 1 груша. Нужно найти число всех возможных перестановок с повторениями.

Если бы все фрукты были различными, получилось бы 10! порядков. Но перестановка одинаковых яблок не создаёт нового варианта.

Каждый порядок мы посчитали 5! раз из-за яблок, 2! раза из-за бананов и ещё 2! раза из-за вишен.

Чтобы убрать повторный подсчёт, делим 10! на 5! · 2! · 2! · 1!.

В общем случае, если элементы повторяются n₁, n₂, …, nₖ раз и n₁ + n₂ + … + nₖ = n, используем формулу ниже.

В знаменателе стоят факториалы числа повторений каждого вида элементов.

Получаем формулу перестановок с повторениями:

Для нашего примера:

Размещения

Размещение из n элементов по m — это выбор m элементов, при котором порядок важен.

Возьмём яблоко, банан и вишню. Нужно выбрать два разных фрукта и расположить их по порядку.

На первое место есть 3 кандидата, на второе — 2. Получаем 3 · 2 = 6 размещений:

1. Яблоко, Банан
2. Банан, Вишня
3. Яблоко, Вишня
4. Вишня, Яблоко
5. Банан, Яблоко
6. Вишня, Банан

Для размещений без повторений на первом месте есть n вариантов, на втором — n − 1 и так далее. Получаем формулу:

В нашем примере n = 3, m = 2:

Если один и тот же элемент можно брать несколько раз, получаем размещения с повторениями.

К шести уже полученным парам добавятся яблоко-яблоко, банан-банан и вишня-вишня. Всего получается 9 вариантов.

На каждую из m позиций можно независимо поставить любой из n элементов. По правилу произведения получаем nᵐ вариантов:

Для трёх фруктов и двух позиций: 3² = 9. Именно размещения с повторениями чаще всего описывают кодовые слова в задании 8.

Сочетания

Сочетание из n элементов по m — выбор m элементов без учёта порядка. Например, пары «яблоко, банан» и «банан, яблоко» считаются одним сочетанием.

Добавим к трём фруктам виноград.

Сколькими способами можно выбрать два разных фрукта, если порядок не важен?

Получаем 6 пар:

1. Банан и виноград
2. Банан и вишня
3. Банан и яблоко
4. Вишня и виноград
5. Виноград и яблоко
6. Вишня и яблоко

Каждое сочетание из m элементов можно упорядочить m! способами. Поэтому число размещений делим на m! и получаем формулу:

Для n = 4 и m = 2:

Если элементы можно брать повторно, а порядок по-прежнему не важен, получаем сочетания с повторениями.

Пусть в магазине есть 4 вида фруктов. Сколькими способами можно купить 2 фрукта, если можно взять два одинаковых?

К шести парам из разных фруктов добавятся ещё четыре пары из одинаковых. Всего 10 вариантов.

Общая формула сочетаний с повторениями:

Подставим n = 4 и m = 2:

Как выбрать нужную операцию

Перед выбором формулы ответьте на три вопроса: важен ли порядок, все ли n элементов используются и разрешены ли повторения.

Дальше двигайтесь по короткой схеме:

• Порядок важен, используются все n элементов — перестановки.
  • Порядок важен, выбирается m из n — размещения.
  • Порядок не важен, выбирается m из n — сочетания.
• Если повторения разрешены, используйте соответствующую формулу с повторениями.
• В задании 8 кодовое слово — это упорядоченная последовательность. Поэтому чаще всего нужны размещения с повторениями или без них. Сочетания нужны реже.

Итоги

На этом мы закончим знакомство с комбинаторикой. В следующей статье познакомимся с функциями product() и permutations() из модуля itertools. С их помощью можно перебирать кодовые слова прямо в Python.