Let $M$ be a positive integer, and let $X\_1, X\_2, \dots$ be i.i.d. r.v.'s having uniform distribution in the set $\{1, \dots, M\}$. For given $N$, let $Z\_N$ denote the number of *distinct* elements of the set $\{X\_1, \dots, X\_N\}$. 


Question: What is the distribution of $Z\_N$?


(In the end, I want to estimate how large $N$ has to be such that $Z\_N$ is close to $M$ with high probability. For example, how large does $N$ have to be such that $Z\_N > 0.9 M$ with probability at least $1/2$?)



What is this distribution?
[Birthday problem:](http://www.randomservices.org/random/urn/Birthday.html)


The probability density function of the number of distinct values $Z$ for population size $M$ and sample size $N$ is given by
$$P(Z = j) = \binom{M}{j} \sum\_{k=0}^j (-1)^k \binom{j}{k} \left(\frac{j - k}{M}\right)^N, \quad j \in \{1, 2, \ldots, \min(M,N)\}$$
$\qquad\qquad\qquad\qquad=\frac{M!}{M^N(M-j)!}S\_N^{(j)}$
([Stirling number of the second kind](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)) 


If you wish $Z$ to be close to $M$ with large probability you will need $N\gtrsim M\log M$.


