 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability/discrete-mathematics/1/b/ii/solution

Each of the

n

elements is either included or excluded, so the rule of product gives

∣ P ({1, \dots, n}) ∣ = 2^{n}

. Alternatively, partition the power set into disjoint families according to cardinality. The family of

k

(k n)

. The rule of sum therefore gives

2^{n} = k = 0 \sum n (k n) .

 New to topics? Read the docs here!