How to calculate $\sum \limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)$ What are the asymptotics of the following sum as $n$ goes to infinity?
$$
S =\sum\limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)
$$
The sum comes from CDF related to sampling with replacement. Consider a random process where integers are sampled uniformly with replacement from $\{1...n\}$.  Let $X$ be a random variable that represents the number of samples until either a duplicate is found or both the values $1$ and $2$ have been found.  So if the samples where $1,6,3,5,1$ then $X=5$ and if it was $1,6,3,2$ then $X=4$. This sum is therefore $\mathbb{E}(X)$.
We therefore know that $S = \mathbb{E}(X) \leq \text{mean time to find a duplicate} \sim \sqrt{\frac{\pi}{2} n}$.
Taking the first part of the sum, 
$$\sum_{x=0}^{n} \frac{n!}{(n-x)!\,n^x} = \left(\frac{e}{n} \right)^n \Gamma(n+1,n) \sim \left(\frac{e}{n} \right)^n  \frac{n!}{2} \sim  \sqrt{\frac{\pi}{2} n}. $$


Let $N_n$ denote a Poisson random variable with parameter $n$, then
  $$
S_n=\frac{n-2}{n-1}n!\left(\frac{\mathrm e}n\right)^n\mathbb P(N_n\leqslant n)+\frac2{n-1}.
$$
  As a consequence, $\lim\limits_{n\to\infty}S_n/\sqrt{n}=\sqrt{\pi/2}$.

To show this (for a shorter proof, see the end of this post), first rewrite each parenthesis in $S_n$ as
$$
1-\frac{x(x-1)}{n(n-1)}=\frac2n(n-x)-\frac1{n(n-1)}(n-x)(n-x-1).
$$
Thus, $\displaystyle S_n=n!\,(2U_n-V_n)$ with
$$
U_n=\frac1n\sum_{x=0}^n\frac1{n^x}\frac{n-x}{(n-x)!}=\sum_{y=1}^n\frac1{n^y}\frac1{(n-y)!}=n^{-n}\sum_{x=0}^{n-1}\frac{n^x}{x!},
$$
and
$$
V_n=\frac1{n(n-1)}\sum_{x=0}^n\frac1{n^x}\frac{(n-x)(n-x-1)}{(n-x)!}=\frac{n}{n-1}\sum_{z=2}^n\frac1{n^z}\frac1{(n-z)!},
$$
that is,
$$
V_n=\frac{n}{n-1}n^{-n}\sum_{x=0}^{n-2}\frac{n^x}{x!}.
$$
Introducing
$$
W_n=n^{-n}\sum_{x=0}^n\frac{n^x}{x!},
$$
this can be rewritten as
$$
U_n=W_n-\frac1{n!},\qquad V_n=\frac{n}{n-1}\,\left(W_n-\frac2{n!}\right),
$$
hence
$$
S_n=n!\left(2\left(W_n-\frac1{n!}\right)-\frac{n}{n-1}\left(W_n-\frac2{n!}\right)\right)=n!\frac{n-2}{n-1}W_n+\frac2{n-1}.
$$
The proof is complete since
$$
W_n=n^{-n}\mathrm e^n\cdot\mathrm e^{-n}\sum_{x=0}^n\frac{n^x}{x!}=n^{-n}\mathrm e^n\cdot\mathbb P(N_n\leqslant n).
$$
Edit: Using the distribution of $N_n$ and the change of variable $x\to n-x$, one gets directly
$$
S_n=n!\left(\frac{\mathrm e}n\right)^n\left(\mathbb P(N_n\leqslant n)-\mathbb E(u_n(N_n))\right),
$$
with
$$
u_n(t)=\frac{(n-t)(n-t-1)}{n(n-1)}\,\mathbf 1_{t\leqslant n}.
$$
Since $N_n/n\to1$ almost surely when $n\to\infty$, $u_n(N_n)\to0$ almost surely. Since $u_n\leqslant1$ uniformly, $\mathbb E(u_n(N_n))\to0$. On the other hand, by the central limit theorem, $\mathbb P(N_n\leqslant n)\to\frac12$, hence Stirling's equivalent applied to the prefactor of $S_n$ yields the equivalent of $S_n$.
Edit-edit: By Berry-Esseen theorem, $\mathbb P(N_n\leqslant n)=\frac12+O(\frac1{\sqrt{n}})$. By the central limit theorem, $\mathbb E(u_n(N_n))=O(\frac1n)$. By Stirling's approximation, $n!\left(\frac{\mathrm e}n\right)^n=\sqrt{2\pi n}+O(\frac1{\sqrt{n}})$. Hence, $S_n=\sqrt{\pi n/2}+T_n+o(1)$ where $\limsup\limits_{n\to\infty}|T_n|\leqslant 2C\sqrt{2\pi}(1+\mathrm e^{-1})$ for any constant $C$ making Berry-Esseen upper bound true, hence $\limsup\limits_{n\to\infty}|T_n|\lt3.3$.
