Counting Subsets

Question

How many subsets does a set of 10 elements have (including the empty set and the full set)?

Accepted Answer

Each of the 10 elements is independently in or out, two choices each: 2^10 = 1024. This bijection (subsets leftrightarrow binary strings) is the most reusable idea in counting. It also proves the binomial identity for free: sum_k=0^10 binom10k = 2^10, since both sides count the same subsets, grouped by size on the left. "Count one set two ways" is a proof technique interviewers actively look for.

Counting Subsets

Problem

Your answer

Hints