= Solution
Group the elements of a colouring by equality of colour. This creates a unique <partition of a set> into nonempty unlabelled blocks, each of one colour, with distinct blocks assigned distinct colours.
For a <partition of a set> with $k$ blocks, assigning distinct colours to the blocks gives the <falling factorial> $x(x-1)\cdots(x-k+1)$ possibilities. To see that no extra factor $k!$ is needed, order the blocks canonically by their smallest elements, then assign colours in that order. There are $A(n,k)$ possible <set partitions> with $k$ blocks; these numbers are the <Stirling numbers of the second kind>.
Every colouring is counted exactly once in exactly one value of $k$, so
$$
\boxed{x^n=\sum_{k=1}^n A(n,k)x(x-1)\cdots(x-k+1).}
$$
For $k>x$, no colouring of the blocks is possible and the displayed <falling factorial> is zero, because one factor is $x-x$.
Back to article page
