Вероятность и статистика · Подсчёт вариантов

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

Симметрия, сумма и рекурсия чисел сочетаний: почему одни и те же числа возникают в разных задачах.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

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

Главная идея. Биномиальный коэффициент C(n, k) считает k-элементные подмножества n различных объектов без учёта порядка. Симметрия возникает потому, что выбрать вошедшие элементы равносильно выбрать оставшиеся.

План рассуждения и проверка понимания

Определите n как размер исходного множества и k как размер выбора; проверьте целые границы 0 ≤ k ≤ n.
Если порядок не важен, вычислите n!/[k!(n − k)!], сокращая общие множители до получения больших факториалов.
При большом k используйте симметрию C(n, k) = C(n, n − k), чтобы считать меньший размер дополнения.
Для суммы по всем k вспомните: каждый элемент либо входит в подмножество, либо нет, поэтому вариантов всего 2ⁿ.

Частая ошибка. Считать C(n, k) вероятностью и ожидать значение между нулём и единицей, хотя коэффициент обозначает количество возможных подмножеств.

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

Схема к теме

Наглядная модель: Биномиальные коэффициенты

Симметрия, сумма и рекурсия чисел сочетаний: почему одни и те же числа возникают в разных задачах.

1. Условия — что известно и что требуется
2. Модель — порядок, повторения и допустимые исходы
3. Подсчёт — каждый вариант учитывается один раз
4. Проверка — малый случай можно выписать вручную

Последовательность отделяет выбор модели от вычисления и не даёт потерять или повторно учесть варианты. Вывод: Сначала ответьте на вопросы о порядке и повторениях, только потом выбирайте формулу.

Проверка пониманияОбъясните тему своими словами

Объясните двумя способами, почему C(12, 10) = C(12, 2) = 66: через дополнение выбранной десятки и через сокращение факториалов.

В хорошем объяснении есть:

Каждой группе из десяти однозначно сопоставлена пара исключённых элементов.
Вычисление сведено к 12 · 11 / 2 без разворачивания полного значения 12!.

Что означает коэффициент

Биномиальный коэффициент $\binom nk$ — число способов выбрать $k$ различных элементов из $n$ , не учитывая порядок. Здесь $n$ — неотрицательное целое, $0\le k\le n$ . Название связано с раскрытием степени суммы двух слагаемых, но комбинаторное определение полезно само по себе.

Для $k=0$ коэффициент равен единице: пустое подмножество только одно. Для $k=n$ он тоже равен единице. Равенство $\binom nk=\binom n{n-k}$ отражает выбор дополнения: выбрать команду из трёх человек среди десяти — всё равно что указать семерых, которые не вошли.

Два полезных свойства

Разделим $k$ -элементные подмножества по тому, входит ли в них последний элемент. Если не входит, остаётся $\binom{n-1}k$ вариантов; если входит — $\binom{n-1}{k-1}$ . Так получается рекурсия Паскаля. А сумма всех коэффициентов строки равна $2^n$ : каждый из $n$ элементов независимо либо включён в подмножество, либо нет. Это утверждение о числе вариантов, не о вероятностной независимости случайных событий.

Три примера

$\binom84=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}=70$ . Сокращение факториалов избавляет от громоздких промежуточных чисел.
$\binom{12}{10}=\binom{12}2=66$ . Выбрать десять удобно через исключение двух.
У множества из пяти элементов всего $2^5=32$ подмножества. Если пустое запрещено, остаётся $32-1=31$ ; если запрещено и полное, остаётся 30.

Где можно ошибиться

Параметр $k$ — размер выбора, а не номер элемента. Коэффициент сам по себе не является вероятностью и часто больше единицы. В вероятностной задаче сначала выясняют, какие исходы равновозможны, а затем делят благоприятное число на общее. За пределами $0\le k\le n$ иногда вводят соглашение о нуле; это соглашение следует назвать явно, а не вычислять факториал отрицательного числа.

Формула, смысл и ограничения

Главные формулы с расшифровкой

\binom nk=\frac{n!}{k!(n-k)!}

Формула словами: Число k-элементных подмножеств n-элементного множества; целые 0 ≤ k ≤ n.

\sum_{k=0}^n\binom nk=2^n

Формула словами: Сумма по всем возможным размерам подмножества.

От формулы к наблюдению

Попробуйте самостоятельно

Измените параметры и сопоставьте расчёт с результатами случайного эксперимента.

Комбинаторика

От простого к сложному

Проверьте себя

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

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.