Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 1

Let $A$ and $B$ be the finite sets of objects satisfying the two properties. The rule of sum says that mutually exclusive alternatives have additive counts: if $A\cap B=\varnothing$, then $|A\cup B|=|A|+|B|$. Without disjointness, the corresponding inclusion-exclusion principle isThe rule of subtraction counts objects satisfying the first property but not the second:In particular, if the objects with the second property form a subset of those with the first, the count is $|A|-|B|$. These conditions prevent either double counting an overlap or subtracting objects that were not counted initially.

The rule of product says that if a construction has $r$ stages, with exactly $a_j$ choices at stage $j$ after every permitted earlier history, then it has ${\prod }_{j=1}^r{a}_j$ possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.

For a permutation of $n$ distinct objects, choose the first object in $n$ ways, the second in $n-1$ ways, and continue until only one remains. Thus the number isEvery ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For $n=0$, the unique empty arrangement agrees with $0!=1$.

An allocation is a tuple $(x_1,\dots ,x_k)$ of nonnegative integers with ${\sum }_j{x}_j=n$, where $x_j$ is the number in labelled box $j$. Empty boxes are allowed. Encode the allocation by $n$ stars and $k-1$ bars: put $x_1$ stars before the first bar, $x_2$ between the first two bars, and so on. Adjacent bars represent an empty intermediate box; a bar at an end represents an empty end box.

Reading the group sizes recovers exactly one allocation from every such string, so this is a bijection. There are $n+k-1$ positions and we choose the $k-1$ bar positions. Hence stars and bars givesNo extra factor for ordering the objects is present, because the objects are indistinguishable. For $k=1$ the string has no bars and gives the single allocation of all objects to that box; for $n=0$ all boxes are empty, also a single allocation.

Pad every integer from $0$ through $999999$ with leading zeros to obtain a unique six-digit decimal string. If its digits sum to $5$, each digit is automatically at most $5$, so the usual digit upper bound $9$ adds no restriction. We therefore count the nonnegative integer solutions ofBy stars and bars, there are $\left(\genfrac{}{}{0ex}{}{5+6-1}{6-1}\right)=\left(\genfrac{}{}{0ex}{}{10}{5}\right)$. The all-zero string is not counted because its digit sum is zero, so every counted integer is positive. Thus the answer is $252$.