Why does a nonempty n-element set have exactly 2^(n-1) even-sized subsets, including the empty set?
Quant ResearchLevel: IntermediateParity bijection
Why does a nonempty n-element set have exactly 2^(n-1) even-sized subsets, including the empty set?
Hints
- Find an operation that flips parity.
- The operation must be invertible.
Answer
Fix one distinguished element and toggle whether it is present. This is a reversible pairing between even and odd subsets. Together there are 2^n subsets, so each class contains half.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial