Задача
COM-B1-M03-P013 Тождество Паскаля
#13
★★★☆☆ Уровень 3 из 5
Докажите комбинаторно, что \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Зафиксируйте один специальный элемент.
Считаем \(k\)-элементные подмножества \(n\)-элементного множества. Специальный элемент либо не выбран: \(\binom{n-1}{k}\), либо выбран: \(\binom{n-1}{k-1}\). Сумма этих двух непересекающихся случаев даёт все подмножества.
Очень важное доказательство идеей, а не алгеброй.