There are $k$ varieties of objects, each variety consisting of the same number of objects. These objects are drawn one at a time and replaced before the next drawing. What is the probability that $n$ and no fewer drawings will be required to produce objects of all varieties?
The back of my book says the answer is $\dfrac{ \sum (-1)^r~~~ ^{k-1}C_r(k-r-1)^{n-1}} { k^{n-1} }$
Attempt: It is evident that $n > k.$ The problem wants that $n$ and no fewer drawings will be required to produce objects of all varieties.
Thus, there exists at least one variety $V_i, ~1 \le i \le k$ such that all objects from $V_i$ are drawn together in the end only.
I am not sure how to proceed ahead with the inclusion-exclusion principle. Could someone please give a direction. Thanks a lot for your help!
@eyeballfrog said $n$'th draw must be the last varieties. Now it like in $n-1$ draw we have $k-1$ varieties without restriction of "And No Fewer Drawing"!
Now drawing $k-1$ varieties is equivalent to skip drawing $1$ variety. If $A_i$ is to skip $i$'th variety, we should compute $|\cup_i A_i|$. By Inclusion-Exclusion Principle we get the nominator of that formula.
Notice $^{k-1}C_r$ is the number of choices of $r$ varieties (to be skipped) from $k-1$ ones.
And $(k-r-1)^{n-1}$ is the number of drawings don't draw those $r$ skipped varieties.