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}={1 \over e}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}},$$

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 {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right\rceil$$ provided ${\frac {K^{n}}{K!}}\leq 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{aligned}\displaystyle {\Big (}{\frac {K+j}{K}}{\Big )}^{n}&\leq {\Big (}{\frac {K+j}{K}}{\Big )}^{K}={\Big (}1+{\frac {j}{K}}{\Big )}^{K}\\&\leq {\Big (}1+{\frac {j}{1}}{\Big )}{\Big (}1+{\frac {j}{2}}{\Big )}\dots {\Big (}1+{\frac {j}{K}}{\Big )}\\&={\frac {1+j}{1}}{\frac {2+j}{2}}\dots {\frac {K+j}{K}}\\&={\frac {(K+j)!}{K!j!}}.\end{aligned}}$$ Therefore ${\frac {(K+j)^{n}}{(K+j)!}}\leq {\frac {K^{n}}{K!}}{\frac {1}{j!}}\leq {\frac {1}{j!}}$ for all $j\geq 0$ so that the tail $\sum _{k\geq K}{\frac {k^{n}}{k!}}=\sum _{j\geq 0}{\frac {(K+j)^{n}}{(K+j)!}}$ is dominated by the series $\sum _{j\geq 0}{\frac {1}{j!}}=e$, which implies $0<B_{n}-{\frac {1}{e}}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}<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:$${1 \over e}\sum _{k=x}^{\infty }{\frac {k^{n}}{(k-x)!}}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}x^{n-k}$$

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

$$T_{n}(x)=e^{-x}\sum _{k=0}^{\infty }{\frac {x^{k}k^{n}}{k!}}$$

Proof

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

$$e^{e^{x}-1}=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}.$$

The power series for the exponential gives

$$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!}}$$

so

$$e^{e^{x}-1}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}$$

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

$$B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.$$

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^{-1}(b)=\{a\in A:f(a)=b\}$. Then $\{f^{-1}(b):b\in B\}$ 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)_{|\pi |}$, 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)_{|\pi |},$$

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)_{|\pi |}.$$

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 {E} [X^{n}]=\sum _{\pi }\mathbb {E} [(X)_{|\pi |}]$$

where $\mathbb {E}$ stands for expected value. But we shall show that all the quantities $\mathbb {E} [(X)_{k}]$ equal 1. It follows that

$$\mathbb {E} [X^{n}]=\sum _{\pi }1,$$

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

The quantity $\mathbb {E} [(X)_{k}]$ 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\geq 0$ with probability $1/(ej!)$. Thus

$$\displaystyle {\begin{aligned}\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{aligned}}$$