Задача
COM-B1-M04-P022 Квадрат размера подмножества
#22
★★★★☆ Уровень 4 из 5
Докажите комбинаторно, что \(\sum_{k=0}^n k^2C(n,k)=n(n+1)2^{n-2}\).
Считайте тройки \((S,x,y)\), где \(x,y\in S\), причём \(x\) и \(y\) могут совпадать.
По размеру \(S=k\) получаем \(k^2\) способов выбрать упорядоченную пару \((x,y)\), значит левая часть. Теперь считаем по \((x,y)\). Если \(x=y\), выбираем этот элемент \(n\) способами, остальные элементы \(S\) произвольны: \(2^{n-1}\). Если \(x e y\), выбираем упорядоченную пару \(n(n-1)\) способами, остальные \(n-2\) элементов произвольны: \(2^{n-2}\). Итого \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).
Сильная identity-задача для первого уровня.