Задача
COM-B2-M03-P007 Тождество Паскаля
#7
★★★☆☆ Уровень 3 из 5
Докажите биекцией тождество \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Разделите \(k\)-подмножества по тому, содержат ли они элемент \(n\).
Все \(k\)-подмножества множества \([n]\) делятся на два класса. Если подмножество не содержит \(n\), оно является \(k\)-подмножеством \([n-1]\): \(\binom{n-1}{k}\) вариантов. Если содержит \(n\), то остальные \(k-1\) элементов выбираются из \([n-1]\): \(\binom{n-1}{k-1}\) вариантов. Эти классы не пересекаются и покрывают все объекты.
Здесь скорее разбиение на случаи, но с явной биекцией каждого класса.