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

For pairwise disjoint finite sets, the rule of sum givesThe password sets of different lengths are disjoint, so the required number is $P_4+P_6+P_8$.

The rule of subtraction isIn particular, if $B\subseteq A$ are finite sets, the set difference has cardinality $|A|-|B|$.

The rule of product says that a sequence of $k$ choices, with $n_i$ possibilities at stage $i$ regardless of earlier choices, has ${\prod }_{i=1}^k{n}_i$ possible outcomes. Applied to the Cartesian product of finite sets, it gives $|A\times B|=|A||B|$. Here independence means that the available choices do not restrict one another; no probability assumption is needed.

The rule of product counts $7^4$ unrestricted passwords and $6^4$ passwords containing no A. By the rule of subtraction, the answer is

The power set is $\mathcal{P}(A)=\{B:B\subseteq A\}$, the set of all subsets of $A$. In this case,

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

For finite sets, the inclusion-exclusion principle statesThus single-set cardinalities are added, pairwise-intersection cardinalities subtracted, triple-intersection cardinalities added, and so on.

Let $A_d$ contain the multiples of $d$ among $1,\dots ,999$. Its cardinality is $\lfloor 999/d\rfloor$, using the floor function. Because $3,7,11$ are pairwise coprime, their pairwise intersections correspond to divisibility by $21,33,77$, and their triple intersection to divisibility by $231$. The inclusion-exclusion principle gives