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

Let $x_i$ be the number of objects in box $i$. The arrangements correspond exactly to nonnegative integer solutions of $x_1+\cdots +x_k=n$. By stars and bars, place $n$ stars and $k-1$ separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives

Put one object into each box first. The remaining $n-k$ objects can be distributed without restrictions, so stars and bars givesEquivalently, the substitution $u_i=x_i-1$ gives a bijection between positive integer solutions of ${\sum }_i{x}_i=n$ and nonnegative integer solutions of ${\sum }_i{u}_i=n-k$.

Use mathematical induction. For $n=1$, the left side is $2^0=1=2^1-1$. If the identity holds at $n$, thenThe base case and induction step establish the geometric series identity

For the base case $n=2$, $1+1/\sqrt{2}>\sqrt{2}$, since multiplying by $\sqrt{2}$ reduces this to $\sqrt{2}+1>2$. Suppose the claimed inequality holds for some $n\ge 2$. The identitythen givesThus mathematical induction proves

The initial values of the two sequences agree: $c_0=d_0=1$ and $c_1=-1+c_0=0=d_1$. For $n\ge 2$, use the first-order recurrence relation at $n$ and $n-1$:Therefore $c_n$ satisfies exactly the same derangement recurrence as $d_n$. By strong induction, equality of the preceding two terms implies equality of the next term. ConsequentlyThe first-order recurrence relation therefore also counts derangements.

For a binary relation $R\subseteq A\times A$, reflexivity means $aRa$ for every $a\in A$; a symmetric relation satisfies $aRb\Rightarrow bRa$ for every $a,b\in A$; an antisymmetric relation satisfies $(aRb\text{ and }bRa)\Rightarrow a=b$ for every $a,b\in A$; transitivity means $(aRb\text{ and }bRc)\Rightarrow aRc$ for every $a,b,c\in A$; an irreflexive relation satisfies $\neg (aRa)$ for every $a\in A$. In particular, failure of reflexivity means at least one missing diagonal pair, whereas irreflexivity requires every diagonal pair to be missing.

There are $n^2$ possible ordered pairs and hence $2^{n^2}$ binary relations. A reflexive relation must contain the $n$ diagonal pairs, while its remaining $n^2-n$ pairs are unrestricted. Subtracting the reflexive relations givesbinary relations that are not reflexive.

A symmetric relation has $n$ independent choices on the diagonal. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs $\{a,b\}$ of distinct elements, either both ordered pairs are included or neither is. Thus there are $2^{n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ symmetric relations, so the requested number is

For each unordered pair $\{a,b\}$ with $a\ne b$, antisymmetry allows three choices: neither direction, only $(a,b)$, or only $(b,a)$. This contributes $3^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. The diagonal is unrestricted by antisymmetry, but being not irreflexive requires a nonempty subset of the $n$ diagonal pairs. There are $2^n-1$ such choices. HenceThis allows some diagonal pairs to be absent; “not irreflexive” does not require a reflexive relation.