Exercise 882Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Counting pairs within subsets

#double counting#subsets#pairs

Statement

Show that $\sum_{S\subseteq\{1,\ldots,n\}}\binom{|S|}{2}=\binom{n}{2}2^{n-2}$ .

Hint

Double count pairs $(x,y)$ with $x<y$ both in $S$ .

Show solutionHide solution

First count. $\sum_S\binom{|S|}{2}$ counts, for each subset $S$ , the pairs inside $S$ .

Second count. Fix a pair $\{x,y\}$ . It's in $2^{n-2}$ subsets. Total: $\binom{n}{2}2^{n-2}$ .

Conclusion. Both equal the number of (subset, pair inside) pairs, giving the identity.