What is the probability that $m$ items drawn from $n$ distinct items contain all $n$ items?

Question

Suppose there are $n$ distinct items to be drawn with replacement for $m$ times, the probability of each item being drawn is assumed to be $\frac{1}{n}$. What is the probability $P(m)$ that $m$ items drawn from the $n$ items contain all $n$ items?

Apparently, if $m<n$

$$P(m)=0$$

For $m=n$,

$$P(m)=P(n)=\frac{n!}{n^n}$$

For $m>n$, I have no idea how to formulate the nominator.

$$P(m)=\frac{?}{n^m}$$

Answer 1

A lower bound can come from assessing the chance that a particular item has not been seen. On each draw you have $1-\frac 1n$ chance of not getting it, so on $m$ draws you have $(1-\frac 1n)^m$ chance of never seeing it. The chance you have not seen some item is then less than $n(1-\frac 1n)^m$. This is the expected number not to see. The chance of having not seen at least one is less than this because sometimes you will have missed more than one, but if the chance of missing one is small the chance of missing two is very small. We can use the fact that $(1-\frac 1n)^n \approx e^{-1}$ to write the expected number to miss as $$n\left(1-\frac 1n\right)^m=n\left(\left(1-\frac 1n\right)^n\right)^{\frac mn}\approx n\left(e^{-1}\right)^{\frac mn}=ne^{-\frac mn}$$ and the chance of missing at least one is less than this.

Answer 2

The numerator is $$n! \, S_2(m,n)$$ where $S_2(m,n)$ represents a Stirling number of the second kind, sometimes written ${m\brace n}$. There is no simple closed form for these, but there are a relatively simple recurrence, generating function and inclusion-exclusion alternating sum of combinations

For example if we call this $f(m,n)=n! \, S_2(m,n)$ then we get

$$S_2(m,n) = S_2(m-1,n-1)+n\,S_2(m-1,n) \\f(m,n) = n(f(m-1,n-1)+f(m-1,n))$$

both starting with $S_2(0,0)=f(0,0)=1$ and $S_2(0,n)=f(0,n)=0$ for $n \not = 0$

For small $m$ and $n$, the values of $f(m,n)=n! \, S_2(m,n)$ are

   n: 1    2    3    4    5
m
1     1    0    0    0    0
2     1    2    0    0    0
3     1    6    6    0    0
4     1   14   36   24    0
5     1   30  150  240  120

and it should be fairly clear that $150=3(14+36)$ and similar patterns with the other entries