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 $|\mathcal{P}(\{1,\dots ,n\})|=2^n$. Alternatively, partition the power set into disjoint families according to cardinality. The family of $k$-element subsets has size equal to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. The rule of sum therefore gives