Иногда из n различных элементов выбирают k, но порядок выбранных не важен: выбрать в жюри Петрова, Орлову и Волкова — то же самое, что выбрать Волкова, Петрова и Орлову.
Определение. Набор из k элементов, взятых из n-элементного множества без учёта порядка (0 ≤ k ≤ n), называется сочетанием из n по k. Число сочетаний обозначают C_n^k (от французского combinaison).
Как найти C_n^k. Упорядоченных наборов (размещений) A_n^k. Каждый неупорядоченный набор встречается среди них P_k = k! раз — столько способов переставить его элементы. Поэтому
C_n^k = (A_n^k)/(k!) = (n(n - 1) · … · (n - k + 1))/(k!) = (n!)/(k! · (n - k)!).
Пример 1. Сколькими способами из 9 участников кружка можно выбрать 4 на олимпиаду? Порядок не важен: C₉⁴ = (9 · 8 · 7 · 6)/(1 · 2 · 3 · 4) = 126.
Пример 2. На окружности 12 точек. Сколько хорд с концами в этих точках? Хорда задаётся парой точек без порядка: C₁₂² = (12 · 11)/2 = 66.
Размещения или сочетания? Спроси себя: если переставить выбранные элементы, получится новый вариант? Да — размещения (места, роли, порядок); нет — сочетания (команда, набор, комиссия).
Свойства. C_n⁰ = C_nⁿ = 1, C_n¹ = n, C_n^k = C_n⁽n - k) (выбрать k элементов — то же, что выбрать n - k, которые не возьмём), C_n^k + C_n⁽k + 1) = C₍n + 1)⁽k + 1) — по этому правилу строится треугольник Паскаля, например C₈² + C₈³ = 28 + 56 = 84 = C₉³. Сумма C_n⁰ + C_n¹ + … + C_nⁿ = 2ⁿ — это число всех подмножеств n-элементного множества: для n = 6 получаем 64. Числа C_n^k называют биномиальными коэффициентами.
Типичная ошибка — делить на k! там, где порядок важен (места, должности), или не делить там, где не важен (команда, набор).