Expected number of drawings to find collision Consider a group $G$ consisting of $n$ distinct elements. Suppose we draw random elements of $G$ (one by one, replacing each element every time) until we draw an element that was drawn before (we say there was a match or collision).
I am in front of the following statement

If elements are drawn at random from $G$ then the expected number of draws before a collision occurs is $\sqrt{πn/2}$

(I suppose it is implicit that all elements of $G$ have the same probability of being drawn).
I tried and failed to understand this statement in terms of expectation of the variable that counts the number of draws before the collision occurs. Any ideas?
 A: The probability that the first collision occurs at draw number $k+1$ is the probability that the first $k$ draws are distinct and the $k+1$'th is equal to one of the first $k$.  The number of outcomes in this event is $\dfrac{n!}{(n-k)!} k$, so its probability is $$P_k = \dfrac{n! k}{(n-k)! n^{k+1}}$$
The expected number of draws before a collision occurs (before, so not counting the draw on which the collision occurs) is then
$$ \sum_{k=0}^n \dfrac{n!\; k^2}{(n-k)!\; n^{k+1}} $$ 
There is no nice closed form for this sum (unless you like $\mbox{$_3$F$_1$}$ hypergeometrics), but of course for any particular $n$ you can compute it exactly: it will be a rational number, so certainly not $\sqrt{\pi n/2}$.  The claim is that it is asymptotic to 
$\sqrt{\pi n/2}$ as $n \to \infty$.
EDIT: Let $X$ be the number of draws before the first collision.  Then $E[X] = \sum_{k=1}^n P(X \ge k)$ where for $1 \le k \le n$, 
$$P(X \ge k) = \dfrac{n!}{(n-k)! n^k} = \prod_{j=0}^k \left(1 - \dfrac{j}{n}\right)$$
I won't bother with the details, but this can be approximated by
$e^{-k^2/(2n)}$.  Then
$$ E[X] \approx \sum_{k=1}^n e^{-k^2/(2n)} \approx \int_0^n e^{-t^2/(2n)}\; dt = \sqrt{n}\int_0^{\sqrt{n}} e^{-s^2/2}\; ds \approx \sqrt{\pi n/2} $$
because $\int_0^\infty e^{-s^2/2}\; ds = \sqrt{\pi/2}$.
