<s>[INST] 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}. $$
 [/INST] 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}).$$
</s>