Dobiński's formula

In combinatorial mathematics, Dobiński's formula^[1] states that the n-th Bell number B_n (i.e., 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 nth 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 nth 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^[2] 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.^[3] 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 ƒ be any function from a size-n set A into a size-x set B. For any b ∈ B, let ƒ⁻¹(b) = {a ∈ A : ƒ(a) = b}. Then {ƒ⁻¹(b) : b ∈ B} is a partition of A. Rota calls this partition the "kernel" of the function ƒ. 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 $π$ that is the kernel. The number of one-to-one functions from $π$ into B is (x)_{| $π$ |}, where | $π$ | is the number of parts in the partition $π$ . 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 $π$ running through the set of all partitions of A. On the other hand, the number of functions from A into B is clearly xⁿ. 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 nth moment of this random variable is

E(X^{n})=\sum _{\pi }E((X)_{|\pi |})

where E stands for expected value. But we shall show that all the quantities E((X)_k) equal 1. It follows that

E(X^{n})=\sum _{\pi }1,

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

The quantity E((X)_k) is called the kth 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}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}}

Notes and references

^ Dobiński, G. (1877). "Summirung der Reihe $\textstyle \sum {\frac {n^{m}}{n!}}$ für m = 1, 2, 3, 4, 5, …". Grunert's Archiv (in German). 61: 333–336.
^ Bender, Edward A.; Williamson, S. Gill (2006). "Theorem 11.3, Dobiński's formula". Foundations of Combinatorics with Applications (PDF). Dover. pp. 319–320. ISBN 0-486-44603-4.
^ Rota, Gian-Carlo (1964), "The number of partitions of a set" (PDF), American Mathematical Monthly, 71 (5): 498–504, doi:10.2307/2312585, JSTOR 2312585, MR 0161805.

[1] Dobiński, G. (1877). "Summirung der Reihe $\textstyle \sum {\frac {n^{m}}{n!}}$ für m = 1, 2, 3, 4, 5, …". Grunert's Archiv (in German). 61: 333–336.

[2] Bender, Edward A.; Williamson, S. Gill (2006). "Theorem 11.3, Dobiński's formula". Foundations of Combinatorics with Applications (PDF). Dover. pp. 319–320. ISBN 0-486-44603-4.

[3] Rota, Gian-Carlo (1964), "The number of partitions of a set" (PDF), American Mathematical Monthly, 71 (5): 498–504, doi:10.2307/2312585, JSTOR 2312585, MR 0161805.

[1]

[2]

[3]