Перестановки, размещения и сочетания

Формулы для числа упорядоченных и неупорядоченных выборок без повторений, свойства сочетаний

Три типа выборок

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

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

Перестановкой из n элементов называют любое упорядоченное расположение всех n элементов. Число перестановок из n элементов обозначают Pₙ и вычисляют как факториал:

$P_{n} = n!$

Пример. Число способов рассадить 4 человек на 4 стула равно P₄=4!=24.

Размещения

Размещением из n элементов по k называют любой упорядоченный набор из k различных элементов, выбранных из данных n (k≤n). Число размещений обозначают Aₙᵏ и вычисляют по формуле:

$A_{n}^{k} = \frac{n!}{(n - k)!} = n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)$

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

Пример 1: размещения

Условие. В группе 10 человек. Сколькими способами можно выбрать старосту, заместителя старосты и профорга (три различные должности, один человек не может занимать две должности одновременно)?

Решение. Поскольку должности различны (порядок выбора важен), применяем формулу размещений при n=10, k=3:

$A_{10}^{3} = 10 \cdot 9 \cdot 8 = 720$

Сочетания

Сочетанием из n элементов по k называют любой неупорядоченный набор (подмножество) из k элементов, выбранных из данных n. В отличие от размещений, здесь не важен порядок выбранных элементов — важен только сам состав набора. Число сочетаний обозначают Cₙᵏ (или биномиальным коэффициентом) и вычисляют по формуле:

$C_{n}^{k} = \frac{n!}{(k! \cdot (n - k)!)} = \frac{A_{n}^{k}}{k!}$

Последняя форма записи наглядно показывает связь между размещениями и сочетаниями: поскольку каждый неупорядоченный набор из k элементов можно упорядочить k! различными способами, размещений в k! раз больше, чем сочетаний.

Пример 2: сочетания

Условие. В группе 10 человек. Сколькими способами можно выбрать делегацию из 3 человек для участия в конференции (все члены делегации равноправны, должности не различаются)?

Решение. Поскольку порядок выбора не важен, применяем формулу сочетаний:

$C_{10}^{3} = \frac{10!}{(3! \cdot 7!)} = \frac{(10 \cdot 9 \cdot 8)}{(3 \cdot 2 \cdot 1)} = \frac{720}{6} = 120$

Обратите внимание: результат ровно в 3!=6 раз меньше, чем в примере 1 с размещениями, — именно во столько раз каждую тройку людей можно упорядочить.

Как распознать тип задачи

Признак задачи	Тип выборки	Формула
`Все n объектов, порядок важен`	`перестановки`	`Pₙ=n!`
`Часть k из n объектов, порядок важен (роли различны)`	`размещения`	`Aₙᵏ=n!/(n−k)!`
`Часть k из n объектов, порядок не важен (равноправная группа)`	`сочетания`	`Cₙᵏ=n!/(k!(n−k)!)`

Основные свойства сочетаний

$C_{n}^{0} = C_{n}^{n} = 1$

$C_{n}^{k} = C_{n}^{n - k} (с и м м е т р и ч н о с т ь)$

$C_{n}^{k - 1} + C_{n}^{k} = C_{n + 1}^{k} (ф о р м у л а П а с к а л я)$

Свойство симметричности Cₙᵏ=Cₙⁿ⁻ᵏ имеет ясный смысл: выбрать k элементов из n — то же самое, что выбрать, какие (n−k) элементов останутся невыбранными, поэтому число способов совпадает. Формула Паскаля лежит в основе построения треугольника Паскаля, каждое число которого равно сумме двух чисел над ним, а также связана с биномом Ньютона, о котором пойдёт речь в следующей статье.

Пример 3: комбинирование сочетаний с правилом произведения

Условие. В классе 15 мальчиков и 12 девочек. Сколькими способами можно выбрать команду из 3 мальчиков и 2 девочек?

Решение. Выбор мальчиков и выбор девочек — независимые этапы, поэтому по правилу произведения перемножаем число сочетаний для каждой группы:

$N = C_{15}^{3} \cdot C_{12}^{2} = 455 \cdot 66 = 30030$

Перестановки с повторениями

Если среди n объектов есть одинаковые (например, буквы в слове, где некоторые буквы повторяются), число различных перестановок меньше n!, поскольку перестановка одинаковых объектов местами не создаёт новой комбинации. Если среди n объектов есть группы одинаковых элементов размером n₁, n₂, …, n_m (n₁+n₂+…+n_m=n), число различных перестановок равно:

$P (n_{1}, n_{2}, \dots, n_{m}) = \frac{n!}{(n_{1} {! \cdot n}_{2}! \cdot \dots {\cdot n}_{m}!)}$

Пример 4: перестановки с повторениями

Условие. Сколько различных перестановок букв в слове «МАТЕМАТИКА»?

Решение. В слове 10 букв: М повторяется 2 раза, А — 3 раза, Т — 2 раза, остальные буквы (Е, И, К) встречаются по одному разу:

$P = \frac{10!}{(2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!)} = \frac{3628800}{24} = 151200$

Типичные ошибки

Главная ошибка — спутать размещения и сочетания, то есть не заметить (или ошибочно предположить), важен ли порядок выбора в конкретной задаче. Признак того, что нужны размещения, — наличие различающихся ролей или позиций (первое место, второе место, разные должности); признак сочетаний — равноправная группа без различия ролей. Вторая частая ошибка — забыть о повторяющихся элементах при подсчёте перестановок, что приводит к завышенному результату в n₁!·n₂!·…· раз.

Краткий словарь терминов

Перестановка — упорядоченное расположение всех n элементов; Pₙ=n!.

Размещение — упорядоченный выбор k элементов из n; Aₙᵏ=n!/(n−k)!.

Сочетание — неупорядоченный выбор k элементов из n; Cₙᵏ=n!/(k!(n−k)!).

Формула Паскаля — Cₙᵏ⁻¹+Cₙᵏ=Cₙ₊₁ᵏ, лежащая в основе треугольника Паскаля.

Заключение

Перестановки, размещения и сочетания — три базовые комбинаторные конструкции, различающиеся тем, выбираются ли все объекты или их часть, и важен ли порядок выбора. Правильное распознавание типа задачи — ключ к выбору верной формулы, а свойства сочетаний (симметричность, формула Паскаля) находят применение далеко за пределами самой комбинаторики, в частности в биноме Ньютона и в теории вероятностей.