Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics III / 5 / b / ii

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 inways. 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 provesHere $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).