§ 37. Сочетания

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

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

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

Формула числа сочетаний: C_n^k = n! / (k!(n − k)!), где 0 ≤ k ≤ n. Знак ! означает факториал: например, 4! = 4 · 3 · 2 · 1. Формула позволяет получить число вариантов, не перечисляя группы по одной, а ограничение напоминает, что нельзя выбрать отрицательное число элементов или больше, чем есть.

Свойство симметрии сочетаний: C_n^k = C_n^n−k. Выбрать k элементов — значит одновременно определить, какие n − k элементов не войдут в группу. Это свойство полезно, если выбрать оставшихся проще, чем перечислять саму группу.

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

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

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

В формуле факториалы собирают произведения последовательных чисел: n! отвечает за общее число вариантов, а (n − k)! сокращает те множители, которые не участвуют в выборе. Множитель k! убирает повторный подсчёт из-за разных порядков одной группы. Условие 0 ≤ k ≤ n необходимо по смыслу: количество выбираемых элементов не может быть меньше нуля или превышать размер набора.

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

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

Как распознать и вычислить число сочетаний

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

Разбор задач

Задача 1. Из 5 учеников нужно выбрать двух дежурных. Сколькими способами это можно сделать? В результате важен только состав пары: назначение «А и Б» не отличается от «Б и А». Значит, нужно найти число сочетаний из пяти элементов по два.

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

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

Задача 2. В классе 10 учеников нужно выбрать команду из 4 человек. Сколько разных команд можно составить? Команда определяется тем, кто в неё входит, поэтому порядок перечисления учеников значения не имеет. Повторно выбрать одного и того же ученика нельзя, следовательно, применяем сочетания.

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

Ответ: можно составить 210 разных команд. Сокращение до вычисления удобнее, чем отдельно находить большие значения 10! и 6!.

Задача 3. Из 12 участников выбирают 9 человек для поездки. Сколькими способами можно сформировать группу? Можно считать сочетание C₁₂⁹, но считать девять выбранных человек длиннее, чем троих оставшихся. По свойству симметрии эти способы выбора равны.

1. Всего участников n = 12, в поездку едут 9, а не едут 12 − 9 = 3.
2. Заменим C₁₂⁹ равным ему сочетанием C₁₂³.
3. Вычислим: C₁₂³ = 12! / (3! · 9!) = (12 · 11 · 10) / (3 · 2 · 1) = 220.

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

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

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

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

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

Четвёртая ошибка — подставить k > n или отрицательное k. Обычно числа берут из условия, не проверяя, может ли такое количество объектов существовать. Перед вычислением сравни k и n: число выбранных элементов должно удовлетворять 0 ≤ k ≤ n. Если условие нарушено, нужно проверить, верно ли определены общее число объектов и размер группы.

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

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

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

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

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

• Сочетание — выбор без учёта порядка.
• Число сочетаний обозначают C_n^k.
• C_n^k = n! / (k!(n − k)!).
• В формуле сочетаний 0 ≤ k ≤ n.
• C_n^k = C_n^n−k.
• Перед вычислением выясни, важен ли порядок выбора.