"Алгебра (углублённый уровень)", Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И. и др./Под ред.Теляковского С.А.
Сочетания помогают считать, сколькими способами можно выбрать группу из нескольких предметов или людей, если порядок выбора не важен. Например, команда из трёх учеников остаётся той же, кто бы ни был назван первым. Число таких выборов обозначают Cₙᵏ и вычисляют по формуле через факториалы. Главное — отличать выбор группы от упорядоченного выбора, правильно находить n и k и пользоваться свойством Cₙᵏ = Cₙⁿ⁻ᵏ.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторная задача — задача о подсчёте числа способов выбрать или расположить элементы. Например, можно считать, сколько команд получится из учеников класса или сколько существует вариантов расставить книги. Понятие помогает определить, какое правило подсчёта подходит к условию задачи.
Сочетание — выбор нескольких элементов из данного множества, при котором порядок выбранных элементов не учитывается. Так, группа из Ани, Веры и Гали не меняется, если перечислить девочек в другом порядке. Это определение позволяет отделить выбор состава группы от выбора порядка.
Число сочетаний из n элементов по k — количество способов выбрать k элементов из n; его обозначают Cₙᵏ, или биномиальным коэффициентом. Здесь n показывает размер исходного множества, а k — сколько элементов нужно выбрать. Обозначение кратко записывает ответ на задачу о выборе группы.
Факториал натурального числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · ... · n. Например, 4! = 4 · 3 · 2 · 1 = 24. Дополнительно принимают 0! = 1, чтобы формулы сочетаний были верны и для выбора пустой группы.
При подсчёте вариантов сначала выясняют, имеет ли значение порядок. Если из трёх учеников выбирают команду для участия в олимпиаде, перестановка имён в списке не создаёт новую команду. Если же выбирают капитана и помощника, назначения различаются, потому что у участников разные роли. Поэтому в первом случае считают сочетания, а во втором — упорядоченные выборы.
Число сочетаний можно связать с числом размещений — способов выбрать элементы и расположить их в определённом порядке. Представим, что сначала выбрали k элементов и записали их в ряд. Одну и ту же группу можно записать k! способами, потому что на первое место приходится k вариантов, на второе — k − 1 и так далее. Значит, каждое сочетание посчитано среди размещений k! раз, и для подсчёта групп нужно разделить число размещений на k!.
Число размещений из n элементов по k равно n!/(n-k)!, поскольку для последовательных мест доступно n, затем n − 1 и далее n − k + 1 вариантов. Разделив это число на k!, получаем формулу сочетаний: Cₙᵏ = n!/(k!(n-k)!). В знаменателе один множитель устраняет повторы из-за порядка внутри выбранной группы, другой возникает при записи числа размещений через факториалы. Формула позволяет сразу находить число групп, не перечисляя их.
При выборе одного элемента из n вариантов результатом может быть любой из n элементов, поэтому Cₙ¹ = n. Если выбирают все элементы, существует только одна группа — исходное множество, значит, Cₙⁿ = 1. Выбор нуля элементов тоже даёт единственный вариант: ничего не взять. Соглашение 0! = 1 согласуется с этим случаем и делает формулу пригодной при k = 0.
Для каждой выбранной группы из k элементов существует ровно одно дополнение: все элементы исходного множества, которые в группу не вошли. В дополнении будет n-k элементов, поэтому подсчёт групп размера k равносилен подсчёту дополнений размера n-k. Отсюда следует равенство Cₙᵏ = Cₙⁿ⁻ᵏ. Оно помогает упростить вычисления: например, вместо C₉⁷ удобнее находить C₉².
| Случай или свойство | Запись | Пояснение |
|---|---|---|
| Выбор k элементов из n без учёта порядка | Сочетание | Состав группы важен, порядок элементов — нет. |
| Число сочетаний | Cₙᵏ | Количество способов выбрать k элементов из n. |
| Формула через факториалы | Cₙᵏ = n!/(k!(n-k)!) | Применяется при 0 ≤ k ≤ n. |
| Выбор ни одного элемента | Cₙ⁰ = 1 | Есть один способ ничего не выбрать. |
| Выбор одного или всех элементов | Cₙ¹ = Cₙⁿ = 1 | При выборе одного элемента число вариантов равно n; при выборе всех — 1. |
| Связь выбора группы с выбором дополнения | Cₙᵏ = Cₙⁿ⁻ᵏ | Каждой группе соответствуют её n-k элементов дополнения. |
Сначала определите общее число элементов n и размер группы k, а затем проверьте, что 0 ≤ k ≤ n. Если k близко к n, замените его на n-k: значение сочетания не изменится, а вычисления могут стать короче. Для частных случаев используйте готовые значения из таблицы.
Из 8 учеников нужно выбрать троих для участия в олимпиаде. Сколькими способами это можно сделать? Учеников выбирают в одну группу, поэтому очередность выбора не создаёт новую команду. Значит, нужно найти число сочетаний из 8 элементов по 3.
Ответ: 56 способов. Деление на 3! убирает повторный подсчёт одной и той же тройки в разном порядке. Например, последовательности Аня—Боря—Вася и Вася—Аня—Боря обозначают одну команду.
Вычислите C₉⁷, не вычисляя отдельно 9! и 7!. Прямое применение формулы потребовало бы работы с большими факториалами. Свойство сочетаний позволяет заменить выбор семи элементов выбором дополнения из двух элементов.
Ответ: 36. Вместо выбора семи элементов мы посчитали, сколькими способами можно определить два элемента, которые не войдут в выбранную группу. Такой переход уменьшил объём вычислений.
В классе 12 учеников выбирают команду из 4 человек. Нужно найти число команд, в которых есть хотя бы одна из двух заранее указанных учениц. Условие «хотя бы одна» включает команды с первой ученицей, со второй и с обеими. Удобнее посчитать все команды и исключить те, где нет ни одной из двух.
Ответ: 285 команд. Вычитание учитывает сразу все случаи, в которых не выбрана ни одна из двух учениц. Поэтому не нужно отдельно складывать команды с первой, со второй и с обеими и опасаться повторного подсчёта команд, где присутствуют обе.
Первая ошибка — считать разные перестановки одной группы разными сочетаниями. Её допускают, когда порядок перечисления принимают за реальное различие; чтобы проверить себя, спросите, изменится ли состав группы после перестановки. Если нет, порядок учитывать не нужно.
Вторая ошибка — путать сочетания с размещениями и не делить число упорядоченных выборов на k!. Размещения различают порядок, а сочетания — нет, поэтому каждую группу при подсчёте размещений посчитали лишние k! раз. Проверьте смысл задачи и выясните, не посчитана ли одна группа несколько раз в разном порядке.
Третья ошибка — неверно подставить параметры в формулу, например поставить (n-k)! вместо k! или перепутать n и k. Такое случается, если числа из условия не связать с их ролями. Перед вычислением подпишите: n — сколько элементов всего, k — сколько выбирают, а затем проверьте знаменатель k!(n-k)!.
Четвёртая ошибка — считать, что Cₙᵏ и Cₙⁿ⁻ᵏ обычно различны. Эти числа равны, потому что одному выбору группы соответствует выбор всех элементов, оставшихся за её пределами. Для проверки выпишите, что именно выбирается в каждом случае: группу или дополнение к ней.
До решения задач на сочетания полезно знать правило умножения: оно помогает считать число последовательных шагов выбора. Также нужны понятие размещения и умение вычислять факториалы, поскольку формула сочетаний выводится через упорядоченные выборы и записывается с факториалами. Сочетания применяются в задачах на формирование групп и команд. Позже они встречаются при изучении биномиальных коэффициентов и формулы бинома Ньютона.
Чем сочетание отличается от размещения?
В сочетании важен только состав выбранной группы, а порядок элементов не учитывается. В размещении порядок важен: например, выбор капитана и заместителя отличается от выбора тех же двух человек без распределения ролей.
Почему в формуле числа сочетаний нужно делить на k!?
Каждую выбранную группу из k элементов можно переставить k! способами. Все эти перестановки дают ту же группу, поэтому число упорядоченных выборов нужно разделить на k!.
Как вычислить число сочетаний из n элементов по k?
Используй формулу Cₙᵏ = n!/(k!(n-k)!), где n — общее число элементов, а k — размер группы. Подставь значения и сократи факториалы, прежде чем перемножать числа.
Почему Cₙᵏ равно Cₙⁿ⁻ᵏ?
Выбрать k элементов — то же самое, что указать, какие n-k элементов не выбраны. Каждой группе соответствует единственное дополнение, поэтому количество вариантов совпадает.
Как учитывать условие «хотя бы один» при подсчёте сочетаний?
Часто проще посчитать все группы, а затем вычесть группы, в которых не выбран ни один из нужных элементов. Например, для условия «хотя бы одна из двух учениц» из числа всех команд вычитают команды без обеих учениц.
Сочетания
