Find the probability of finding $r$ distinct numbers when picked from a set of $r$ distinct elements, $n$ times. You have a set containing $r$ distinct elements say $1,2,...,r$. You pick $n (n>r)$ samples from this set with replacement (equal probability of picking any number). What would be the probability of finding $r$ distinct elements when $n$ samples are drawn?
Note: Sequence of numbers matters.
I have worked out the following:
For $r=3$, I got the following formula for finding out the number of different configurations where we get $r$ distinct elements.
$N(n,r) = \sum_{i=1}^{n-r+1} \sum_{j=i+1}^{n-r+2} r^i * (r-1)^{j-i} * (r-2)^{n-j}$
Similarly, for $r=4$,
$N(n,r) = \sum_{i=1}^{n-r+1} \sum_{j=i+1}^{n-r+2} \sum_{k=j+1}^{n-r+3} r^i * (r-1)^{j-i} * (r-2)^{k-j} * (r-3)^{n-k}$
The probability of the event would be $\frac{N(n,r)}{r^n}$.
As $r$ increases, I don't think the formula for $N(n,r)$ is appreciable. There must be a better (elegant) way to solve this. Any leads are appreciated!
Thanks in advance!
PS: This might be asked before as well. I tried my best to see if there are similar questions, but couldn't find one. I would appreciate if anyone could point me to one if it exists!
 A: This is an inclusion-exclusion calculation.  The chance that a specific number is missing is $\left(\frac {r-1}r\right)^n$.  The chance that some number is missing would be $r$ times this, but we double count the cases where two numbers are missing, so need to add them back in once.  Then we removed the ones with three numbers missing three times and added them back in three times, so need to subtract them once and so on.  You get
$$1-r\left(\frac {r-1}r\right)^n+{r \choose 2}\left(\frac {r-2}r\right)^n-{r \choose 3}\left(\frac {r-3}r\right)^n+\ldots$$
A: The Stirling number of the second kind, $\big\{ {n\atop r} \big\}$, is defined to be the number of ways to partition a set of $n$ elements into $r$ nonempty (unlabeled) subsets. It's not hard to see that your counting problem is asking about the same question for labeled subsets, the answer for which is simply $r! \big\{ {n\atop r} \big\}$. Therefore the probability in question is $\frac{r!}{r^n} \big\{ {n\atop r} \big\}$. This is consistent with the formula given in Ross Millikan's answer.
