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

Each of the $n$ distinguishable elements has $x$ independent choices of colour. By the multiplication principle, the number of functions from the $n$-element set to the $x$-element colour set is

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$.

Using the probability mass function of the Poisson distribution directly givesFor each fixed positive integer $n$, this series converges: the ratio of successive nonzero terms is $(1+1/j{)}^n/(j+1)$, which tends to zero. Equivalently, using the polynomial identity in (ii) and the factorial moments from (a)(iv) gives $\mathbb{E}[X^n]={\sum }_{k=1}^{n}A(n,k)$; the extension of that identity to $X=0,1$ is justified in (iv).

Both sides of (ii) are polynomials in the colour count, and they agree at every integer $x\ge 2$. A nonzero polynomial has only finitely many roots, so this is a polynomial identity and holds also at $x=0,1$. It can therefore be evaluated at every possible value of the Poisson random variable $X$.

Take expectations and use the factorial moments from (a)(iv). The sum over $k$ is finite, so linearity of expectation givesCombining this with (iii) proves Dobiński's formula for the Bell numbers:For completeness, the empty set has one partition of a set, giving $B(0)=1$; that case uses the empty-product conventions $0^0=1$ in this identity and a $k=0$ term in the partition sum.