Ttdfjt

I want to compute the expectation to get the first match which is not difficult (See section 5.6, "average number of people").

My question is how to prove the Ramanujan's formula given there,

$$ Q(M)=sum_k=1^M fracM!(M-k)! M^ksimsqrtfracpi M2-frac13+frac112sqrtfracpi2M-frac4135M+cdots$$

Any good reference available?

A crystal clear derivation using only elementary calculus is given by Donald Knuth on page 116-121 of The Art of Computer Programming (volume 1).

I reproduce the first and the last paragraphs of Knuth's exposition:

We have $$Q(n)=sum_k=0^n-1 (1-1/n)(1-2/n)ldots(1-k/n).$$
Write $1-x/n=e^-x/n-x^2/(2n^2)-ldots$, then
$$Q(n)=sum_k=0^n-1 expleft(-frack(k+1)2n-frack(k+1)(2k+1)12n^2-ldotsright).$$
If $kgeqslant n^1/2+0.00001$, the corresponding summands are super-polynomially small and do not rely on the asymptotics. For $k<n^1/2+0.00001$ , the first few summands in the expansion define it with good accuracy ($n$ to any prescribed negative power) and we get a standard problem of the asymptotics of $sum_k g(k)$ for $g(k)=exp(-frack(k+1)2n-frack(k+1)(2k+1)12n^2)$, say. It is obtained by Euler–Maclaurin. The main term comes from the approximation of $sum_k exp(-k^2/(2n))$ by $int_0^infty exp(-x^2/(2n))dx=sqrtpi n/2$.