§ 48. Выбор нескольких элементов. Биномиальные коэффициенты

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

Сочетанием называют выбор k элементов из n имеющихся, если порядок выбранных элементов не учитывается. Например, выбор книг A и B — тот же выбор, что и B и A. Сочетания нужны в задачах, где важен состав группы, но не последовательность действий.

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

Биномиальный коэффициент — это число сочетаний Cₙᵏ. Его вычисляют по формуле Cₙᵏ = n!/(k!(n−k)!), где 0 ≤ k ≤ n. Факториал n!, то есть произведение всех натуральных чисел от 1 до n, позволяет коротко записать нужные произведения.

Треугольник Паскаля — это расположенная в виде треугольника таблица биномиальных коэффициентов. Каждая строка содержит коэффициенты с одним и тем же n, начиная с Cₙ⁰ и заканчивая Cₙⁿ. По этой таблице можно находить коэффициенты, не вычисляя каждый раз факториалы.

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

Чтобы понять формулу сочетаний, сначала представим, что порядок выбора важен. Тогда число вариантов выбрать и упорядочить k элементов из n равно n(n−1)…(n−k+1), или n!/(n−k)!. Но для одной и той же группы из k элементов существует k! порядков, и каждый из них описывает одно сочетание. Поэтому число упорядоченных выборок делят на k!, получая Cₙᵏ = n!/(k!(n−k)!).

В формуле n! содержит произведение от 1 до n, а (n−k)! — произведение от 1 до n−k. При сокращении этих общих множителей в дроби остаются только n(n−1)…(n−k+1), то есть число вариантов упорядоченного выбора. Затем деление на k! устраняет все перестановки внутри выбранной группы. Так факториалы не просто сокращают запись, а отражают подсчёт вариантов и повторов.

Справедливо равенство Cₙᵏ = Cₙⁿ⁻ᵏ. Если из n элементов выбрали k, то остальные n−k элементов образуют дополнение к выбранной группе. И наоборот, если указать, какие n−k элементов не брать, оставшиеся k будут выбраны однозначно. Поэтому подсчёт выбранных элементов и подсчёт оставшихся дают одинаковое число вариантов.

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

Рекуррентное равенство задаёт построение треугольника Паскаля. В строке с номером n крайние коэффициенты равны единице: есть один способ выбрать ноль элементов и один способ выбрать все n элементов. Любое число внутри строки получают сложением двух соседних чисел над ним, что соответствует двум случаям — элемент выбрали или не выбрали. Например, строка для n = 4 имеет вид 1, 4, 6, 4, 1.

Основные свойства числа сочетаний

Сначала проверьте, что задача действительно о выборе без учёта порядка, и определите n и k. Для небольших n удобно найти коэффициент в треугольнике Паскаля, а для остальных случаев — использовать формулу. Симметрия помогает заменить k на меньшее число n−k и упростить вычисления.

Разбор задач

Сколькими способами можно выбрать 2 книги из 5, если порядок выбора не важен? Поскольку два выбранных тома образуют одну и ту же пару независимо от последовательности выбора, это сочетание. Здесь n = 5, а k = 2.

1. Записываем число вариантов как C₅². Это означает, что из пяти книг выбирают две, не различая порядок.

2. Подставляем числа в формулу: C₅² = 5!/(2!·3!). Сокращаем 5! = 5·4·3!, поэтому получаем (5·4)/(2·1) = 10.

Ответ: выбрать две книги можно 10 способами. Если бы порядок учитывался, каждая пара была бы посчитана дважды, поэтому деление на 2! здесь необходимо.

В группе из 8 учеников нужно выбрать 3 участников команды. Состав команды не меняется, если перечислить тех же учеников в другом порядке, значит, нужно найти сочетание. Здесь n = 8 и k = 3.

1. Записываем C₈³ = 8!/(3!·5!). Сокращаем 8! = 8·7·6·5!, чтобы убрать общий множитель 5!.

2. Вычисляем оставшуюся дробь: (8·7·6)/(3·2·1) = 336/6 = 56. Знаменатель 3! убирает повторы, возникающие из-за разных порядков одних и тех же участников.

Ответ: команду можно составить 56 способами. Число получается целым, как и должно быть для количества возможных групп.

Вычислим C₈⁵, используя свойства биномиальных коэффициентов, а затем сверим результат с треугольником Паскаля. По симметрии C₈⁵ = C₈³, потому что выбрать пять элементов из восьми равносильно тому, чтобы определить три элемента, которые останутся. Сокращение индекса упрощает вычисление.

1. Используем уже понятную форму формулы: C₈³ = 8!/(3!·5!) = (8·7·6)/(3·2·1) = 56. Следовательно, C₈⁵ тоже равно 56.

2. Проверяем результат по треугольнику Паскаля. В строке n = 8 коэффициенты идут от C₈⁰ до C₈⁸, а пятый выбор соответствует C₈⁵; симметричные коэффициенты C₈³ и C₈⁵ равны 56.

Ответ: C₈⁵ = 56. Проверка подтверждает, что симметрия и вычисление по формуле дают одинаковый результат.

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

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

Вторая ошибка — перепутать n и k или записать Cₖⁿ. В Cₙᵏ нижний индекс обозначает общее число элементов, а верхний — сколько выбирают; при этом k не может быть больше n. Перед вычислением выпишите оба числа словами и проверьте, что число выбираемых элементов не превышает общее.

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

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

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

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

Биномиальные коэффициенты встречаются в формуле бинома Ньютона: они показывают, с какими коэффициентами раскрывается степень суммы. Сочетания также нужны в задачах на вероятность, когда требуется посчитать число равновозможных групп или исходов. Поэтому понимание того, что именно считается, помогает выбрать верную формулу в разных разделах математики.

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

• Сочетание — выбор нескольких элементов, в котором порядок не учитывается.
• Число сочетаний обозначают Cₙᵏ.
• Cₙᵏ = n!/(k!(n−k)!), где 0 ≤ k ≤ n.
• Cₙᵏ = Cₙⁿ⁻ᵏ.
• Cₙ⁰ = Cₙⁿ = 1.
• Каждый внутренний элемент треугольника Паскаля равен сумме двух элементов над ним.