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}. $$

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)$.
