5. Сочетания и биномиальные коэффициенты

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

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

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

Число сочетаний вычисляют по формуле Cₙᵏ = n!/(k!(n − k)!), где знак ! обозначает факториал: например, 4! = 4 · 3 · 2 · 1. Формула применима при целых k от 0 до n включительно. Эти границы означают, что можно выбрать ни одного элемента или все элементы, но нельзя выбрать отрицательное число элементов или больше, чем есть в множестве.

Биномиальный коэффициент Cₙᵏ — это число сочетаний из n элементов по k, то есть количество возможных групп такого размера. Поэтому он всегда целый и неотрицательный: речь идёт о подсчёте объектов, а количество групп не может быть дробным или отрицательным. Для k = 0 и k = n существует ровно один выбор, поэтому Cₙ⁰ = Cₙⁿ = 1.

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

Чтобы понять, считать ли сочетания или размещения, спросите себя: меняется ли результат, если переставить выбранные элементы? Если выбирают двух дежурных, пара «Маша и Илья» не отличается от пары «Илья и Маша», поэтому это сочетание. Если же назначают первого и второго дежурного, роли различаются, и порядок уже важен: тогда считают размещения.

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

Симметрия Cₙᵏ = Cₙⁿ⁻ᵏ возникает потому, что группу можно описать двумя равноправными способами: перечислить k выбранных элементов или n − k оставшихся. Например, если из 10 человек выбрали троих, это равносильно указанию семи, которые не вошли в группу. Между такими описаниями есть взаимно однозначное соответствие, поэтому число вариантов одинаково.

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

При раскрытии (a + b)ⁿ каждый множитель содержит выбор одного из двух слагаемых a или b. Чтобы получить член aⁿ⁻ᵏbᵏ, нужно выбрать b ровно в k из n множителей, а число таких выборов равно Cₙᵏ. Поэтому разложение имеет вид суммы членов Cₙᵏaⁿ⁻ᵏbᵏ. Коэффициенты можно расположить по строкам: крайние равны 1, а каждый внутренний равен сумме двух соседних сверху по соотношению Паскаля — так устроен треугольник Паскаля.

Основные свойства биномиальных коэффициентов

В таблице собраны формулы и коротко указано, что именно они позволяют делать. Сначала проверьте, что выбранные значения удовлетворяют условию 0 ≤ k ≤ n. Для вычислений часто удобнее симметрия или соотношение Паскаля, чем непосредственная подстановка факториалов.

Разбор задач

Задача 1. Из 7 учеников нужно выбрать двух дежурных. Сколькими способами это можно сделать? Сначала выясним, имеет ли значение порядок выбора. Если дежурные выполняют одинаковую роль, то выбор тех же двух учеников в другой очередности не создаёт новую пару. Значит, считаем сочетания.

1. Общее число учеников n = 7, число выбираемых k = 2. Так как порядок не важен, записываем C₇². По формуле получаем C₇² = 7!/(2! · 5!).
2. Сокращаем факториалы: 7!/(2! · 5!) = (7 · 6)/(2 · 1) = 21. Деление на 2! убирает повторный подсчёт каждой пары в двух порядках.

Ответ: 21 способом.

Задача 2. Вычислить C₁₀³ и проверить результат с помощью симметрии. Здесь можно применить формулу напрямую, а затем сравнить ответ с сочетанием, в котором выбирают 10 − 3 элементов. Проверка подтверждает, что подсчёт не зависит от того, описываем ли мы выбранную группу или оставшихся людей.

1. Подставляем n = 10 и k = 3: C₁₀³ = 10!/(3! · 7!). Сокращаем 10! с 7! и вычисляем (10 · 9 · 8)/(3 · 2 · 1) = 120.
2. По симметрии C₁₀³ = C₁₀⁷. Проверим вычислением: C₁₀⁷ = 10!/(7! · 3!), что совпадает с той же формулой и даёт 120.

Ответ: C₁₀³ = 120, и C₁₀⁷ = 120.

Задача 3. Найти натуральное n, если Cₙ² = 45. Поскольку выбирают два элемента, формулу сочетаний можно упростить до Cₙ² = n(n − 1)/2. Решим полученное уравнение и обязательно проверим, что ответ подходит исходному условию.

1. Записываем n(n − 1)/2 = 45 и умножаем обе части на 2. Получаем n² − n − 90 = 0. Разложение на множители: (n − 10)(n + 9) = 0.
2. Корни уравнения — n = 10 и n = −9. Натуральным является только n = 10; при нём k = 2 удовлетворяет условию 0 ≤ k ≤ n. Проверка: C₁₀² = 10 · 9/2 = 45.

Ответ: n = 10.

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

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

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

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

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

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

Для изучения сочетаний нужны правило произведения и факториал: они помогают посчитать упорядоченные выборы и вывести формулу. Поэтому полезно отличать последовательное заполнение мест от формирования группы без порядка. Такое различие определяет, какую комбинаторную формулу следует применять.

Сочетания встречаются в задачах на подсчёт способов и в теории вероятностей, когда нужно определить число равновозможных исходов. В биномиальном разложении они задают коэффициенты при членах (a + b)ⁿ. Соотношение Паскаля связывает вычисление этих коэффициентов с треугольником Паскаля: крайние числа равны единице, остальные получаются сложением соседних.

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

• В сочетании порядок выбранных элементов не учитывается.
• Число сочетаний из n элементов по k равно Cₙᵏ = n!/(k!(n − k)!).
• Для допустимых k выполняется 0 ≤ k ≤ n.
• Cₙᵏ = Cₙⁿ⁻ᵏ.
• Cₙᵏ = Cₙ₋₁ᵏ + Cₙ₋₁ᵏ⁻¹.
• Коэффициент при aⁿ⁻ᵏbᵏ в разложении (a + b)ⁿ равен Cₙᵏ.