In combinatorial mathematics, Dobiński's formula states that the <math>n</math>th Bell number <math>B_n</math>, the number of partitions of a set of size <math>n</math>, equals
<math display=block>B_n = {1 \over e}\sum_{k=0}^\infty \frac{k^n}{k!},</math>
where <math>e</math> denotes Euler's number.
The formula is named after G. Dobiński, who published it in 1877.
Probabilistic content
In the setting of probability theory, Dobiński's formula represents the <math>n</math>th moment of the Poisson distribution with mean 1. Sometimes Dobiński's formula is stated as saying that the number of partitions of a set of size <math>n</math> equals the <math>n</math>th moment of that distribution.
Reduced formula
The computation of the sum of Dobiński's series can be reduced to a finite sum of <math>n+o(n)</math> terms, taking into account the information that <math>B_n</math> is an integer. Precisely one has, for any integer <math>K > 1</math>
<math display=block>B_n = \left\lceil {1 \over e}\sum_{k=0}^{K-1}\frac{k^n}{k!}\right\rceil</math>
provided <math>\frac{K^n}{K!}\le 1</math> (a condition that of course implies <math>K > n</math>, but that is satisfied by some <math>K</math> of size <math>n+o(n)</math>). Indeed, since <math>K > n</math>, one has
<math display=block>\begin{align}
\displaystyle\Big(\frac{K+j}K\Big)^n &\le\Big(\frac{K+j}K\Big)^K=\Big(1+\frac jK\Big)^K \\
&\le \Big(1+\frac j1\Big)\Big(1+\frac j2\Big)\dots\Big(1+\frac jK\Big)\\
&=\frac{1+j}1 \frac{2+j}2 \dots \frac{K+j}K\\
&=\frac{(K+j)!}{K!j!}.
\end{align}</math>
Therefore <math>\frac{(K+j)^n}{(K+j)!}\le \frac{K^n}{K!}\frac 1{j!} \le \frac1{j!}</math> for all <math>j \ge0</math>
so that the tail <math>\sum_{k\ge K} \frac{k^n}{k!}=\sum_{j\ge 0} \frac{(K+j)^n}{(K+j)!}</math> is dominated by the series <math>\sum_{j\ge 0} \frac{1}{j!}=e</math>, which implies <math>0 < B_n - \frac1{e}\sum_{k=0}^{K-1}\frac{k^n}{k!}<1</math>, whence the reduced formula.
Generalization
Dobiński's formula can be seen as a particular case, for <math>x=0</math>, of the more general relation:<math display="block">{1 \over e}\sum_{k=x}^\infty \frac{k^n}{(k-x)!} = \sum_{k=0}^n \binom{n}{k} B_{k} x^{n-k}</math>
and for <math>x=1</math> in this formula for Touchard polynomials
<math display="block">T_n(x) = e^{-x}\sum_{k=0}^\infty \frac{x^kk^n}{k!}</math>
Proof
One proof relies on a formula for the generating function for Bell numbers,
<math display=block> e^{e^x - 1} = \sum_{n = 0}^\infty \frac{B_n}{n!} x^n. </math>
The power series for the exponential gives
<math display=block> e^{e^x} = \sum_{k = 0}^\infty \frac{e^{kx{k!} =
\sum_{k = 0}^\infty \frac{1}{k!} \sum_{n = 0}^\infty \frac{(kx)^n}{n!} </math>
so
<math display=block>e^{e^x - 1} = \frac{1}{e} \sum_{k = 0}^\infty \frac{1}{k!} \sum_{n = 0}^\infty \frac{(kx)^n}{n!} </math>
The coefficient of <math>x^n</math> in this power series must be <math>B_n/n!</math>, so
<math display=block>B_n = \frac{1}{e} \sum_{k = 0}^\infty \frac{k^n}{k!}.</math>
Another style of proof was given by Rota. Recall that if <math>x</math> and <math>n</math> are nonnegative integers then the number of one-to-one functions that map a size-<math>n</math> set into a size-<math>x</math> set is the falling factorial
<math display=block>(x)_n = x(x-1)(x-2)\cdots(x-n+1)</math>
Let <math>f</math> be any function from a size-<math>n</math> set <math>A</math> into a size-<math>x</math> set <math>B</math>. For any <math>b\in B</math>, let <math>f^{-1}(b)=\{a\in A:f(a)=b\}</math>. Then <math>\{f^{-1}(b):b\in B\}</math> is a partition of <math>A</math>. Rota calls this partition the "kernel" of the function <math>f</math>. Any function from <math>A</math> into <math>B</math> factors into
- one function that maps a member of <math>A</math> to the element of the kernel to which it belongs, and
- another function, which is necessarily one-to-one, that maps the kernel into <math>B</math>.
The first of these two factors is completely determined by the partition <math>\pi</math> that is the kernel. The number of one-to-one functions from <math>\pi</math> into <math>B</math> is <math>(x)_{|\pi|}</math>, where <math>|\pi|</math> is the number of parts in the partition <math>\pi</math>. Thus the total number of functions from a size-<math>n</math> set <math>A</math> into a size-<math>x</math> set <math>B</math> is
<math display=block>\sum_\pi (x)_{|\pi|},</math>
the index <math>\pi</math> running through the set of all partitions of <math>A</math>. On the other hand, the number of functions from <math>A</math> into <math>B</math> is clearly <math>x^n</math>. Therefore, we have
<math display=block>x^n = \sum_\pi (x)_{|\pi|}.</math>
Rota continues the proof using linear algebra, but it is enlightening to introduce a Poisson-distributed random variable <math>X</math> with mean 1. The equation above implies that the <math>n</math>th moment of this random variable is
<math display=block>\mathbb{E}[X^n] = \sum_\pi \mathbb{E}[(X)_{|\pi|}]</math>
where <math>\mathbb{E}</math> stands for expected value. But we shall show that all the quantities <math>\mathbb{E}[(X)_k]</math> equal 1. It follows that
<math display=block>\mathbb{E}[X^n] = \sum_\pi 1,</math>
and this is just the number of partitions of the set <math>A</math>.
The quantity <math>\mathbb{E}[(X)_k]</math> is called the <math>k</math>th factorial moment of the random variable <math>X</math>. To show that this equals 1 for all <math>k</math> when <math>X</math> is a Poisson-distributed random variable with mean 1, recall that this random variable assumes each value integer value <math>j \ge 0</math> with probability <math>1/(ej!)</math>. Thus
<math display=block>\displaystyle\begin{align}
\mathbb{E}[(X)_k] &= \sum_{j = 0}^\infty \frac{(j)_k}{ej!} \\
&= \frac{1}{e} \sum_{j = 0}^\infty \frac{j(j-1) \cdots (j-k+1)}{j(j-1) \cdots 1}\\
& = \frac{1}{e} \sum_{j = i}^\infty \frac{1}{(j-i)!} = 1.
\end{align}</math>