# Closed form expression for the series $\sum_{k=0}^\infty \frac{k^j}{k!}$ in terms of $j$

For my research I need to compute "approximate" moment generating function (we approximate exponential with the first $$D$$ elements of its Taylor series) of the number of fixed points of a permutation which involves the following sum:

$$$$\sum_{k=0}^\infty \frac{k^j}{k!}$$$$

in terms of $$j$$. I am pretty sure this grows exponential in $$j$$ but I am interested in finding the exact exponent. With some elementary calculations I get the following recurrence relation

$$$$\sum_{k=0}^\infty \frac{k^j}{k!} = \sum_{m=0}^{j-1}{j-1\choose m} \sum_{k=0}^\infty \frac{k^{j-1-m}}{k!}$$$$

but I couldn't proceed further.

• You infinite series is equal to $e$ times the $j^{th}$ Bell number, for which there is no closed form. There are some asymptotic estimates in the Wikipedia link. – Mike Earnest Feb 14 '19 at 17:33
• @Mikeearnest Hi Mike. The Stirling Numbers of the Second Kind can be expressed in closed form (in terns of a finite summation). Inasmuch as The Bell Numbers are a finite sum over the Belk Numbers, the Bell Numbers do have a closed form in terms of a finite sum over two indices. – Mark Viola Feb 15 '19 at 3:28
• @MarkViola You’ve got a point! – Mike Earnest Feb 15 '19 at 4:42
• Cf Dobiński's formula en.wikipedia.org/wiki/Dobi%C5%84ski%27s_formula – leonbloy Feb 16 '19 at 19:37

This will be $$\lim_{x\to1}\left(x\frac d{dx}\right)^j e^x=\lim_{x\to1}e^x\sum_{k=1}^j{j\brace k}x^k= B_je,$$ where $${j\brace k}$$ are the Stirling numbers of the second kind and $$B_j=\sum_{k=1}^j{j\brace k}$$ are the Bell (or exponential) numbers.

• thanks, this exactly matches what I observed numerically as well. – E Onaran Feb 14 '19 at 17:37

Note that we have

$$\sum_{k=0}^\infty \frac{k^j}{k!}=\left(\left.\left(x\frac{d}{dx}\right)^j\{e^x\}\right)\right|_{x=1}$$

LEMMA:

In general, if $$f(x)$$ is $$n$$ times differentiable, then we have

$$\left(x\frac{d}{dx}\right)^j\{f(x)\}=\sum_{k=1}^j \begin{Bmatrix} j \\ k \end{Bmatrix}x^k\frac{d^k\,f(x)}{dx^k}$$

where $$\begin{Bmatrix} j \\ k \end{Bmatrix}=\frac1{k!}\sum_{\ell=0}^k (-1)^{k-\ell}\binom{k}{\ell}\,\ell^j$$ are the Stirling Numbers of the Second Kind.

PROOF:

We assume that we can write $$\left(x\frac{d}{dx}\right)^j\{f(x)\}$$ as

$$\left(x\frac{d}{dx}\right)^j\{f(x)\}=\sum_{k=1}^j s(j,k)x^k\frac{d^kf(x)}{dx^k}$$

for coefficients $$s(j,k)$$, where $$s(j,1)=1$$. As an inductive base case, take $$j=1$$. Then, we have

\begin{align} \left(x\frac{d}{dx}\right)^{j+1}\{f(x)\}&=\left(x\frac{d}{dx}\right)\sum_{k=1}^j s(j,k)x^k\frac{d^kf(x)}{dx^k}\\\\ &=\sum_{k=1}^j s(j,k)\left(x^{k+1}\frac{d^{k+1}f(x)}{dx^{k+1}}+kx^k \frac{d^{k}f(x)}{dx^{k}}\right)\\\\ &=\sum_{k=1}^{j+1} \left(s(j,k-1)+k s(j,k)\right)x^{k}\frac{d^{k}f(x)}{dx^{k}}\\\\ &=\sum_{k=1}^{j+1} s(j+1,k)x^{k}\frac{d^{k}f(x)}{dx^{k}} \end{align}

