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

A derangement of a finite set $A$ is a permutation $\sigma :A\to A$ with no fixed point: $\sigma (a)\ne a$ for every $a\in A$. Thus every element is moved, although the permutation remains a bijection.

The initial values are $d_1=0$ and $d_2=1$: one element cannot move, while two elements must be swapped.

For $n\ge 3$, fix one distinguished element, called $n$, and choose its image $j\ne n$, in $n-1$ ways. If $n,j$ form a two-cycle, deleting them leaves an arbitrary derangement on the other $n-2$ elements, giving $d_{n-2}$ choices.

Otherwise the permutation cycle containing $n$ has length at least three. Remove $n$ from that cycle, joining its predecessor directly to $j$. No fixed point is created because the predecessor is not $j$. This gives a derangement on $n-1$ elements. Conversely, any such derangement uniquely recovers the original one by inserting $n$ immediately before $j$ in its cycle. This case contributes $d_{n-1}$ choices for each $j$.

The two cases are disjoint and exhaustive, so the derangement recurrence is

An upper bound of $S$ is an element $u\in A$ with $s⪯u$ for every $s\in S$. It need not belong to $S$. A maximum, or greatest element, is an $m\in S$ with that same property. A least upper bound is an upper bound $\ell \in A$ satisfying $\ell ⪯u$ for every upper bound $u$.

A maximum belongs to $S$; a least upper bound need not. In a partially ordered set, an existing maximum is automatically the least upper bound, and the antisymmetric relation condition makes each unique.

Put $J=\{k\in \mathbb{N}:k\le 100\}$, avoiding any dependence on whether the convention includes $0$ among the natural numbers. Under set inclusion, the results are

The set union of all three-element subsets of $\mathbb{N}$ is $\mathbb{N}$. An upper bound for $S_1$ under set inclusion would have to contain this entire infinite set, whereas members of $A$ are finite. Thus $S_1$ has no upper bound and hence no maximum or least upper bound.

For $S_2$, every member is a subset of the finite set $J$, and $J$ itself belongs to $S_2$, making it both maximum and least upper bound. The union of the three-element subsets of $J$ is again $J$, so $J$ is the least upper bound of $S_1\cap S_2$. It is not a member of that family, and no three-element member contains all the others, so there is no maximum.

The displayed relation is not a partial order on the printed $A$. Since the empty set belongs to $A$, vacuous truth makeshold for every finite $T$, including nonempty $T$. This violates the defining condition of an antisymmetric relation. It also violates transitivity: $\{2\}{⪯}_2\varnothing {⪯}_2\{1\}$ holds, but $\{2\}{⋠}_2\{1\}$. Consequently the usual unique-maximum and unique-least upper bound terminology for a partially ordered set does not apply as claimed.

The available inputs still determine what happens if one applies the formulas in (b) literally to this relation:

For $S_1$, no nonempty finite set can lie above all triples of arbitrarily large numbers, while $\varnothing$ does so vacuously. Thus $\varnothing$ is its sole literal upper bound, but is not a member of $S_1$. For each of the two bounded families, the literal upper bounds are $\varnothing$ and all nonempty finite sets whose elements are at least $100$. Among these, exactly $\varnothing$ and $\{100\}$ lie below every such upper bound. Both belong to $S_2$, but neither belongs to its three-element subfamily.

For comparison, a natural correction is to retain the given rule for nonempty sets and declare $\varnothing$ to be a bottom element: no nonempty set is then below $\varnothing$. Under this explicitly corrected partial order, $S_1$ has neither a maximum nor a least upper bound; $S_2$ has maximum and least upper bound $\{100\}$; and $S_1\cap S_2$ has no maximum but has least upper bound $\{100\}$. A nonempty upper bound must have every element at least as large as every element of the bounded family. These corrected answers are conditional on the stated repair, not answers obtained by silently excluding the empty set from the source.

False. For $n\ge 3$, every factor from $3$ through $n$ is at least $3$, soNo fixed multiple of $2^n$ eventually bounds the factorial, contradicting the definition of Big O notation. No use of Stirling's approximation is required.

True. For every $n\ge 4$, $2\le \sqrt{n}$, and raising both nonnegative sides to the $n$th power givesThus the Big O notation condition holds with constant $C=1$ and threshold $n_0=4$.

False. It suffices to find a subsequence along which the ratio is unbounded. Set $n=4m$. The last $3m$ factors of $(4m)!$ are at least $m$, while the first $m$ factors have product at least one. HenceThis contradicts the eventual uniform bound required by Big O notation. The proof is an elementary factorial comparison, independent of Stirling's approximation.