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

The probability generating function of a nonnegative integer-valued random variable isUse $s^0=1$, including at $s=0$. The power series converges absolutely for every real $s\in [-1,1]$, since ${\sum }_{j}p(j)|s{|}^j\le 1$. In particular it is always defined on the usual probability-generating interval $[0,1]$. It may also be defined for $|s|>1$, depending on the radius of convergence and convergence at its endpoints; the precise real domain of finite expectation is $\{s\in \mathbb{R}:{\sum }_{j}p(j)|s{|}^j<\infty \}$.

By hypothesis the power series converges at every positive real argument, so its radius of convergence is infinite. Termwise differentiation of a power series is therefore valid in a neighborhood of $s=1$. For $k\ge 1$,At $s=1$, the right side is the expectation of the falling factorial of $X$:The special case $k=1$ givesFor $k=0$, take the empty product as $1$; the equality becomes $G(1)=1$. These are the factorial moments.

Since $X^2=X(X-1)+X$, the probability generating function identities giveSubtracting the squared mean yields the variance

For the Poisson distribution with parameter $1$, the exponential series givesEvery derivative is $G^{(k)}(s)=e^{s-1}$, so the factorial moments areIn particular $G^{\prime }(1)=G^{\prime \prime }(1)=1$, and the variance is

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.