Misplaced Pages

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

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

where ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ equals the ${\displaystyle 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 ${\displaystyle n+o(n)}$ terms, taking into account the information that ${\displaystyle B_{n}}$ is an integer. Precisely one has, for any integer ${\displaystyle K>1}$ $${\displaystyle B_{n}=\left\lceil {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right\rceil }$$ provided ${\displaystyle {\frac {K^{n}}{K!}}\leq 1}$ (a condition that of course implies ${\displaystyle K>n}$, but that is satisfied by some ${\displaystyle K}$ of size ${\displaystyle n+o(n)}$). Indeed, since ${\displaystyle K>n}$, one has $${\displaystyle {\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 ${\displaystyle {\frac {(K+j)^{n}}{(K+j)!}}\leq {\frac {K^{n}}{K!}}{\frac {1}{j!}}\leq {\frac {1}{j!}}}$ for all ${\displaystyle j\geq 0}$ so that the tail ${\displaystyle \sum _{k\geq K}{\frac {k^{n}}{k!}}=\sum _{j\geq 0}{\frac {(K+j)^{n}}{(K+j)!}}}$ is dominated by the series ${\displaystyle \sum _{j\geq 0}{\frac {1}{j!}}=e}$, which implies ${\displaystyle 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 ${\displaystyle x=0}$, of the more general relation:$${\displaystyle {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 ${\displaystyle x=1}$ in this formula for Touchard polynomials

$${\displaystyle 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,

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

The power series for the exponential gives

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

$${\displaystyle 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 ${\displaystyle x^{n}}$ in this power series must be ${\displaystyle B_{n}/n!}$, so

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

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

$${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1)}$$

Let ${\displaystyle f}$ be any function from a size-${\displaystyle n}$ set ${\displaystyle A}$ into a size-${\displaystyle x}$ set ${\displaystyle B}$. For any ${\displaystyle b\in B}$, let ${\displaystyle f^{-1}(b)=\{a\in A:f(a)=b\}}$. Then ${\displaystyle \{f^{-1}(b):b\in B\}}$ is a partition of ${\displaystyle A}$. Rota calls this partition the "kernel" of the function ${\displaystyle f}$. Any function from ${\displaystyle A}$ into ${\displaystyle B}$ factors into

• one function that maps a member of ${\displaystyle 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 ${\displaystyle B}$.

The first of these two factors is completely determined by the partition ${\displaystyle \pi }$ that is the kernel. The number of one-to-one functions from ${\displaystyle \pi }$ into ${\displaystyle B}$ is ${\displaystyle (x)_{|\pi |}}$, where ${\displaystyle |\pi |}$ is the number of parts in the partition ${\displaystyle \pi }$. Thus the total number of functions from a size-${\displaystyle n}$ set ${\displaystyle A}$ into a size-${\displaystyle x}$ set ${\displaystyle B}$ is

$${\displaystyle \sum _{\pi }(x)_{|\pi |},}$$

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

$${\displaystyle x^{n}=\sum _{\pi }(x)_{|\pi |}.}$$

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

$${\displaystyle \mathbb {E} =\sum _{\pi }\mathbb {E} }$$

where ${\displaystyle \mathbb {E} }$ stands for expected value. But we shall show that all the quantities ${\displaystyle \mathbb {E} }$ equal 1. It follows that

$${\displaystyle \mathbb {E} =\sum _{\pi }1,}$$

and this is just the number of partitions of the set ${\displaystyle A}$.

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

$${\displaystyle \displaystyle {\begin{aligned}\mathbb {E} &=\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

1. Dobiński, G. (1877). "Summirung der Reihe ${\displaystyle \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.

• Combinatorics
• Poisson point processes