Задача
COM-B2-M01-P009 Две отмеченные точки
#9
★★★☆☆ Уровень 3 из 5
Докажите тождество \(\sum_{k=0}^n \binom{k}{2}\binom nk=\binom n2 2^{n-2}\).
Считайте подмножество и пару отмеченных элементов внутри него.
Считаем пары \((A,\{x,y\})\), где \(A\subseteq[n]\) и \(x,y\in A\). Если сначала выбрать \(A\) размера \(k\), получаем \(\binom{k}{2}\binom nk\). Суммируем по \(k\). Если сначала выбрать \(\{x,y\}\), есть \(\binom n2\) способов, а остальные \(n-2\) элементов можно выбирать свободно: \(2^{n-2}\) способов.
Это первый шаг к подсчёту троек и пересечений.