Suppose we have a random process defined on set with $S=\{1, 2, \ldots, N\}$, where at each time step $1 \leq t \leq M$, you select a random variable $ X_t \in S$ with equal probability. I am interested in distribution of the number of unique elements $u$ that have been selected at least once after $M$ trials, let's call this $f(u; N, M)$.
For example, $f(u=6; N=10, M=15)$ would give the probability that 6 out of $N=10$ distinct variables have been selected, after $M=15$ trials. We see that the domain of $u$ is restricted to $1 \leq u \leq \min(N, M)$.
What I have tried so far: Let $(x_1, \ldots, x_N)$ be the number of times each of the variables are selected, subject to the constraint $\sum_{i=1}^{N} x_i = M$. The statistics of $f(u)$ seems to be obtainable from the multinomial distribution which with equal probabilities for all outcomes, \begin{equation} f_M(x_1, \ldots, x_{N}) = \frac{1}{N^M} \binom{M}{x_1, \ldots, x_{N}}. \end{equation} Here, the multinomial coefficient $\binom{M}{x_1, \ldots, x_{N}}$ gives the number of realizations that leads to the outcome $(x_1, \ldots, x_N)$ and $N^M$ is the total number of realizations.
Now we want to restrict ourselves to $(x_1, \ldots, x_{N})$ where only $u$ of the $x_i$ are larger than zero and the rest is zero. If we order these non-zero values such that $(x_1 >0, \ldots, x_u >0, x_{u+1}=0, \ldots, x_{N} =0)$, then the probability in this ordering equals \begin{equation} \sum_{x_1 + \ldots + x_u = M} f_M(x_1, \ldots, x_u, x_{u+1}=0, \ldots, x_{u}=0) = \sum_{x_1 + \ldots + x_u = M} \frac{1}{N^M} \binom{M}{x_1, \ldots, x_{N}} = \left(\frac{u}{N}\right)^M. \end{equation} Now in general the $u$ non-zero outcomes do not have be the first $u$ outcomes, but can be any of the $\binom{N}{u}$ ways of selecting these variables. Hence my final expression is \begin{equation} f(u; N, M) = \binom{N}{u} \left(\frac{u}{N}\right)^M. \end{equation} However, it is easily verified that this is incorrect for small $N$ and $M$ because the $\sum_{u=1}^{ \min(N,M) } f(u) \neq 1$. What am I missing here?
Notice that when you do $u^M$ you are assuming that you are taking any possibility of assignment in those $u$ outcomes. What if in all of those you choose the same element? The number of chosen ones would be $1$ instead of $u.$ So you need is the number of surjective functions from $M$ to $u,$ this is given by $u!{M\brace u},$ where ${a \brace b}$ denotes the Stirling numbers of second kind (number of ways to partition $[a]$ into $b$ non empty blocks). so $$f(u,N,M)=\binom{N}{u}\frac{{M\brace u}u!}{N^M}.$$