Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 2

The Stirling number of the second kind $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ counts partitions of an $n$-element set into $k$ nonempty unlabeled blocks. Distinguishing the block containing the last element gives

Solved by gpt-5.6-sol high.

For a positive integer $x$, count functions $[n]\to [x]$ by the number $k$ of nonempty fibres. Their fibres form a $k$-block partition in $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ ways, and the blocks receive distinct images in $x^{\underline{k}}$ ways. HenceBoth sides are polynomials of degree $n$ agreeing at every positive integer, so this is a polynomial identity.

Solved by gpt-5.6-sol high.

Partitions of the vertices into independent blocks are the unlabeled colour-class partitions counted by the Graphical Stirling number. ThereforeSince ${\chi }_{P_n}(x)=x(x-1{)}^{n-1}$, the ordinary Stirling identity applied to $x-1$ givesUniqueness in the falling-factorial basis proves the claim.

Solved by gpt-5.6-sol high.

The sum is the chromatic polynomial of the path, so

Solved by gpt-5.6-sol high.

In an independent-block partition of $P_n$, either $v_1,v_n$ lie in different blocks, giving a partition valid for $C_n$, or they lie in the same block. Contracting those endpoints in the second case gives an independent-block partition of $C_{n-1}$. This bijection proves the recurrence. Multiplying by $x^{\underline{k}}$ and summing givesUsing ${\chi }_{P_n}=x(x-1{)}^{n-1}$ and induction from $C_2=P_2$ yields

Solved by gpt-5.6-sol high.

A proper colouring using exactly $k$ colours first partitions the vertices into $k$ nonempty independent colour classes and then injectively assigns $k$ of the $x$ named colours to those classes. These choices numberSumming over $k$ counts every proper colouring exactly once; the expression is the chromatic polynomial ${\chi }_G(x)$.

Solved by gpt-5.6-sol high.