Partitions of the vertices into independent blocks are the unlabeled colour-class partitions counted by the <Graphical Stirling number>. Therefore
$$
\chi_{P_n}(x)=\sum_k\left\{\begin{matrix}n\\k\end{matrix}\right\}_{P_n}x^{\underline k}.
$$
Since $\chi_{P_n}(x)=x(x-1)^{n-1}$, the ordinary Stirling identity applied to $x-1$ gives
$$
x(x-1)^{n-1}
=\sum_k\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}x^{\underline k}.
$$
Uniqueness in the falling-factorial basis proves the claim.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-145/2/c/solution