Dobiński's formula explained

In combinatorial mathematics, Dobiński's formula^[1] states that the

n th Bell number B _{n} , the number of partitions of a set of size n , equals

$$B\_n\; =\; \backslash sum\_^\backslash infty\; \backslash 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\; =\; \backslash left\backslash lceil\; \backslash sum\_^\backslash frac\backslash right\backslash rceil$$provided (K ^{n})/(K!) \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 Therefore ((K + j) ^{n})/((K + j)!) \le (K ^{n})/(K!) (1 {j!})/(\le) (1 {j!})/() for all j \ge 0 so that the tail \sum _{k\ge} (k ^{n})/(k!) = \sum _{j\ge} ((K + j) ^{n})/((K + j)!) is dominated by the series \sum _{j\ge} (1)/(j!) = e , which implies 0 < B _{n} - (1 {e}\sum)/(_{k=0}) ^{K-1} (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:$$\backslash sum\_^\backslash infty\; \backslash frac\; =\; \backslash sum\_^n\; \backslash binom\; B\_\; x^$$

and for

x =1 in this formula for Touchard polynomials

$$T\_n(x)\; =\; e^\backslash sum\_^\backslash infty\; \backslash frac$$

Proof

One proof^[2] relies on a formula for the generating function for Bell numbers,

$$e^\; =\; \backslash sum\_^\backslash infty\; \backslash frac\; x^n.$$

The power series for the exponential gives

$$e^\; =\; \backslash sum\_^\backslash infty\; \backslash frac\; =\; \backslash sum\_^\backslash infty\; \backslash frac\; \backslash sum\_^\backslash infty\; \backslash frac$$

so

$$e^\; =\; \backslash frac\; \backslash sum\_^\backslash infty\; \backslash frac\; \backslash sum\_^\backslash infty\; \backslash frac$$

The coefficient of

x ^{n} in this power series must be B _{n/n!} , so

$$B\_n\; =\; \backslash frac\; \backslash sum\_^\backslash infty\; \backslash frac.$$

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)\backslash 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

$$\backslash sum\_\backslash 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\; =\; \backslash sum\_\backslash pi\; (x)\_$$

.X with mean 1. The equation above implies that the n th moment of this random variable is

$$\backslash mathbb[X^n]\; =\; \backslash sum\_\backslash pi\; \backslash mathbb[(X)\_\{|\backslash pi|\}]$$

where

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

$$\backslash mathbb[X^n]\; =\; \backslash sum\_\backslash pi\; 1,$$

and this is just the number of partitions of the set

A .

The quantity

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 \ge 0 with probability 1 /(ej!) . Thus

Notes and References

1. G. . Dobiński. Summirung der Reihe style\sum (n ^{m})/(n!) für m = 1, 2, 3, 4, 5, …. Grunert's Archiv. 61. 1877. 333–336. German.
2. Book: Bender . Edward A. . Williamson . S. Gill . Theorem 11.3, Dobiński's formula . 0-486-44603-4 . 319–320 . Dover . Foundations of Combinatorics with Applications . 2006 .
3. .