Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 8 / b / ii

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$, soFor $k>x$, no colouring of the blocks is possible and the displayed falling factorial is zero, because one factor is $x-x$.