= Solution
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.
Back to article page
