Задача
COM-B2-M01-P004 Все подмножества
#4
★★☆☆☆ Уровень 2 из 5
Докажите комбинаторно тождество \(\sum_{k=0}^{n}\binom nk=2^n\).
Посчитайте все подмножества \(n\)-элементного множества.
Правая часть \(2^n\) считает подмножества по независимому выбору: каждый элемент либо входит, либо не входит. Левая часть считает те же подмножества по размеру: сначала выбираем размер \(k\), затем само \(k\)-элементное подмножество. Это один и тот же набор объектов, значит тождество доказано.
Даже базовое тождество нужно объяснять через объект подсчёта.