Dobiński's formula

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=\lceil \frac{1}{e}\sum _{k=0}^{K-1}\frac{k^n}{k!}\rceil }$$ provided ${\displaystyle \frac{K^n}{K!}\le 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{array}{cc}{\displaystyle (\frac{K+j}{K}{)}^n}& \le (\frac{K+j}{K}{)}^K=(1+\frac{j}{K}{)}^K\\ & \le (1+\frac{j}{1})(1+\frac{j}{2})\dots (1+\frac{j}{K})\\ & =\frac{1+j}{1}\frac{2+j}{2}\dots \frac{K+j}{K}\\ & =\frac{(K+j)!}{K!j!}.\end{array}}$$ Therefore ${\displaystyle \frac{(K+j{)}^n}{(K+j)!}\le \frac{K^n}{K!}\frac{1}{j!}\le \frac{1}{j!}}$ for all ${\displaystyle j\ge 0}$ so that the tail ${\displaystyle \sum _{k\ge K}\frac{k^n}{k!}=\sum _{j\ge 0}\frac{(K+j{)}^n}{(K+j)!}}$ is dominated by the series ${\displaystyle \sum _{j\ge 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 \frac{1}{e}\sum _{k=x}^{\mathrm{\infty }}\frac{k^n}{(k-x)!}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{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}^{\mathrm{\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}^{\mathrm{\infty }}\frac{B_n}{n!}{x}^n.}$$

The power series for the exponential gives

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

so

$${\displaystyle e^{e^x-1}=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}\sum _{n=0}^{\mathrm{\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}^{\mathrm{\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}[X^n]=\sum _{\pi }\mathbb{E}[(X{)}_{|\pi |}]}$$

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

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

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

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

$${\displaystyle {\displaystyle \begin{array}{cc}\mathbb{E}[(X{)}_k]& =\sum _{j=0}^{\mathrm{\infty }}\frac{(j{)}_k}{ej!}\\ & =\frac{1}{e}\sum _{j=0}^{\mathrm{\infty }}\frac{j(j-1)\cdots (j-k+1)}{j(j-1)\cdots 1}\\ & =\frac{1}{e}\sum _{j=i}^{\mathrm{\infty }}\frac{1}{(j-i)!}=1.\end{array}}}$$