дискретная-математика - Сумма биноминальных коэффициентов

При $%k\ge2$% имеет место следующее тождество: $$k(k-1)C_n^k=k(k-1)\frac{n!}{k!(n-k)!}=n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!}=n(n-1)C_{n-2}^{k-2}.$$ Далее мы суммируем в пределах $%2\le k\le n$%. Множитель $%n(n-1)$% не зависит от $%k$%, а сумма сочетаний из $%n-2$% по всем числам $%k-2=0,...,n-2$% равна $%2^{n-2}$%. В ответе получается $%n(n-1)2^{n-2}$%, где $%n\ge2$%.

Второй способ подсчёта, чисто комбинаторный: рассмотрим половину суммы; слагаемые при этом имеют вид $%C_n^k\cdot C_k^2$%. Это значит, что мы сначала выбираем из $%n$% элементов какие-то $%k\ge2$%, а затем из $%k$% элементов отмечаем какие-то два. Что получается в результате? Два отмеченных элемента -- их выбор осуществляется $%C_n^2$% способами, а также разбиение оставшихся элементов на два подмножества, в одном из которых имеется $%k-2\ge0$% элементов, а в другом $%n-k$%. Ясно, что после выбора отмеченной пары мы ровно $%2^{n-2}$% способами можем задать $%(k-2)$%-элементное подмножество для всевозможных значений $%k$%, так как при суммировании число $%k-2$% принимает все значения от $%0$% до $%n-2$%. Тем самым, найденная нами полусумма составляет $%C_n^2\cdot2^{n-2}$%, и после умножения на $%2$% мы приходим к тому же ответу.