Asymptotics of $e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot\frac1{n-k}$ 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.
 A: 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.

A: 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.
$$
A: 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.
