1.6. Сочетания

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

Сочетание — это выбор нескольких элементов из данного множества, при котором порядок выбранных элементов не учитывается. Например, выбор Ани и Бориса образует ту же пару, что и выбор Бориса и Ани. Поэтому сочетания подходят для описания групп, команд и наборов, где важен состав, а не последовательность выбора. Перед подсчётом полезно спросить себя: изменится ли результат, если поменять выбранные элементы местами?

Число способов выбрать k элементов из n обозначают Cₙᵏ и читают «число сочетаний из n по k». Здесь n — общее количество элементов, k — размер выбираемой группы; параметры должны удовлетворять условию 0 ≤ k ≤ n. Например, C₅² показывает, сколькими способами можно выбрать пару из пяти объектов. Такое обозначение позволяет кратко записывать ответ, не перечисляя все группы.

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

Числа Cₙᵏ также называют биномиальными коэффициентами: они являются коэффициентами при раскрытии степеней двучлена, например (a + b)ⁿ. Это название не меняет их комбинаторного смысла: каждое такое число равно количеству сочетаний из n элементов по k. Поэтому одна и та же запись связывает подсчёт групп с алгебраическими формулами. Позже эти коэффициенты встретятся также в задачах на вероятность.

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

Чтобы понять, почему сочетаний меньше, чем размещений, сначала посчитаем упорядоченные выборы. Для первого элемента есть n вариантов, для второго — n − 1, и так далее до k-го; получаем Aₙᵏ = n!/(n − k)!. Но один и тот же набор из k элементов можно перечислить в разных порядках, и все k! перестановок дают разные размещения. Значит, размещения учитывают каждый состав группы k! раз, хотя для сочетаний порядок несущественен.

Разделив число размещений на k!, получаем Cₙᵏ = Aₙᵏ/k! = [n!/(n − k)!]/k! = n!/[k!(n − k)!]. Сокращать факториалы полезно ещё до вычисления: так числа остаются небольшими и снижается риск ошибки. Например, в C₈³ можно сократить 8! с 5!, получив 8 · 7 · 6 / (3 · 2 · 1). Деление на k! не случайное действие, а способ убрать повторный подсчёт одной группы в разных порядках.

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

Если k = 0, выбирается пустая группа, и для неё есть ровно один вариант — ничего не брать. Если k = n, можно выбрать только всё множество; поэтому Cₙ⁰ = Cₙⁿ = 1. При k > n выбрать k разных элементов невозможно, так что число таких выборов равно нулю; формулу с факториалом для этого случая напрямую не применяют. Эти случаи помогают проверять ответы и задавать края таблицы сочетаний.

Рассмотрим выбор k элементов из n, выделив один конкретный элемент. Все наборы распадаются на две непересекающиеся группы: те, в которые выделенный элемент входит, и те, в которые он не входит. Во второй группе остальные k элементов выбирают из n − 1, получая Cₙ₋₁ᵏ вариантов; в первой уже выбран один элемент, поэтому ещё k − 1 выбирают из n − 1, получая Cₙ₋₁⁽ᵏ⁻¹⁾ вариантов. Складывая количества двух групп, получаем Cₙᵏ = Cₙ₋₁ᵏ + Cₙ₋₁⁽ᵏ⁻¹⁾.

Числа сочетаний: формула и основные свойства

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

Разбор задач

Задача 1. Из 5 учеников нужно выбрать 2 дежурных. Сколькими способами это можно сделать? Дежурные образуют группу, поэтому назначение первого и второго по очереди не создаёт нового варианта. Значит, нужно вычислить число сочетаний C₅².

1. Определяем параметры: всего n = 5 учеников, выбрать нужно k = 2.
2. Подставляем значения в формулу: C₅² = 5!/(2! · 3!).
3. Сокращаем факториалы: 5!/(2! · 3!) = (5 · 4)/(2 · 1) = 10.

Ответ: выбрать дежурных можно 10 способами. Проверка смысла проста: если тех же двух учеников назвать в обратном порядке, пара не изменится, поэтому перестановки не нужно считать отдельно.

Задача 2. Сколькими способами можно выбрать 3 книги из 8 разных книг? Каждая книга отличается от остальных, но порядок, в котором книги окажутся в наборе, значения не имеет. Поэтому используем сочетания C₈³, а не размещения.

1. Устанавливаем параметры: n = 8, k = 3, значит C₈³ = 8!/(3! · 5!).
2. Сокращаем общую часть факториалов: 8!/5! = 8 · 7 · 6.
3. Вычисляем: (8 · 7 · 6)/(3 · 2 · 1) = 336/6 = 56.

Ответ: выбрать книги можно 56 способами. Сокращение до перемножения всех чисел помогает не работать с большими значениями 8! и 5! отдельно.

Задача 3. В группе 10 человек нужно выбрать команду из 4 человек, но двое конкретных участников не должны попасть в неё одновременно. Сначала посчитаем все команды, а затем исключим запрещённые. Так мы учитываем ограничение, не разбивая допустимые команды на множество случаев.

1. Без ограничений команд C₁₀⁴ = 10!/(4! · 6!) = (10 · 9 · 8 · 7)/(4 · 3 · 2 · 1) = 210.
2. В запрещённой команде уже есть оба конкретных участника. Ещё двух нужно выбрать из остальных восьми, поэтому таких команд C₈² = 8 · 7/(2 · 1) = 28.
3. Вычитаем запрещённые варианты: 210 − 28 = 182.

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

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

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

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

Третья ошибка — неверно записать знаменатель или использовать Cₙᵏ = n!/(n − k)!. Такая формула считает размещения: в ней порядок важен и деления на k! нет. При проверке выпишите отдельно k и n − k: их факториалы должны стоять в знаменателе формулы сочетаний. Также можно сравнить результат с размещениями: число сочетаний не должно быть больше числа упорядоченных выборов.

Четвёртая ошибка — подставить k > n или k < 0, не проверив допустимость параметров. В этих случаях обычный выбор k элементов из n невозможен, а выражение с факториалами может оказаться не определено. Перед вычислениями убедитесь, что n — целое неотрицательное число и 0 ≤ k ≤ n. Если k > n, число возможных выборов равно нулю.

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

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

Биномиальные коэффициенты Cₙᵏ используются при раскрытии бинома Ньютона: они показывают, с какими коэффициентами входят слагаемые в разложение (a + b)ⁿ. В теории вероятностей сочетания помогают считать число равновозможных наборов, например вариантов выбора нескольких объектов. В таких задачах сначала подсчитывают все подходящие исходы, а затем сравнивают их с общим числом исходов.

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

• В сочетании порядок выбранных элементов не учитывается.
• Число сочетаний из n элементов по k обозначают Cₙᵏ.
• Cₙᵏ = n! / (k!(n − k)!).
• Cₙᵏ = Cₙ⁽ⁿ⁻ᵏ⁾.
• Cₙ⁰ = Cₙⁿ = 1.
• Cₙᵏ = Cₙ₋₁ᵏ + Cₙ₋₁⁽ᵏ⁻¹⁾.