Число сочетаний в комбинаторике¶

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

¶Определение

Пусть имеется множество из \(n\) различных элементов. Числом сочетаний из \(n\) по \(k\) называют количество подмножеств мощности \(k\), которые можно составить из этих элементов. Обозначается оно \(C_n^k\), \(\binom{n}{k}\) или \(C(n,k)\). Порядок элементов внутри выбранного подмножества не важен: наборы, отличающиеся только расположением элементов, считаются одним и тем же сочетанием.

Формула для вычисления имеет вид:

\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]

где \(n!\) — факториал числа \(n\), то есть произведение всех натуральных чисел от 1 до \(n\). Формула справедлива для целых \(0 \le k \le n\); при \(k > n\) число сочетаний полагают равным нулю.

¶Связь с размещениями и перестановками

Число размещений \(A_n^k\) учитывает порядок и равно \(\frac{n!}{(n-k)!}\). Поскольку каждое сочетание из \(k\) элементов можно упорядочить \(k!\) способами, получается соотношение:

\[ A_n^k = \binom{n}{k} \cdot k! \]

Отсюда и выводится основная формула. Перестановка — частный случай размещения при \(k = n\), а сочетание отличается от обоих именно игнорированием порядка.

¶Основные свойства

• Симметрия: \(\binom{n}{k} = \binom{n}{n-k}\). Выбор \(k\) элементов равносилен выбору \(n-k\) элементов, которые остаются.
• Граничные значения: \(\binom{n}{0} = \binom{n}{n} = 1\).
• Рекуррентное правило Паскаля: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\).
• Сумма по строке: \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\) — общее число всех подмножеств множества из \(n\) элементов.

¶Треугольник Паскаля

Значения \(\binom{n}{k}\) удобно располагать в виде треугольной таблицы — треугольника Паскаля. Каждое число в нём равно сумме двух стоящих над ним чисел, а края строк заполнены единицами. Строка с номером \(n\) содержит последовательность \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\). Таблица применяется для быстрого нахождения коэффициентов бинома и в учебных задачах.

¶Биномиальные коэффициенты

Числа \(\binom{n}{k}\) называют биномиальными коэффициентами, поскольку они входят в формулу бинома Ньютона:

\[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \]

Коэффициент при \(a^{n-k}b^k\) показывает, сколькими способами из \(n\) множителей можно выбрать \(k\), дающих \(b\). Это связывает комбинаторику с алгеброй многочленов.

¶Примеры вычислений

Последний пример соответствует числу возможных комбинаций в лотерее «6 из 49»: именно столько различных шестёрок можно составить из 49 чисел.

¶Применение

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

В статистике сочетания лежат в основе гипергеометрического распределения, описывающего выборку без возврата из конечной совокупности. В информатике и программировании формулы сочетаний применяются в алгоритмах перебора, при оценке сложности и в криптографии. В генетике и биологии сочетания используются при подсчёте вариантов скрещивания и комбинаций признаков.

¶История

Отдельные значения биномиальных коэффициентов встречаются в трудах математиков средневекового Востока и Европы. Треугольник, носящий имя Блеза Паскаля, был известен задолго до него — в частности, в работах китайских и персидских учёных. В XVII веке Паскаль систематически описал свойства этих чисел в «Трактате об арифметическом треугольнике». Современные обозначения \(\binom{n}{k}\) закрепились в XIX–XX веках.

¶Обобщения

Помимо классического случая, рассматривают сочетания с повторениями, когда элементы могут выбираться многократно. Их число равно \(\binom{n+k-1}{k}\). Существуют также обобщения на произвольные множества и мультимножества, применяемые в перечислительной комбинаторике.

¶Обозначения и вычисления на практике

В российских школьных учебниках чаще используется запись \(C_n^k\), в международной литературе — \(\binom{n}{k}\). При больших \(n\) факториалы вычисляют через логарифмы или рекуррентно, чтобы избежать переполнения. Часто применяют последовательное умножение числителя и деления на знаменатель, что даёт точный целочисленный результат.

Источники: учебники по комбинаторике и теории вероятностей, математические энциклопедии, материалы по истории математики.