Exercise 447Combinatorics › Counting principlesHigh schoolAdded 3 Nov 2026
Subsets and their complements
#subsets#complement#bijection
Statement
How many subsets of an -element set have even size?
Hint
Pair each subset with its complement, or use the binomial sum.
Show solutionHide solution
Solution
Method 1. For , subsets pair up with . If is odd, exactly one is even; there are even subsets. If is even, the pairing preserves parity; a more refined argument shows exactly half are even: .
Method 2. .
Conclusion. There are subsets of even size.