"Алгебра", Никольский С.М., Потапов М.К., Решетников Н.Н. и др.
Сочетание из n элементов по k — это выбор k элементов, в котором порядок не имеет значения. Например, наборы {а, б} и {б, а} считаются одним сочетанием. Число сочетаний обозначают Cₙᵏ и вычисляют по формуле Cₙᵏ = n!/(k!(n−k)!). Сочетания нужны, когда требуется подсчитать варианты выбора команды, набора предметов или группы объектов без их расстановки по местам.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сочетание из n элементов по k — это выбор k элементов из n данных элементов, при котором порядок выбранных элементов не учитывается. Например, выбор учеников Ани и Бори совпадает с выбором Бори и Ани. Такое определение подходит для задач, где важен состав группы, а не порядок её участников.
Число сочетаний — количество всех сочетаний из n элементов по k. Если из десяти учеников выбирают команду из трёх человек, число сочетаний показывает, сколько разных составов команды возможно. Это позволяет заменить перебор вариантов точным вычислением.
Число сочетаний обозначают Cnk. Нижний индекс n показывает, из скольких элементов выбирают, а верхний индекс k — сколько элементов берут. Поэтому запись C103 означает число способов выбрать три элемента из десяти.
Для вычисления применяют формулу Cnk = n!/(k!(n−k)!), где факториал числа n! — произведение всех натуральных чисел от 1 до n, а 0! = 1. Формула действует при условии 0 ≤ k ≤ n. Она даёт число выборок без повторений и без учёта порядка.
Порядок не создаёт нового сочетания, потому что выбранные элементы образуют одну и ту же группу. Например, {а, б, в} и {в, а, б} имеют одинаковый состав. В размещениях эти записи различались бы, так как там учитывается, какой элемент стоит на первом, втором и следующих местах.
Чтобы вывести формулу, сначала представим, что порядок учитывается. Первый элемент можно выбрать n способами, второй — n−1 способом и так далее, поэтому упорядоченных выборок из k элементов получается n!/(n−k)!. Но каждый один и тот же набор посчитан k! раз — по одному разу для каждого порядка его элементов.
Именно поэтому упорядоченное число делят на k!: получаем Cnk = n!/(k!(n−k)!). В записи n! остаются множители, связанные с выбранными и невыбранными элементами. Множитель k! устраняет перестановки выбранных элементов, а (n−k)! сокращает часть произведения, которая относится к оставшимся элементам.
Параметры должны удовлетворять условию 0 ≤ k ≤ n. Нельзя выбрать отрицательное число элементов или взять элементов больше, чем есть всего; кроме того, выбор нуля элементов единственный. Поэтому перед вычислением нужно определить, что означает каждый индекс, и проверить неравенства.
Равенство Cnk = Cnn−k объясняется дополнением: каждому набору из k выбранных элементов соответствует набор из n−k элементов, которые не выбраны. Рекуррентное свойство Cnk = Cn−1k−1 + Cn−1k получают так: фиксированный элемент либо входит в набор, либо не входит. В первом случае выбирают ещё k−1 элементов, во втором — все k из оставшихся n−1.
Таблица помогает быстро выбрать нужное свойство. Сначала определите, требуется ли прямой расчёт, упрощение выражения или построение последовательности чисел. Затем проверьте ограничения на n и k.
| Свойство | Запись | Смысл | Когда применять |
|---|---|---|---|
| Определение | Cnk | Количество выборок из k элементов, составленных из n элементов без учёта порядка | При распознавании типа комбинаторной задачи |
| Формула вычисления | Cnk = n!/(k!(n−k)!) | Переход от заданных n и k к числовому ответу | При прямом вычислении |
| Крайние значения | Cn0 = Cnn = 1 | Пустой выбор и выбор всех элементов дают по одному варианту | В задачах с нулевым или полным выбором |
| Симметрия | Cnk = Cnn−k | Выбрать k элементов равносильно выбрать n−k элементов, которые не входят в набор | Для упрощения вычислений |
| Рекуррентное свойство | Cnk = Cn−1k−1 + Cn−1k | Наборы разделяются на содержащие и не содержащие фиксированный элемент | При построении таблицы или последовательном вычислении |
Например, при большом верхнем индексе сначала замените его на n−k, если это число меньше. Рекуррентное свойство удобно, когда соседние значения уже известны или нужно построить строку треугольника Паскаля.
Сколькими способами можно выбрать 3 учеников из класса, в котором 10 учеников? Порядок учеников в команде не задан, поэтому перестановки одного состава не создают новых вариантов. Значит, задача сводится к нахождению C103.
Ответ: 120 способов. Если бы требовалось распределить учеников по разным должностям, порядок или роль каждого участника имели бы значение, и это была бы уже другая комбинаторная модель.
Нужно вычислить число сочетаний из 12 элементов по 8. Прямое применение формулы содержит факториалы 8! и 4!, но симметрия позволяет заменить восемь выбранных элементов четырьмя невыбранными. Это уменьшает число множителей и снижает риск ошибки.
Ответ: C128 = 495. Такой приём особенно полезен, когда k близко к n: вместо выбора большого числа элементов рассматривают небольшое дополнение.
Из 7 различных книг выбирают 3 для выставки, а затем одну из выбранных назначают главной. Сначала определяется набор книг, поэтому применяется сочетание. После этого для каждого набора есть 3 варианта выбора главной книги, и этапы соединяются правилом произведения.
Ответ: 105 вариантов. Нельзя просто использовать C74 или считать все книги упорядоченными: главная книга выделяется отдельно только после выбора общего набора.
Первая ошибка — считать {a, b} и {b, a} разными наборами. Её допускают, когда механически перечисляют варианты и не спрашивают, важен ли порядок; проверка проста: сравните только состав групп.
Вторая ошибка — подменять сочетания размещениями или перестановками. Это происходит, если не разделить выбор элементов и их расстановку по местам. Проверьте условие: слова «команда», «группа», «набор» обычно указывают на сочетания, а должности и места требуют учёта порядка.
Третья ошибка — перепутать индексы и записать Ckn, когда k больше n. Перед формулой подпишите: n — всего элементов, k — выбранных; затем убедитесь, что 0 ≤ k ≤ n.
Четвёртая ошибка — неверно раскрыть факториалы, забыв скобки в (n−k)! или приняв 0! за 0. Сначала вычисляйте разность n−k, помните, что 0! = 1, и после сокращения оцените, получилось ли целое неотрицательное число.
Для сочетаний нужны факториалы, правило произведения и различие между перестановками, размещениями и сочетаниями. Эти знания помогают определить модель задачи до начала вычислений. Особенно важно отличать выбор группы от расстановки выбранных объектов.
Сочетания применяются в задачах на вероятность: число благоприятных исходов и число всех исходов часто считают именно так. Они также связаны с биномиальными коэффициентами и разложением бинома Ньютона, где Cnk являются коэффициентами.
Рекуррентное свойство образует треугольник Паскаля. В нём каждое внутреннее число равно сумме двух чисел над ним, поэтому нужные значения можно находить без многократного раскрытия факториалов.
Чем сочетания отличаются от размещений?
В сочетаниях порядок выбранных элементов не учитывается: наборы {а, б} и {б, а} одинаковы. В размещениях порядок важен, поэтому эти варианты считаются разными.
Почему порядок выбранных элементов не учитывается?
Сочетание описывает только состав выбранной группы, а не места элементов в ней. Если меняется лишь порядок записи тех же элементов, новая группа не появляется.
Что означают верхний и нижний индексы в записи C_n^k?
Нижний индекс n показывает, из скольких элементов выбирают. Верхний индекс k показывает, сколько элементов должно войти в каждый набор.
Почему C_n^k равно C_n^(n−k)?
Выбрать k элементов означает одновременно оставить вне набора n−k элементов. Каждому набору из k элементов соответствует единственное дополнение из n−k элементов, поэтому количества равны.
Как быстрее вычислить большое число сочетаний?
Сначала проверьте симметрию: C_n^k = C_n^(n−k), и используйте меньший из k и n−k. Также числа сочетаний можно находить по рекуррентной формуле или треугольнику Паскаля.
13.5. Сочетания
