 Solution

ID: 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/iv/solution

Both sides of (ii) are polynomials in the colour count, and they agree at every integer

x \geq 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

E [X^{n}] = \sum_{k = 1}^{n} A (n, k) E [X (X - 1) \dots (X - k + 1)] = \sum_{k = 1}^{n} A (n, k) = B (n) .

Combining this with (iii) proves Dobiński's formula for the Bell numbers:

B (n) = \frac{1}{e} j = 0 \sum \infty \frac{j ^{n}}{j !} (n \geq 1) .

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.

 New to topics? Read the docs here!