Let $X, Y$ be finite sets with $|Y|= n$ and $f: X \to Y$ such that all preimages $f^{-1}(y),\,y\in Y$ have the same cardinality.
A pair $x_1 \neq x_2$ in $X$ such that $f(x_1)=f(x_2)$ is called a collision. The literature on the birthday attack states (cf. wikipedia.org/wiki/Birthday_attack). :
(S) If $f$ is evaluated at $\sqrt{2log(2)}\cdot \sqrt{n}$ elements than the probability of observing a collision is 1/2 for $n$ large.
The argument that is usually given is simple: Computing $y=f(x)$ for randomly chosen $x$ is the same as choosing $y \in Y$ randomly. This is equivalent to drawing balls from an urn containing $n$ labelled balls with replacement. So the problem is solved by the birthday problem.
But actually, I think this argument isn't very convincing. For, suppose $f$ is bijective. Then there will be no collision at all and the statement is wrong.
In some sources (e.g. www.pumj.org/docs/Issue1/Article_3.pdf) $|X| \gg |Y|$ is required. But then, in a proof, this property has to be used seriously – just referring to the birthday problem for $Y$ isn't sufficient.
Question: Is there a precise proof of the statement (S) in the literature or can someone sketch such a proof?
Scatch of the proof for (S): As explained by Robert Israel in a comment, the probability for a collision after evaluating $k$ elements from $X$ is $$p = 1 - \dfrac{{n \choose k} m^k}{{nm \choose k}}\tag{1}$$ Let $q(n) := (n-k+1)\cdots n / n^k$. By the standard approximation $q(n)\sim e^{\frac{-k(k-1)}{2n}}$ (e.g. Is there a precise error bound for the approximation used in the description of the Birthday Paradox distribution?) we find for $p' := 1-p$ and $n$ large: $$p' = \frac{q(n)n^km^k}{q(nm)(nm)^k} \sim \frac{e^{\frac{-k(k-1)}{2n}}}{e^{\frac{-k(k-1)}{2nm}}}=e^{(\frac{1}{m}-1)\frac{k(k-1)}{2n}}$$ Taking $k=\sqrt{n}$ yields $p' \sim e^{\frac{1}{2}\cdot(\frac{1}{m}-1)}\sim e^{-\frac{1}{2}}$ for $m$ large. This proves (S).