Основы комбинаторики: перестановки, размещения, сочетания

В этой формуле для получения следующего элемента необходимо знать предыдущий.

Правило суммы — если объект A можно выбрать способами, а объект B можно выбрать способами, то объект «A или B» можно выбрать n + m способами.

Правило произведения — если объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами, то для пары «A и B» есть n ∙ m вариантов выбора.

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

Перестановка n объектов/элементов — это способ их последовательного расположения с учётом порядка. Например, abc, bca и cab — это разные перестановки трёх букв.

Перестановку n объектов ещё называют перестановкой длины n. Количество всех таких перестановок обозначается как Pₙ.

Пример. На странице интернет-магазина одежды размещены три футболки. Если поменять их расположение на странице, получится новая перестановка. Сколькими способами можно расположить футболки на странице?

Решение. Три футболки можно расположить на странице 6 способами: P₃ = 3! = 1 ∙ 2 ∙ 3.

Пример. Чтобы выполнить ежедневный квест, игроку нужно принести магу корзину с четырьмя кристаллами разного цвета. Первой необходимо найти корзину, а кристаллы можно сложить в неё в произвольном порядке. Как найти число способов выполнить задание?

Решение. Для выполнения квеста нужно 5 предметов. Корзину всегда находят первой, поэтому её позиция зафиксирована. Порядок сбора 4 оставшихся предметов равен числу перестановок 4 элементов. Всего есть 4! = 24 способа выполнить задание.

Когда порядок расстановки важен, говорят о размещении.

Размещение из n по k — это упорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть некая перестановка k выбранных элементов из n.

Количество размещений из n по k обозначают и вычисляют так:

В отличие от перестановки, у размещения два параметра: из скольких элементов выбирают (n) и сколько именно выбирают (k).

Порядок выбора элементов важен, когда:

● Выбирают несколько элементов для разных целей, разных дней, разных ролей.
● В задачах на расположение, когда элементы различимы. Например, когда надо выбрать несколько человек из группы и разместить их на креслах в кинотеатре. Люди разные, поэтому имеет значение, кто где сядет.

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

Решение. Порядок выбора важен, поэтому выбрать четыре ресторана поможет правило произведения: существует 9 ∙ 8 ∙ 7 ∙ 6 = 3024 способа. Это как раз и есть количество размещений из 9 по 4.

Пример. Сколькими способами можно заполнить спортивный пьедестал из трёх мест, если есть 10 претендентов?

Решение. Выбрать упорядоченную тройку можно 10 ∙ 9 ∙ 8 = 720 способами. По формуле для количества размещений это считается так:

Когда порядок выбора или расположения не важен, говорят о сочетании.

Сочетание из n по k — это неупорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть набор, для которого порядок выбора не имеет значения.

Количество сочетаний из n по k обозначают и вычисляют так:

Порядок выбора или расстановки не важен, когда:

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

Пример. Из 9 актёров выбирают четырёх для массовки. Порядок выбранных людей не важен. Сколько есть способов выбрать актёров?

Решение. Чтобы получить количество вариантов выбора 4 из 9 без учёта порядка, нужно

Это количество сочетаний из 9 по 4: сначала нашли количество способов выбрать 4 из 9, потом «склеили» все варианты с одним набором актёров, но разным порядком.

Пример. В сувенирном магазине продаются 6 видов кружек. Сколько есть способов выбрать 4 разные?

Решение. Общее количество перестановок для 6 элементов нужно разделить на (6 – 4)! и ещё на 4!, так как не нужно учитывать ни перестановки «невыбираемых» кружек, ни порядок среди выбираемых.

Его называют свойством симметрии для количества сочетаний.