Using generating functions one can see that the $n^{th}$ Bell number, i.e., the number of all possible partitions of a set of $n$ elements, is equal to $E(X^n)$ where $X$ is a Poisson random variable with mean 1. Is there a way to explain this connection intuitively?


One way may be to use these facts. You can decide if this is intuitive enough or not. :)

  1. $B_n = \sum_{k=0}^n \left\{n \atop k \right\}$, where $\left\{n \atop k \right\}$ is a Stirling number of the second kind. (The number $\left\{ n \atop k \right\}$ counts the number of ways to partition a set of $n$ elements into $k$ sets.)

  2. Stirling numbers of the second kind are used to convert ordinary powers to falling powers via $x^n = \sum_{k=0}^n x^{\underline{k}} \left\{n \atop k \right\}$, where $x^{\underline n} = x(x-1)(x-2) \cdots (x-n+1)$.

  3. The factorial moments of a Poisson$(1)$ distribution are all $1$; i.e., $E[X^{\underline{n}}] = 1$.

Putting them together yields

$$E[X^n] = \sum_{k=0}^n E[X^{\underline{k}}] \left\{n \atop k \right\} = \sum_{k=0}^n \left\{n \atop k \right\} = B_n.$$

Facts 1 and 2 are well-known properties of the Bell and Stirling numbers. Here is a quick proof of #3. The second step is the definition of expected value, using the Poisson probability mass function. The second-to-last step is the Maclaurin series expansion for $e^x$ evaluated at $1$.

$$E[X^{\underline{n}}] = E[X(X-1)(X-2) \cdots (X-n+1)] = \sum_{x=0}^{\infty} x(x-1) \cdots (x-n+1) \frac{e^{-1}}{x!}$$

$$= \sum_{x=n}^{\infty} x(x-1) \cdots (x-n+1) \frac{e^{-1}}{x!} = \sum_{x=n}^{\infty} \frac{x!}{(x-n)!} \frac{e^{-1}}{x!} = \sum_{y=0}^{\infty} \frac{e^{-1}}{y!} = e/e = 1.$$

  • $\begingroup$ Very interesting argument . $\endgroup$ – Arin Chaudhuri Oct 8 '10 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.