Calclute the probability? A random function $rand()$ return a integer between $1$ and $k$ with the probability $\frac{1}{k}$. After $n$ times we obtain a sequence $\{b_i\}_{i=1}^n$, where $1\leq b_i\leq k$.
Set $\mathbb{M}=\{b_1\}\cup\{b_2\}\cdots \cup\{b_n\}$.
I want to known the probability $\mathbb{M}\neq \{1, 2\cdots, k\}$.

Hint: Obviously $n<k$ is trivial. Thereafter, the question becomes equivalent to solving

What fraction of $n$-tuples with the digits $1,\ldots,k$ are in fact $n$-tuples formed from a strict subset of these numbers?

or a surjection-counting problem.
You can find a recursive solution by letting $p_{n,k}$ be the probability that a set of $n$ digits up to $k$ contains all distinct digits, and then considering the last digit of a sequence leading to $(n+1)$-tuples.
Edit: I should make clear that a recursive 'solution' essentially is the best you can do, which is why I called it that! The numbers don't have a closed form. (See e.g. https://mathoverflow.net/questions/27071/counting-sequences-a-recurrence-relation for a discussion, once you've worked out the recursive form yourself.)
