Комбинаторное тождество часто означает, что один и тот же набор объектов посчитан двумя способами. Это даёт доказательство без вычисления больших факториалов и помогает запомнить общую формулу.
C(n,k)=C(n−1,k−1)+C(n−1,k)
Обозначения и задача
C(n, k) — число k-элементных подмножеств n-элементного множества. Все параметры ниже — неотрицательные целые, выборы допустимы; C(n, k) = 0 при k вне диапазона 0,…,n. Рассмотрим девять равенств источника, обобщим их и дадим словесную и алгебраическую проверку.
1. Симметрия
C(10, 7) = C(10, 3); в общем C(n, k) = C(n, n − k).
Выбрать k книг — то же самое, что указать n − k оставленных. Алгебраически обе стороны равны n!/[k!(n − k)!].
2. Правило Паскаля
C(10, 3) + C(10, 4) = C(11, 4); в общем C(n, k − 1) + C(n, k) = C(n + 1, k).
Разделим k-элементные подмножества n + 1 объектов на содержащие выделенный объект и не содержащие его. Алгебраически приведение двух факториальных дробей к общему знаменателю даёт множитель k + (n + 1 − k) = n + 1.
3. Все подмножества
Σk=0⁴ C(4, k) = 2⁴; в общем Σk=0ⁿ C(n, k) = 2ⁿ.
Каждый объект либо включается, либо нет — n независимых двоичных решений. Алгебраически подставляем x = 1 в разложение (1 + x)ⁿ.
4. Группа с руководителем
4C(10, 4) = 10C(9, 3); в общем kC(n, k) = nC(n − 1, k − 1).
Можно сначала выбрать группу и руководителя в ней либо руководителя и остальных участников. Подстановка факториалов сокращает k против k! и n против n!, оставляя одну и ту же дробь.
5. Две непересекающиеся группы
C(10, 3)C(7, 2) = C(10, 2)C(8, 3).
В общем C(n, a)C(n − a, b) = C(n, b)C(n − b, a). Можно сначала выбрать группу типа А либо группу типа Б. Типы различаются, а внутри групп порядок не важен. Обе стороны равны n!/[a!b!(n − a − b)!].
6. Любое подмножество с выделенным участником
Σk=1⁵ kC(5, k) = 5 · 2⁴; в общем Σk=1ⁿ kC(n, k) = n2n−1.
Сначала выбираем выделенного участника n способами, затем произвольное подмножество остальных. Алгебраически дифференцируем (1 + x)ⁿ и подставляем x = 1. Равносильно можно применить тождество 4 к каждому слагаемому.
7. Тождество хоккейной клюшки
C(2, 2) + … + C(6, 2) = C(7, 3).
Общая форма: Σj=kⁿ C(j, k) = C(n + 1, k + 1). Выбираем k + 1 чисел из 1,…,n + 1 и группируем наборы по максимальному числу j + 1. Остальные k выбираются из первых j. Алгебраически используем C(j, k) = C(j + 1, k + 1) − C(j, k + 1); сумма телескопическая.
8. Тождество Вандермонда
Σk=0³ C(4, k)C(5, 3 − k) = C(9, 3).
Для двух групп размеров m и n число способов выбрать r человек равно Σ C(m, k)C(n, r − k) = C(m + n, r). Слева группируем выборы по числу участников из первой группы. Алгебраически сравниваем коэффициент при xʳ в (1 + x)ᵐ(1 + x)ⁿ = (1 + x)m+n.
9. Сумма квадратов сочетаний
Σk=0⁵ C(5, k)² = C(10, 5); в общем Σk=0ⁿ C(n, k)² = C(2n, n).
Выбираем n человек из двух групп по n. Если из первой взято k, из второй нужно n − k; по симметрии C(n, n − k) = C(n, k). Это частный случай Вандермонда и одновременно его алгебраическое доказательство.
В словесной подсказке источника к последнему примеру ошибочно говорится о выборе четырёх человек. Для написанного равенства нужно выбрать пять. Здесь объяснение приведено в соответствие с формулой. Общие формы и алгебраические доказательства дополнены редакцией.
Четыре задачи на применение сочетаний · Математика.
Б. Демешев и участники · probability_pro, 5.1 · CC BY 4.0. Адаптация; доказательства дополнены, подсказка уточнена.