A Proof of Dobinski’s Formula for Bell Numbers

Dobinski’s formula entails the following infinite series expression for the nth Bell number \varpi_n:

\displaystyle \varpi_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}.

In this post we’ll work through a proof of Dobinski’s formula.  We’ll need four formulas:

  1. The Maclaurin series for e^x: \displaystyle e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}.
  2. The formula for converting normal powers to falling factorial powers: \displaystyle x^n = \sum_{k=0}^n \left\{ n \atop k \right\} x^{\underline{k}}, where \left\{ n \atop k \right\} is a Stirling number of the second kind.
  3. The formula relating Bell numbers and Stirling numbers of the second kind: \displaystyle \varpi_n = \sum_{k=0}^n \left\{ n \atop k \right\}.  (This follows directly from the combinatorial definitions of the Bell numbers and the Stirling numbers of the second kind.)
  4. The representation of falling factorial powers as factorials: \displaystyle k^{\underline{m}} = \frac{k!}{(k-m)!}, valid when k \geq m and k, m \in \mathbb{N}.

Here we go… Starting with the infinite series expression \displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!}, convert to falling factorial powers to get

\displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!} = \sum_{k=0}^{\infty} \frac{1}{k!} \sum_{j=0}^n \left\{n \atop j \right\} k^{\underline{j}} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=0}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{n \atop j \right\} \sum_{k=j}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=j}^{\infty} \frac{1}{(k-j)!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{i=0}^{\infty} \frac{1}{i!} = \sum_{j=0}^n \left\{ n \atop j \right\} e.

Thus \displaystyle \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} = \frac{1}{e} \sum_{j=0}^n \left\{ n \atop j \right\} e = \varpi_n.

(I made a similar argument in this Math.SE question.)

Advertisements
This entry was posted in Bell numbers, sequences and series, Stirling numbers. Bookmark the permalink.

2 Responses to A Proof of Dobinski’s Formula for Bell Numbers

  1. Sergey Bond says:

    I think #4 condition is not needed since if k<j, then k(k-1)(k-2)..(k-j+1)=0 since one of the factors (one of the round brackets) will be 0. Thanks for the proof!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s