= Solution
{c}
Every assignment determines a unique <set partition> into its nonempty colour classes. If there are $k$ such <blocks of a set partition>, there are $A(n,k)$ choices for that <set partition>. For each fixed choice, assign distinct colours to the $k$ <blocks of a set partition> in
$$
(x)_k=x(x-1)\cdots(x-k+1)
$$
ways. Although the <blocks of a set partition> are unlabelled, they are distinguishable by their elements: ordering them temporarily, for instance by their least elements, counts each assignment exactly once. The <falling factorial> is zero when $k>x$, as it should be. Summing over the possible numbers of used colours proves
$$
\boxed{x^n=\sum_{k=1}^n A(n,k)(x)_k.}
$$
Here $A(n,k)$ is the <Stirling number of the second kind>. Both sides are <polynomials> in $x$ and agree at infinitely many integers $x>2$, so the identity also holds for every real $x$, including $0,1,2$. This extension will justify substituting the <random variable> $X$ in part (iii).
Back to article page
