Asymptotics of $e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot\frac1{n-k}$

Question

Letting $$ a_n = \sqrt{2\pi n}\cdot e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot{\frac1{n-k}}, $$ does anyone know of a simple asymptotic equivalent for $a_n$? Numerical experimentation suggests that $$ a_n \stackrel{?}\sim \tfrac12\log n. $$ If we get rid of the $\frac1{n-k}$, there is a simple answer, because $$ \lim_{n\to\infty} e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}=\frac12. $$ as shown here. Throwing in the factor $\frac1{n-k}$ seems to change the asymptotics entirely.

The context is that $a_n$ is result of applying Stirling's approximation to $\sum_{k=1}^n \frac{n_{(k)}}{kn^k},$ which is the expected number of "cycles" that a random function on a set of $n$ elements to itself has, where a cycle is a set of distinct numbers $\{x_1,x_2,\dots,x_k\}$ for which $f(x_i)=x_{i+1}$. If you replace "random function" with "random bijection," the expected number of cycles is about $\log n$, so if my guess is correct then random functions tend to have half as many cycles as permutations.

Answer 1

Here we follow exercise 5.2 from Asymptopia by Joel Spencer and show OP's assumption is correct.

The following is valid \begin{align*} \color{blue}{\sum_{k=1}^n\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}\sim \frac{1}{2}\ln n} \end{align*}

where $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ denotes the falling factorial.

A convenient approach is to split the index range of $k$ into three parts:

• a small range: $\qquad\quad k<\frac{\sqrt{n}}{\ln n}$

• a middle range: $\quad\quad \frac{\sqrt{n}}{\ln n} < k < \sqrt{n}\ln n$

• and a large range: $\ \quad k>\sqrt{n}\ln n$.

Small range: $k<\frac{\sqrt{n}}{\ln n}$

We write \begin{align*} \frac{n^{\underline{k}}}{n^k}=\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right) \end{align*} and consider the logarithm of the product. Since $$\ln(1-x)=-x+O(x^2)$$ when $x\rightarrow 0$ we obtain \begin{align*} \ln\left(\frac{n^{\underline{k}}}{n^k}\right)&=\sum_{j=1}^{k-1}\ln\left(1-\frac{j}{n}\right)\\ &\sim\sum_{j=1}^{k-1}-\frac{j}{n}\sim -\frac{k^2}{2n}=o(1) \end{align*} Thus we have \begin{align*} \frac{n^{\underline{k}}}{n^k}\sim 1\tag{1} \end{align*} We obtain from (1) \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\sim\sum_{k}\frac{1}{k}\sim\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim\ln\sqrt{n}-\ln\ln n\\ &\,\,\color{blue}{\sim\frac{1}{2}\ln n}\tag{2} \end{align*}

Medium range: $\frac{\sqrt{n}}{\ln n}<k<\sqrt{n}\ln n$

Since $\frac{n^{\underline{k}}}{n^k}\leq 1$ we obtain \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\leq \sum_{k}\frac{1}{k}\\ &\sim\ln\left(\sqrt{n}\ln n\right)-\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim \ln \sqrt{n}+\ln\ln n-\ln \sqrt{n}+\ln \ln n\\ &\,\,\color{blue}{\sim{2\ln \ln n}}\tag{3} \end{align*}

Large range: $k>\sqrt{n}\ln n$

Here we have $\frac{n^{\underline{k}}}{n^k}=o(1)$ and we obtain \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&=o(1)\sum_{k}\frac{1}{k}\\ &= o(1)\left(\ln n-\ln \left(\sqrt{n}\ln n\right)\right)\\ &\,\,\color{blue}{=o(\ln n)}\tag{4} \end{align*}

We see (2) provides the main contribution compared with (3) and (4) and the claim follows.

Answer 2

First, we reverse the order of summation, then we get ($k\to n-k)$: $$\sqrt{2\pi n}e^{-n}\sum^n_{k=1}\frac{n^n}{(n-k)!n^k}\frac1k$$ $$=\sqrt{2\pi n}e^{-n}n^n\frac1{n!}\sum^n_{k=1} \frac{n!}{(n-k)!n^k}\frac1k$$ $$=(1+o(?))\sum^n_{k=1} (1+o(?))\frac1k\sim H_n\sim \gamma +\ln n$$

I can’t get the $\frac12$ factor. By the way, the two asymptotic formulae used are well-known, but I don’t know the lower order effect.

Answer 3

Okay, so un-applying the Stirling's approximation, we want to find $$ \sum_{k=1}^n\frac{n_{(k)}}{n^k}\cdot \frac1k $$ where $n_{(k)}=\frac{n!}{(n-k)!}$. The general idea is that for small enough $k$,$\frac{n_{(k)}}{n^k}\approx 1$, while when $k$ is large, $\frac{n_{(k)}}{n^k}\approx 0$. We need to find the cutoff point where $\frac{n_{(k)}}{n^k}$ is moderate; then the summation is effectively the sum of $1/k$ up to the cutoff point.

Using Stirling's approximation, $$ \log \frac{n_{(k)}}{n^k} =n\log n-n-[(n-k)\log (n-k)-(n-k)]-k\log n+\dots\approx -\frac{k^2}{2n}-\frac{k^3}{6n^2}-\dots $$ Therefore, when $k\sim \sqrt{n}$, $ \frac{n_{(k)}}{n^k}\approx e^{-1/2}$, and that it drops off exponentially quickly after and before. Therefore, waving hands, $$ \sum_{k=1}^n\frac{n_{(k)}}{n^k}\cdot \frac1k\approx \sum_{k=1}^{\sqrt{n}}\frac1k\sim \tfrac12\log n. $$