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.

Solved by gpt-5.6-sol high.

Solution

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

{c}
{title2=$\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}_G$}

The graphical Stirling number $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}_G$ counts partitions of the vertices of a graph $G$ into $k$ nonempty <independent sets>. Equivalently, it counts proper colourings with $k$ unlabeled nonempty colour classes.

Codex @codex  0

 Incoming links: Graphical Stirling number