"Алгебра. (в 2 частях)", Петерсон Л.Г., Агаханов Н.Х., Петрович А.Ю., Подлипский О.К., Рогатова М.В., Трушин Б.В.
Сочетания помогают считать выборы, в которых порядок элементов не важен: например, состав команды или набор задач. Для выбора k элементов из n используют число сочетаний Cₙᵏ. Главная формула выражает его через факториалы: Cₙᵏ = n!/(k!(n − k)!). В параграфе также объясняется симметрия сочетаний, связь с размещениями, крайние случаи и правило, лежащее в основе треугольника Паскаля.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сочетание — это выбор k элементов из n данных элементов, при котором порядок выбранных элементов не учитывается. Например, команда из игроков А, Б и В такая же, как команда из В, А и Б. Это понятие используют, когда важен состав группы, но не порядок её участников.
Число сочетаний — количество всех сочетаний из n элементов по k. Оно отвечает на вопрос, сколько разных наборов можно получить при таком выборе. Если нужно сравнить варианты без перечисления каждого из них, находят именно число сочетаний.
Число сочетаний обозначают Cnk, где n — общее число элементов, а k — число выбираемых элементов. Допустимы значения 0 ≤ k ≤ n. Запись C83 означает количество способов выбрать 3 элемента из 8.
Формула числа сочетаний — это способ вычислить Cnk через факториалы: Cnk = n!/(k!(n − k)!). Факториал n! равен произведению всех натуральных чисел от 1 до n, причём 0! = 1. Число Cnk также называют биномиальным коэффициентом.
Выборы, отличающиеся только порядком элементов, считают одним сочетанием, потому что они описывают один и тот же состав. Например, при выборе двух дежурных пара учеников Ира и Олег не меняется от перестановки имён. Если в условии нет ролей и последовательности действий, повторно считать такие варианты нельзя.
Связь с размещениями возникает потому, что размещение учитывает порядок, а сочетание — нет. В каждом наборе из k разных элементов можно расставить элементы k! способами. Поэтому число размещений из n по k делят на k!: Cnk = Ank/k!.
В формуле размещений Ank = n!/(n − k)!, поэтому после деления на k! получается Cnk = n!/(k!(n − k)!). Множитель n! учитывает выбор и порядок первых элементов, k! убирает лишний учёт их перестановок, а (n − k)! появляется из сокращённой записи произведения. Для вычисления сначала подставляют n и k, затем считают факториалы и выполняют деление.
Число сочетаний из n элементов по k равно числу сочетаний по n − k: Cnk = Cnn − k. Выбрать k элементов — то же самое, что указать остальные n − k элементов, которые не выбраны. Это свойство часто позволяет заменить неудобное большое k на маленькое число и упростить вычисления.
Крайние случаи объясняются смыслом выбора: нулевые элементы можно выбрать единственным пустым способом, как и весь набор. Отсюда Cn0 = Cnn = 1, а Cn1 = n. Если разделить сочетания из n элементов по наличию определённого элемента, получим Cnk = Cn−1k−1 + Cn−1k; именно это правило вместе с единицами по краям образует треугольник Паскаля.
| Свойство или случай | Формула или запись | Смысл |
|---|---|---|
| Общее вычисление | Cnk = n!/(k!(n − k)!) | Число сочетаний из n элементов по k |
| Выбор нуля элементов | Cn0 = 1 | Единственный пустой выбор |
| Выбор всех элементов | Cnn = 1 | Весь набор выбирается единственным способом |
| Выбор одного элемента | Cn1 = n | Каждый из n элементов даёт отдельное сочетание |
| Симметрия сочетаний | Cnk = Cnn − k | Выбор k элементов равносилен выбору n − k элементов, которые не выбраны |
| Рекуррентное свойство | Cnk = Cn−1k−1 + Cn−1k | Сочетания разбиваются по наличию или отсутствию выбранного элемента |
Таблицу удобно использовать как памятку перед вычислениями. Сначала проверьте, не подходит ли готовое свойство: например, симметрия может заменить Cn8 на Cn2. Если значение не является крайним, применяйте общую формулу или рекуррентное правило.
Треугольник Паскаля строится так: по краям каждой строки стоят единицы, а внутреннее число равно сумме двух чисел над ним. Эти числа являются сочетаниями, поэтому таблица помогает находить некоторые значения без факториалов.
Условие. Сколькими способами можно выбрать 3 учащихся из 8 для участия в олимпиаде? Важно только, кто войдёт в группу, а распределения мест внутри группы нет. Значит, порядок выбранных учащихся не учитывается.
Ответ: 56 способов.
Условие. В классе 10 учащихся нужно выбрать председателя, заместителя и ещё одного члена совета. Это не обычное сочетание трёх учащихся, потому что должности различаются. Один и тот же состав при другой расстановке должностей даёт новый вариант.
Ответ: 720 способов.
Условие. Найдите n, если Cn2 = 45. Здесь число выбираемых элементов k равно 2, поэтому в формулу подставляем именно этот верхний индекс. После решения нужно проверить, что n не меньше 2.
Ответ: n = 10.
Учитывают порядок выбранных элементов и получают число размещений вместо сочетаний, потому что не проверяют смысл выбора. Так бывает, когда набор участников мысленно превращают в последовательность. Проверьте: если перестановка выбранных объектов не создаёт новый вариант, нужен знак сочетаний.
Забывают делить число упорядоченных выборок на k!, так как не замечают, что один набор можно переставить несколькими способами. В результате ответ оказывается в k! раз больше правильного. Для самопроверки перечислите перестановки маленького набора из двух или трёх элементов.
Неправильно записывают формулу, путая k! и (n − k)! или теряя один из множителей. Такая ошибка меняет значение даже при верных подстановках. Сверяйте формулу с записью n!/(k!(n − k)!) и проверяйте симметрию Cnk = Cnn − k.
Применяют формулу при k > n или получают нецелый ответ, не проверяя допустимость параметров и результат. Нельзя выбрать больше элементов, чем дано, а число сочетаний всегда является целым. Перед вычислением проверьте 0 ≤ k ≤ n, затем оцените смысл полученного числа.
До изучения сочетаний нужны факториал, правило произведения и размещения без повторений. Факториал сокращает записи, правило произведения помогает считать последовательные выборы, а размещения дают основу для вывода формулы сочетаний.
Сочетания применяются в задачах на вероятность, когда нужно подсчитать число равноправных групп или исходов. Они также входят в биномиальную формулу, раскрывающую степени суммы.
Дальше сочетания связываются с биномиальными коэффициентами и треугольником Паскаля. Рекуррентное свойство позволяет строить значения сочетаний по предыдущей строке без непосредственного вычисления факториалов.
Чем сочетания отличаются от размещений?
В сочетаниях порядок выбранных элементов не имеет значения: набор {А, Б, В} один и тот же при любой перестановке. В размещениях порядок важен, поэтому последовательности АБВ и ВБА считаются разными.
Почему в формуле сочетаний нужно делить на k!?
При подсчёте размещений один и тот же набор из k элементов получается k! раз — по числу его перестановок. Деление на k! убирает эти повторы и оставляет каждый набор один раз.
Что означает нижний и верхний индекс в записи C_n^k?
Нижний индекс n показывает, сколько всего элементов дано. Верхний индекс k показывает, сколько элементов выбирают.
Можно ли выбирать k, если k больше n?
Нет, выбрать больше элементов, чем есть в исходном наборе, невозможно. Формула сочетаний применяется при 0 ≤ k ≤ n.
Как быстро проверить, что результат вычисления числа сочетаний верен?
Проверьте, что ответ целый и не меньше единицы, а также сравните его с симметричным значением Cₙⁿ⁻ᵏ. Для небольших k можно пересчитать результат по правилу Паскаля или проверить крайний случай, если он близок к 0, 1 или n.
1.2.3. Сочетания
