4. Сочетания без повторений

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

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

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

Число сочетаний обозначают Cₙᵏ. Нижний индекс n показывает, сколько элементов находится в исходном множестве, а верхний индекс k — сколько элементов выбирают. Например, C₅² означает число способов выбрать два элемента из пяти; порядок и повторный выбор не учитываются.

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

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

Пусть есть три элемента: А, Б и В, и нужно выбрать два. Возможны группы АБ, АВ и БВ; запись БА не создаёт новой группы, потому что в ней выбраны те же А и Б. Значит, выбор А затем Б и выбор Б затем А — разные последовательности действий, но одно сочетание. Это различие объясняет, почему при подсчёте сочетаний нельзя просто считать все порядки как отдельные варианты.

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

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

Размещение отличается от сочетания тем, что в нём порядок выбранных элементов важен. Если сначала посчитать сочетания, то каждому из них можно сопоставить k! размещений: выбранные элементы можно расставить k! способами. Значит, число размещений равно Cₙᵏ · k!, что согласуется с подсчётом упорядоченных выборов. Эта связь позволяет переходить от задачи о группах к задаче о последовательностях.

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

Основные свойства числа сочетаний без повторений

Пользуйтесь формулой, когда нужно найти точное число вариантов, а симметрией — если удобнее считать, кого не выбрали. Рекуррентное соотношение помогает вычислять значения через меньшие сочетания, а связь с размещениями — проверить, учтён ли порядок. При k = 0 или k = n сразу используйте крайние случаи.

Разбор задач

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

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

Ответ: 10 способов. Если бы дежурные занимали разные должности, порядок или роли имели бы значение, и понадобился бы другой подсчёт.

Задача 2. Сколькими способами можно составить команду из 4 человек среди 9 участников? Команда определяется только тем, кто в неё вошёл, поэтому перестановка участников не создаёт новую команду. Нужно вычислить C₉⁴.

1. Подставим n = 9 и k = 4: C₉⁴ = 9! / (4! · 5!).
2. Сократим общую часть факториалов: C₉⁴ = (9 · 8 · 7 · 6) / (4 · 3 · 2 · 1).
3. Выполним вычисление: 3024 / 24 = 126.

Ответ: 126 команд. Для быстрой проверки можно применить симметрию C₉⁴ = C₉⁵ и получить то же число.

Задача 3. Из группы выбрали 3 человека, и число таких выборов равно 56. Сколько человек было в группе, если известно, что их меньше 10? Обозначим размер группы через n и запишем условие как Cₙ³ = 56. Проверим целые n, большие или равные трём, поскольку выбрать троих из меньшего числа нельзя.

1. По формуле Cₙ³ = n(n − 1)(n − 2) / 6.
2. Подставим n = 8: C₈³ = 8 · 7 · 6 / 6 = 56.
3. Проверим соседние допустимые значения: C₇³ = 35, а C₉³ = 84. Число сочетаний растёт с увеличением n, потому что к прежним выборам добавляются новые варианты с дополнительным элементом.

Ответ: в группе было 8 человек. Условие n < 10 исключает дальнейший поиск больших значений, а соседняя проверка подтверждает, что подходит именно n = 8.

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

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

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

Третья ошибка — путать n и k или подставлять в формулу размер выборки вместо размера исходного множества. Из-за этого получается неверная формула даже при правильном вычислении факториалов. Сначала подпишите словами: n — сколько элементов всего, k — сколько выбирают; затем проверьте, что 0 ≤ k ≤ n.

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

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

Для работы с сочетаниями нужны факториал, правило произведения и понимание разницы между упорядоченным и неупорядоченным выбором. Факториал помогает записывать число последовательных выборов, а правило произведения — умножать число вариантов для разных шагов. Различение порядка позволяет решить, следует ли делить полученное число на k!.

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

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

• В сочетании порядок элементов не учитывается.
• Повторно выбирать один и тот же элемент нельзя.
• Cₙᵏ = n! / (k!(n − k)!).
• Cₙᵏ = Cₙⁿ⁻ᵏ.
• Cₙ⁰ = Cₙⁿ = 1.
• Каждому сочетанию из k элементов соответствуют k! размещений.