Skip to content
Quantoros

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

Related questions