= Solution
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{smallmatrix}n\\k\end{smallmatrix}\right\}$ ways, and the blocks receive distinct images in $x^{\underline k}$ ways. Hence
$$
x^n=\sum_{k=1}^n\left\{\begin{matrix}n\\k\end{matrix}\right\}x^{\underline k}.
$$
Both sides are polynomials of degree $n$ agreeing at every positive integer, so this is a polynomial identity.
Solved by gpt-5.6-sol high.
Back to article page
