Задача
COM-B1-M04-P013 Общее тождество о размерах
#13
★★★☆☆ Уровень 3 из 5
Докажите комбинаторно, что \(\sum_{k=0}^n kC(n,k)=n2^{n-1}\).
Считайте пары \((S,x)\), где \(x\in S\).
По размеру \(S=k\): есть \(C(n,k)\) подмножеств и \(k\) способов выбрать отмеченный элемент, получаем левую часть. По отмеченному элементу: \(n\) вариантов для \(x\), остальные \(n-1\) элементов выбираются в \(S\) произвольно, \(2^{n-1}\) способов. Получаем правую часть.
Ключевое тождество модуля.