\section*{5. For ALL APPLICANTS.}
This question is about counting the number of ways of partitioning a set of $n$ elements into subsets, each with at least two and at most $n$ elements. If $n$ and $k$ are integers with $1 \leqslant k \leqslant n$, let $f ( n , k )$ be the number of ways of partitioning a set of $n$ elements into $k$ such subsets. For example, $f ( 5,2 ) = 10$ because the allowable partitions of $\{ 1,2,3,4,5 \}$ are

$$\begin{array} { l l } 
\{ 1,5 \} , \{ 2,3,4 \} , & \{ 1,2,5 \} , \{ 3,4 \} , \\
\{ 2,5 \} , \{ 1,3,4 \} , & \{ 3,4,5 \} , \{ 1,2 \} , \\
\{ 3,5 \} , \{ 1,2,4 \} , & \{ 1,3,5 \} , \{ 2,4 \} , \\
\{ 4,5 \} , \{ 1,2,3 \} , & \{ 2,4,5 \} , \{ 1,3 \} , \\
& \{ 1,4,5 \} , \{ 2,3 \} , \\
& \{ 2,3,5 \} , \{ 1,4 \} .
\end{array}$$

(i) Explain why $f ( n , k ) = 0$ if $k > n / 2$.\\
(ii) What is the value of $f ( n , 1 )$ and why?\\
(iii) In forming an allowable partition of $\{ 1,2 , \ldots , n + 1 \}$ into subsets of at least two elements, we can either

\begin{itemize}
  \item pair $n + 1$ with one other element, leaving $n - 1$ elements to deal with, or
  \item take an allowable partition of $\{ 1,2 , \ldots , n \}$ and add $n + 1$ to one of the existing subsets, making a subset of size three or more.
\end{itemize}

Use this observation to find an equation for $f ( n + 1 , k )$ in terms of $f ( n - 1 , k - 1 )$ and $f ( n , k )$ that holds when $2 \leqslant k < n$.\\
(iv) Use this equation to compute the value of $f ( 7,3 )$.\\
(v) Give a formula for $f ( 2 n , n )$ in terms of $n$ when $n \geqslant 1$ and show that it is correct.


If you require additional space please use the pages at the end of the booklet