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}. $$
 A: 
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$.
A: The result below is not completely rigorous though I believe the argument (and especially the result) to be essential correct. 
Defining
$$f_n(k) = \frac{n!}{(n-k)!\,n^k}\left[1-\frac{k(k-1)}{n(n-1)}\right],$$ we transform the sum
$$S_n=\sum_{k=0}^n f_n(k) =\sum_{k=1}^{n} k [f_n(k-1) -f_n(k)] $$
using summation by parts.
Some straightforward calculation shows
$$g_n(k) = f_n(k-1)- f_n(k) = \frac{(k-1)(k+n)}{n(n-1)} \frac{n!}{ n^k (n-k)!}.$$
Because of the definition of $f_n(k) = P(X\ge x)$, we know that $g_n(k) \geq 0$ for $k\in[1,n]$.
We have that $$\frac{n!}{(n-k)!} \frac{1}{n^k}
= \frac{n}{n} \frac{n-1}{n} \cdots \frac{n-k+1}{n}
= \prod_{j=1}^{k-1} \left(1- \frac{j}{n}\right)$$
thus ($k\ll n$)
$$\log \left[\frac{n!}{(n-k)!} \frac{1}{n^k}\right]
= \log\left[ 1 -\sum_{j=1}^{k-1}\frac{j}{n}
+ \mathcal{O}\left(\frac{1}{n^2}\right)\right]
=  - \frac{k(k-1)}{2n} + \mathcal{O}\left(n^{-2}\right).$$
You can see that for large $n$ this function is maximal for $k=1$ with a broad peak of size $\simeq \sqrt{n}$. Nevertheless, because for large $n$, $\sqrt{n} \ll n$ the most weight of the sum is concentrated for small $k \lesssim \sqrt{n} \ll n$.
We can simplify
$$S_n =\sum_{k=1}^n k g_n(k) \sim \sum_{k=1}^n \frac{k (k-1)\overbrace{(k+n)}^{\approx n}}{\underbrace{n(n-1)}_{\approx n^2}}  e^{-k(k-1)/2n}
\sim -2 \partial_{\alpha}\sum_{k=1}^n e^{-\alpha k(k-1)/2n}\bigg|_{\alpha=1}.$$
Because the summand changes little from $k$ to $k+1$, the remaining sum can be approximated by the integral
$$  \sum_{k=1}^n e^{-\alpha k(k-1)/2n}
 \sim \int_0^n e^{-\alpha x^2/2n} 
 \sim \int_0^\infty e^{-\alpha x^2/2n} = \sqrt{\frac{\pi n}{2 \alpha}}.$$
Concluding, we have
$$S_n \sim -2 \partial_{\alpha} \sqrt{\frac{\pi n}{2 \alpha}}\,\bigg|_{\alpha=1}=  \sqrt{\frac{\pi n}{2}}.$$
Edit:
let us think about the errors made in each step:
1) in the expansion of
$$ \log \left[\frac{n!}{(n-k)!} \frac{1}{n^k}\right]$$
the next term is $\mathcal{O}(k^3/n^2) = \mathcal{O}(n^{-1/2})$ using the fact that $k\leq \sqrt{n}$.
2) We have $k+n = n [1+ \mathcal{O}(n^{-1/2})]$ and $n(n-1) = n^2[1+\mathcal{O}(n^{-1})]$.
3) The error in replacing the sum with the integral
$$ \sum_{k=1}^n e^{-\alpha k(k-1)/2n}
 \sim \int_1^{n-1} e^{-\alpha x(x-1)/2n} $$ is given by the maximum of $\partial_x e^{- x(x-1)/2n}$ times $\sqrt{n}$, i.e., the error is of the order $n^{-1/2}$.
4) Replacing $x(x-1)$ with $x^2$ introduces a relative error of $n^{-1/2}$.
5) Extending the upper bound of the integral to infinity contributes with an error $\propto e^{-n}$.
s) Summarizing, we expect $S_n = \sqrt{\pi n/2} + \mathcal{O}(1)$.
A: I get $$S = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2+4\epsilon}).$$

