Maths WorkshopMaths problems with full solutions
Exercise 447Combinatorics › Counting principlesHigh schoolAdded 3 Nov 2026

Subsets and their complements

#subsets#complement#bijection

Statement

How many subsets of an nn-element set have even size?

Hint

Pair each subset with its complement, or use the binomial sum.

Show solutionHide solution

Solution

Method 1. For n≥1n\ge1, subsets pair up (S,Sˉ)(S,\bar S) with ∣S∣+∣Sˉ∣=n|S|+|\bar S|=n. If nn is odd, exactly one is even; there are 2n−12^{n-1} even subsets. If nn is even, the pairing preserves parity; a more refined argument shows exactly half are even: 2n−12^{n-1}.

Method 2. ∑k even(nk)=(1+1)n+(1−1)n2=2n−1\sum_{k\text{ even}}\binom{n}{k}=\frac{(1+1)^n+(1-1)^n}{2}=2^{n-1}.

Conclusion. There are 2n−12^{n-1} subsets of even size.