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

There are $n$ choices for the first position, then $n-1$ choices for the second, and so on down to one choice. The multiplication principle therefore gives $n!$ permutations. This also agrees with the empty permutation convention $0!=1$.

Let $E_i$ be the set of permutations fixing object $i$. If a specified collection of $k$ objects is fixed, the remaining $n-k$ objects can be arranged in $(n-k)!$ ways. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such collections. Applying the inclusion-exclusion principle to exclude all fixed objects givesFor $n\ge 1$, the terms $k=0$ and $k=1$ cancel. Thus the number of derangements is $d_n=\frac{n!}{2!}-\frac{n!}{3!}+\cdots +(-1{)}^n\frac{n!}{n!}$, interpreting the remaining sum as empty when $n=1$. The full inclusion-exclusion formula also gives $d_0=1$.

The base case $n=3$ isAssume the displayed formula holds at some $n\ge 3$. Adding the next term yieldsThe last step uses $(2n-1)(n+1)-2n=(2n+1)(n-1)$. This is the required formula at $n+1$, completing the proof by mathematical induction. The identity holds for all $n\ge 3$.

Use mathematical induction with two consecutive base cases: $F_2=1=(3/2{)}^0$ and $F_3=2\ge (3/2{)}^1$. Suppose the bounds hold for exponents $n$ and $n+1$. The Fibonacci recurrence givesThus the consecutive pair of bounds advances one step. $F_{n+2}\ge (3/2{)}^n$ for every $n\ge 0$.

Pad every number with leading zeros to obtain exactly $n$ decimal digits. Its digits are a solution of $d_1+\cdots +d_n=9$ in nonnegative integers. Conversely every such solution is a valid digit string, since no individual digit can exceed $9$; its digit sum also excludes the number zero. The stars and bars count therefore givesFor $n\ge 1$, $n+j\le n(j+1)$, so $f(n)\le n^9{\prod }_{j=0}^8(j+1)/9!=n^9$. Thus $f(n)=O(n^9)$, with an explicit Big O notation constant $C=1$ and threshold $n=1$.