Coupon Collecting Problem

Question

There are $c$ different types of coupon, and each coupon obtained is equally likely to be any one of the $c$ types. Find the probability that the first $n$ coupons which you collect do not form a complete set.

It is clear that the probability of getting a new coupon on the first draw is 1, and that the probability of getting a new coupon on the second is $(c-1)/c$, or $(c-i)/c$ for the $i$-th new coupon after the initial draw (or $(c-(i-1))=c$ if you include the first draw as a new $i$-th coupon) I don't know where to go from here.

Answer 1

Here is another answer: The probability that none of the n coupons are of type 1 is ${(\frac{c-1}{c})}^n$. Likewise for all the other types. The sum of these is an overcount of the total probability. We can use the inclusion exclusion principle. Subtract the probability that two types are excluded, then add the probability that three types are, and so forth until all possibilities are covered.

Answer 2

Just because you accepted a wrong answer.

There are in total $c^n$ possible collections among the first $n$ collected coupons. Among them there are $$ c!{n \brace c} $$ combinations with each coupon collected at least once. Here ${n \brace c}$ is the Stirling number of second kind.

Therefore the probability in question is: $$ 1-\frac{c!}{c^n}{n \brace c}. $$