\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
An $n$-fan consists of a row of $n$ points, the tips, in a straight line, together with another point, the hub, that is not on the line. The $n$ tips are joined to each other and to the hub with line segments. For example, the left-hand picture here shows a 6 -fan,\\
\includegraphics[max width=\textwidth, alt={}, center]{a86ae71c-8798-4752-b262-80c21427f83e-20_382_314_758_543}\\
\includegraphics[max width=\textwidth, alt={}, center]{a86ae71c-8798-4752-b262-80c21427f83e-20_382_317_758_1139}

For a given $n$-fan, an $n$-span is a subset containing all $n + 1$ points and exactly $n$ of the line segments, chosen so that all the points are connected together, with a unique path between any two points. The right-hand picture shows one of many 6 -spans obtained from the given 6 -fan; in this 6 -span, the tips are in "groups" of 3,1 and 2 , with the top "group" containing 3 tips.\\
(i) Draw all three 2 -spans.\\
(ii) Draw all 3 -spans.\\
(iii) By considering the possible sizes of the top group of tips and how the group is connected to the hub, calculate the number of 4 -spans.\\
(iv) For $n \geqslant 1$ let $z _ { n }$ denote the number of $n$-spans. Give an expression for $z _ { n }$ in terms of $z _ { k }$, where $1 \leqslant k < n$. Use this expression to show that $z _ { 5 } = 55$.\\
(v) Use this relationship to calculate $z _ { 6 }$.


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

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

M