§ 3. Размещения и сочетания

Определения и обозначения

Факториал натурального числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · … · n. Например, 4! = 24, а по соглашению 0! = 1. Факториал кратко записывает произведения, которые возникают при подсчёте вариантов.

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

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

Число размещений обозначают Aₙᵏ, а число сочетаний — Cₙᵏ; в обоих случаях 0 ≤ k ≤ n. Здесь n — общее число доступных элементов, k — сколько из них выбирают. Условия нужны, чтобы нельзя было выбрать отрицательное число элементов или больше, чем имеется.

Как это устроено

В размещениях порядок учитывается потому, что элементы получают разные места в последовательности. На первое место можно поставить любой из n элементов, на второе — любой из оставшихся n − 1, на третье — один из n − 2. Поэтому число вариантов на каждом шаге уменьшается: уже выбранный элемент повторно использовать нельзя.

Чтобы получить формулу размещений, перемножаем число вариантов на каждом из k шагов: Aₙᵏ = n(n − 1)(n − 2) · … · (n − k + 1). В n! входят все множители от n до 1, а в (n − k)! — те, которые не понадобились при выборе. Если сократить n! на (n − k)!, останется ровно произведение первых k множителей: Aₙᵏ = n!/(n − k)!.

Одна группа из k выбранных элементов соответствует не одному размещению, а нескольким: её элементы можно перечислить в разном порядке. На первое место в такой последовательности можно поставить любой из k элементов, на второе — один из k − 1 оставшихся, и так далее. Получается k! порядков, и все они относятся к одному сочетанию.

Поэтому, чтобы перейти от числа размещений к числу сочетаний, делим Aₙᵏ на k!: Cₙᵏ = Aₙᵏ/k!. Подставляем формулу размещений и получаем Cₙᵏ = n!/(k!(n − k)!). Деление убирает повторный подсчёт одной группы в нескольких порядках.

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

Размещения и сочетания без повторений

Сначала найди в условии общее число объектов n и число выбираемых элементов k. Затем проверь, имеет ли значение порядок: это и определяет нужный столбец и формулу.

Связь между числами полезна для проверки вычислений: число размещений должно быть в k! раз больше числа сочетаний. При k = n формулы тоже дают понятный результат — перестановки всех объектов или единственную группу из всех объектов.

Разбор задач

Задача 1. Из 8 учеников нужно выбрать старосту, заместителя и ответственного за мероприятие. Сколькими способами это можно сделать? Роли разные, поэтому назначение учеников на должности имеет значение: староста и заместитель не взаимозаменяемы. Ищем размещения A₈³.

1. Для старосты есть 8 вариантов.
2. После этого для заместителя остаётся 7 учеников, а для ответственного — 6.
3. Перемножаем варианты: A₈³ = 8 · 7 · 6 = 336.

Ответ: 336 способов.

Задача 2. Из 10 книг нужно выбрать 4 книги для выставки. Сколькими способами можно сделать выбор? Здесь не распределяют книги по местам и не задают им разные роли, поэтому перестановка выбранных книг ничего не меняет. Вычисляем число сочетаний C₁₀⁴.

1. Подставляем n = 10 и k = 4 в формулу: C₁₀⁴ = 10!/(4! · 6!).
2. Сокращаем 10! на 6!: C₁₀⁴ = (10 · 9 · 8 · 7)/(4 · 3 · 2 · 1).
3. Вычисляем: 5040/24 = 210.

Ответ: 210 способов.

Задача 3. Из 7 спортсменов нужно выбрать капитана и ещё двух участников команды. Сколькими способами можно сформировать команду с капитаном? Капитан отличается от остальных участников, значит его кандидатура важна, а порядок выбора двух обычных участников — нет. Можно сначала выбрать капитана, а затем группу из двух оставшихся.

1. Капитана можно выбрать 7 способами.
2. После этого двух участников выбираем из 6 спортсменов: C₆² = 6!/(2! · 4!) = 15.
3. Перемножаем независимые этапы: 7 · 15 = 105.
4. Проверка другим способом: A₇³ считает роли капитана и двух участников в установленном порядке, но два последних места можно менять; поэтому A₇³/2! = 210/2 = 105.

Ответ: 105 способов.

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

Ошибка: применять сочетания, если выбранным объектам назначают разные роли. Так делают, когда замечают только число выбранных людей, но забывают, что староста и заместитель — разные должности. Проверь, изменится ли результат при обмене людей ролями: если да, считай размещения.

Обратная ошибка — использовать размещения для выбора группы, хотя её состав не зависит от порядка перечисления. Она возникает, когда при подсчёте вариантов каждый новый порядок группы принимают за другой результат. Для самопроверки переставь выбранные элементы: если ничего не изменилось, результат посчитан несколько раз и нужны сочетания.

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

Ещё одна ошибка — неверно вычислить факториал или считать, что 0! = 0. Факториал включает произведение всех чисел до n, а 0! по соглашению равен 1, чтобы формулы работали и при выборе нуля элементов. Проверь малые значения отдельно: 3! = 6, 1! = 1, 0! = 1.

Связь с другими темами

Для размещений и сочетаний нужны правило произведения, перестановки и умение вычислять факториалы. Правило произведения помогает посчитать варианты последовательного выбора, а понятие перестановки объясняет, почему при k = n размещения дают n! способов. Позже эти формулы пригодятся в задачах на вероятность и комбинаторный подсчёт, когда нужно определить общее число исходов или число подходящих вариантов. Числа сочетаний также называют биномиальными коэффициентами: они участвуют в разложении бинома Ньютона.

Что запомнить

• Размещение — выбор с учётом порядка.
• Сочетание — выбор без учёта порядка.
• Aₙᵏ = n!/(n − k)!.
• Cₙᵏ = n!/(k!(n − k)!).
• Aₙᵏ = k!Cₙᵏ.
• Перед выбором формулы нужно выяснить, меняется ли результат при перестановке выбранных элементов.