Dobiński's Formula

In combinatorial mathematics, Dobiński's formula states that the $n$th Bell number $B_n$, the number of partitions of a set of size $n$, equals

$B_n = \sum_^\infty \frac,$

where $e$ 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 $n$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 $n$ equals the $n$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 $n+o(n)$ terms, taking into account the information that $B_n$ is an integer. Precisely one has, for any integer $K > 1$
$B_n = \left\lceil \sum_^\frac\right\rceil$
provided $\frac\le 1$ (a condition that of course implies $K > n$, but that is satisfied by some $K$ of size $n+o(n)$). Indeed, since $K > n$, one has
$\begin \displaystyle\Big(\fracK\Big)^n &\le\Big(\fracK\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)\\ &=\frac1 \frac2 \dots \fracK\\ &=\frac. \end$
Therefore $\frac\le \frac\frac 1 \le \frac1$ for all $j \ge0$
so that the tail $\sum_ \frac=\sum_ \frac$ is dominated by the series $\sum_ \frac=e$, which implies $0 < B_n - \frac1\sum_^\frac<1$, whence the reduced formula.

Generalization

Dobiński's formula can be seen as a particular case, for $x=0$, of the more general relation:$\sum_^\infty \frac = \sum_^n \binom B_ x^$

and for $x=1$ in this formula for Touchard polynomials

$T_n(x) = e^\sum_^\infty \frac$

Proof

One proof relies on a formula for the generating function for Bell numbers,

$e^ = \sum_^\infty \frac x^n.$

The power series for the exponential gives

$e^ = \sum_^\infty \frac = \sum_^\infty \frac \sum_^\infty \frac$

so

$e^ = \frac \sum_^\infty \frac \sum_^\infty \frac$

The coefficient of $x^n$ in this power series must be $B_n/n!$, so

$B_n = \frac \sum_^\infty \frac.$

Another style of proof was given by Rota.. Recall that if $x$ and $n$ are nonnegative integers then the number of one-to-one functions that map a size-$n$ set into a size-$x$ set is the falling factorial

$(x)_n = x(x-1)(x-2)\cdots(x-n+1)$

Let $f$ be any function from a size-$n$ set $A$ into a size-$x$ set $B$. For any $b\in B$, let $f^(b)=\$. Then $\$ is a partition of $A$. Rota calls this partition the "kernel" of the function $f$. Any function from $A$ into $B$ factors into
* one function that maps a member of $A$ to the element of the kernel to which it belongs, and
* another function, which is necessarily one-to-one, that maps the kernel into $B$.
The first of these two factors is completely determined by the partition $\pi$ that is the kernel. The number of one-to-one functions from $\pi$ into $B$ is $(x)_$, where $, \pi,$ is the number of parts in the partition $\pi$. Thus the total number of functions from a size-$n$ set $A$ into a size-$x$ set $B$ is

$\sum_\pi (x)_,$

the index $\pi$ running through the set of all partitions of $A$. On the other hand, the number of functions from $A$ into $B$ is clearly $x^n$. Therefore, we have

$x^n = \sum_\pi (x)_.$

Rota continues the proof using linear algebra, but it is enlightening to introduce a Poisson-distributed random variable $X$ with mean 1. The equation above implies that the $n$th moment of this random variable is

\mathbb ^n= \sum_\pi \mathbbX)_/math>

where $\mathbb$ stands for expected value. But we shall show that all the quantities \mathbb X)_k/math> equal 1. It follows that

\mathbb ^n= \sum_\pi 1,

and this is just the number of partitions of the set $A$.

The quantity \mathbb X)_k/math> is called the $k$th factorial moment of the random variable $X$. To show that this equals 1 for all $k$ when $X$ is a Poisson-distributed random variable with mean 1, recall that this random variable assumes each value integer value $j \ge 0$ with probability $1/(ej!)$. Thus

\displaystyle\begin
\mathbb X)_k&= \sum_^\infty \frac \\
&= \frac \sum_^\infty \frac\\
& = \frac \sum_^\infty \frac = 1.
\end

Notes and references

{{DEFAULTSORT:Dobinski's formula
Combinatorics
Poisson point processes
Articles containing proofs