An asymptotic for the summand.
If $x \leq n^{1/2+\epsilon}$, then Stirling's approximation yields $$\log\left(\frac{n!}{(n-x)!n^x}\right) = - \frac{x^2}{2n} + \frac{x}{2n} - \frac{x^3}{6n^2} + O(n^{-1+4\epsilon}) \tag{1}.$$  To obtain this, we need to rewrite $\log(n-x)$ as $\log(n) \log(1-x/n)$, use the Maclaurin series $\log(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} + O(x^4)$ to get the dominant terms of $\log(1-x/n)$, and then crunch through a lot of algebra.  Most of the initially dominant terms cancel.
Thus, if $x \leq n^{1/2+\epsilon}$, $$\frac{n!}{(n-x)!n^x} = e^{-x^2/2n} \left(1 + \frac{x}{2n} - \frac{x^3}{6n^2} + O(n^{-1+4\epsilon})\right),$$
where we use the Maclaurin series $e^x = 1 + x + O(x^2)$ on all but the dominant term in Eq. (1).
Bounding the tail sum.
Since $\displaystyle \frac{n!}{(n-x)!n^x}$ is a decreasing function of $x$, if $x > n^{1/2+\epsilon}$, then $\displaystyle \frac{n!}{(n-x)!n^x} = O(e^{-x^2/2n}) = O(e^{-n^{2\epsilon}/2})$.  Thus for the tail sum we get $$\sum_{x > n^{1/2} + \epsilon} \frac{n!}{(n-x)!n^x} = O(ne^{-n^{2\epsilon}/2}),$$ which is exponentially small.  Therefore we can ignore it from here out for asymptotic purposes.
A useful asymptotic sum.
Problem 9.30 (p. 491) in Concrete Mathematics states that 
$$\sum_{k \geq 0} k^r e^{-r^2/n} = \frac{1}{2} n^{(r+1)/2} \Gamma\left(\frac{r+1}{2}\right) - \frac{B_{r+1}}{(r+1)!} + O(n^{-1}) \tag{2},$$ where $B_r$ is the $r$th Bernoulli number. (An outline of the proof is given in the answer section of the book.)
The asymptotic for the first, dominant term.
Equation (2) gives us
\begin{align*}
\sum_{x =0}^n \frac{n!}{(n-x)!n^x} = &\frac{1}{2} \sqrt{2n} \Gamma(1/2) + \frac{1}{2} + O(n^{-1}) + \frac{1}{2n}\left(\frac{1}{2} 2n \Gamma(1) + O(1)\right) \\
&- \frac{1}{6n^2} \left(\frac{1}{2} (2n)^2 \Gamma(2) + O(1)\right) + O(n^{-1/2 + 4 \epsilon}) \\
= & \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2 + 4 \epsilon}).
\end{align*}
An asymptotic for the second term.
For the second term $\displaystyle \sum_{x =0}^n \frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)},$ a similar analysis holds.  We can ignore the tail sum when $x > n^{1/2+\epsilon}$ because it is even smaller than the tail sum in the first term.  If  $x \leq n^{1/2+\epsilon}$, we get $$\frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)} = e^{-x^2/2n} O(n^{-1+\epsilon}).$$
Therefore, by Equation (2),
$$\sum_{x=0}^n \frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)} = O(n^{-1/2+\epsilon}).$$
Finally.
All together, then, 
$$S = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2+4\epsilon}).$$

Additional comments.
Incidentally, the sum $\displaystyle \sum_{x=0}^n \frac{n!}{(n-x)!n^x}$ is one that appears in several places in Knuth's work, and in The Art of Computer Programming, Vol. I, p. 120, he gives the asymptotic (in his notation) $$\sum_{x=0}^n \frac{n!}{(n-x)!n^x} = 1 + Q(n) = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + \frac{1}{12}\sqrt{\frac{\pi}{2n}} - \frac{4}{135n} + \frac{1}{288} \sqrt{\frac{\pi}{2n^3}} + O(n^{-2}).$$
