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\}$.
 A: The probability that $j$ of the $k$ numbers is excluded is $(1-j/k)^n$ and there are $\binom{k}{j}$ ways to choose those $j$ to be excluded. The inclusion-exclusion principle says that the probability that at least one of the $k$ numbers is excluded is
$$
\sum_{j=1}^k(-1)^{j-1}\binom{k}{j}\left(1-\frac{j}{k}\right)^n
$$
A: 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.)
A: Principle of inclusion and exclusion? That will do, I think, because probability that you didn't get $j$, $1\leq j \leq k $, $\quad$ is $\quad$ $( \frac{k-1}{k} )^n$ and so on ...