where $$s(j,k)$$ satisfies the relationship

$$s(j+1,k)=s(j,k-1)+ks(j,k)$$

along with the conditions $$s(j,1)=s(j,j)=1$$ and $$s(j,k)=0$$ for $$k>j$$. Noting that $$S(j,k)$$ and $$\begin{Bmatrix} j \\ k \end{Bmatrix}$$ satisfy the same recurrence relationship and initial conditions, the proof is complete.

If $$f(x)=e^x$$ then

\begin{align} \left.\left(\left(x\frac{d}{dx}\right)^j\{e^x\}\right)\right|_{x=1}&=e\sum_{k=1}^j \begin{Bmatrix}j\\k\end{Bmatrix}\\\\ &=eB_j \end{align}

where $$B_j=\sum_{k=1}^j \begin{Bmatrix}j\\k\end{Bmatrix}$$ are the Bell Numbers.

Alternatively, we could use the Faà_di_Bruno Formula to calculate the term $$\left(x\frac{d}{dx}\right)^j \{e^x\}$$. To do this, we first make the substitution $$x=e^y$$.

Then, using the Bell Polynomials, $$B_{n,k}(x_1,x_2,\dots,x_{n-k+1})$$, we have

\begin{align} \left(\left.\left(x\frac{d}{dx}\right)^j\{e^x\}\right)\right|_{x=1}&=\left(\left.\left(\frac{d}{dy}\right)^j\{e^{e^y}\}\right)\right|_{y=0}\\\\ &=\sum_{k=1}^j \left(\left.\left(e^{e^y}\right)^{(k)}B_{j,k}((e^y)^{(1)},(e^y)^{(2)},\dots,(e^y)^{(j-k+1)})\right)\right|_{y=0}\\\\ &=e\sum_{k=1}^j B_{j,k}(1,1\dots, 1)\tag1\\\\ &=B_j e\tag2 \end{align}

In going from $$(1)$$ to $$(2)$$ we used the relationship between the Bell Numbers, $$B_n$$, and the sum over the Stirling Numbers of the second kind:

$$B_n=\sum_{k=1}^n B_{n,k}(1,1,\dots,1)=\sum_{k=1}^n {n \brace k}$$

As a side note, it is interesting to observe that

$$\sum_{j=0}^\infty\frac1{j!} \left(\sum_{k=0}^\infty\frac{k^j}{k!}\right)=e^e$$

• Please let me know how I can improve my answer. I really want to give you the best answer I can. – Mark Viola Feb 25 '19 at 4:30
• And feel free to up vote answers you find useful and accept an answer as you see fit. ;-) – Mark Viola Feb 25 '19 at 4:30

@user has already answered the question, and @MikeEarnest has noted how little we know about Bell numbers, but I'll chime in with an explanation of where these numbers come from.

In how many ways can we partition a size-$$n+1$$ set? Call the answer $$B_n$$. Fix one element $$a$$ and count the number of solutions in which all but $$k$$ of the remaining $$n$$ objects are grouped with $$a$$; we choose those $$k$$ in one of $$\binom{n}{k}$$ ways, so $$B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_k$$.

It's not hard to show this implies the exponential generating function $$B(x):=\sum_n\frac{B_nx^n}{n!}$$ satisfies $$B(0)=1,\,B^\prime(x)=B(x)\exp x$$, so $$B(x)=\exp(\exp x-1)$$. If we write $$B^{(n)}(x)=p_n(\exp x)B(x)$$ the polynomials satisfy $$p_0=1,\,p_{n+1}(x)=x(p_n(x)+p_n^\prime(x))$$, the same recursion relation as the $$p_n$$ we can define from $$\left(x\frac{d}{dx}\right)^n\exp x=p_n(x)\exp x$$. This implies these definitions are equivalent, and $$p_n(1)=\frac{B^{(n)}(0)}{B(0)}=B_n$$, as already stated.