4
$\begingroup$

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:

\begin{equation}\sum_{k=0}^\infty \frac{k^j}{k!} \end{equation}

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

\begin{equation}\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!} \end{equation}

but I couldn't proceed further.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Mike Earnest Feb 14 '19 at 17:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Mark Viola Feb 15 '19 at 3:28
  • 1
    $\begingroup$ @MarkViola You’ve got a point! $\endgroup$ – Mike Earnest Feb 15 '19 at 4:42
  • $\begingroup$ Cf Dobiński's formula en.wikipedia.org/wiki/Dobi%C5%84ski%27s_formula $\endgroup$ – leonbloy Feb 16 '19 at 19:37
5
$\begingroup$

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.

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

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$$

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

@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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.