Размещения и сочетания: биномиальный коэффициент

Учимся выбирать часть объектов: с учётом порядка (размещения) и без (сочетания).

Сочетание из $n$ по $k$ — это выбор $k$ объектов из $n$ без учёта порядка; их число обозначают $\binom{n}{k}$.

Перестановки упорядочивали все объекты. Но чаще нужно выбрать лишь часть: $k$ из $n$. Тут важно, считаем ли мы порядок. Если да — это размещения, если нет — сочетания. Различие определяет, какую формулу применять, и ошибка здесь — источник большинства неправильных ответов в задачах на вероятность. Простой способ не запутаться — придумать «тест на порядок»: поменяйте местами два выбранных объекта и спросите, изменился ли результат. Пьедестал почёта (золото-серебро-бронза) — порядок важен, перестановка призёров даёт другой расклад, это размещения. Букет из трёх цветов — порядок не важен, роза-тюльпан-ромашка и ромашка-роза-тюльпан это один и тот же букет, это сочетания. PIN-код — размещения, рука в покере — сочетания, состав сборной — сочетания, а распределение ролей в этой сборной — уже размещения. Привыкнув задавать себе этот вопрос, вы перестанете путать две формулы.

Размещения: порядок важен

Размещение — это выбор $k$ объектов из $n$ с учётом порядка. Первое место — $n$ вариантов, второе — $n-1$, и так $k$ шагов:

$$A_n^k=\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1).$$

Например, сколько трёхбуквенных «слов» из различных букв можно составить из 5 разных букв? Это $A_5^3=5\cdot 4\cdot 3=60$.

Сочетания: порядок не важен

Если порядок не важен, каждое сочетание мы посчитали $k!$ раз (по числу его внутренних перестановок). Поэтому делим:

$$\binom{n}{k}=\frac{n!}{k!\,(n-k)!}.$$

Это и есть биномиальный коэффициент. Проверим его перебором: itertools.combinations выдаёт все сочетания, а math.comb считает $\binom{n}{k}$ напрямую.

import math, itertools

for n, k in [(5, 2), (6, 3), (10, 4), (12, 5)]:
    items = range(n)
    brute = sum(1 for _ in itertools.combinations(items, k))
    print(f"C({n},{k}): перебор={brute:>4}, формула={math.comb(n, k):>4}")

Вывод:

C(5,2): перебор=  10, формула=  10
C(6,3): перебор=  20, формула=  20
C(10,4): перебор= 210, формула= 210
C(12,5): перебор= 792, формула= 792

Симметрия и треугольник Паскаля

Биномиальные коэффициенты обладают красивой симметрией:

$$\binom{n}{k}=\binom{n}{n-k}.$$

Выбрать $k$ объектов «в команду» — то же самое, что выбрать $n-k$ «не в команду». А соседние коэффициенты связаны правилом Паскаля $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$, которое порождает знаменитый треугольник.

Применение к вероятности

Сочетания нужны, чтобы считать вероятности «выбора кучкой». Какова вероятность вытащить 2 туза из 4, выбрав наугад 2 карты из 4 тузов и 4 королей (8 карт)? Благоприятных исходов $\binom{4}{2}=6$, всех — $\binom{8}{2}=28$, значит $P=6/28\approx 0{,}2143$. Проверим симуляцией.

import random, math
random.seed(3)

deck = ["A", "A", "A", "A", "K", "K", "K", "K"]
n = 500000
two_aces = 0
for _ in range(n):
    hand = random.sample(deck, 2)
    if hand.count("A") == 2:
        two_aces += 1
print("Симуляция:", round(two_aces / n, 4))
print("Теория:   ", round(math.comb(4,2)/math.comb(8,2), 4))

Вывод:

Симуляция: 0.2147
Теория:    0.2143

Как работает под капотом

Функция random.sample выбирает $k$ элементов без повторов, причём все $\binom{n}{k}$ подмножеств равновероятны — поэтому доля «удачных» рук стремится к отношению сочетаний. А math.comb вычисляет биномиальный коэффициент эффективно, без построения огромного факториала целиком, сокращая дробь по ходу — иначе для больших $n$ числа не поместились бы в память даже у Python с его длинной арифметикой.

Частые ошибки

Главная путаница — между размещениями и сочетаниями. Спросите себя: «важен ли порядок?» Пароли и пьедесталы — размещения; команды, букеты, руки карт — сочетания. Вторая ошибка — делить на $k!$ дважды или забыть поделить вовсе. Третья — применять эти формулы при выборе с возвратом (когда объект можно взять повторно): там работают другие, степенные формулы.

Итог

• Размещения учитывают порядок: $A_n^k=\dfrac{n!}{(n-k)!}$.
• Сочетания порядок игнорируют: $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$.
• Симметрия $\binom{n}{k}=\binom{n}{n-k}$ и правило Паскаля упрощают подсчёты.
• В вероятности сочетания дают число благоприятных исходов при выборе «кучкой».