A trading card series has 200 different cards in it, which are sold in 5-card packages.

Each package has a random sampling of the cards (assume that any card of the 200 has an equal chance of being in a package).

On the average, how many packages will need to be bought to collect the complete series if...

A: all the cards in a package will always be different

B: a package can have repeats

The ORwise probabilities are easy enough to compute. The probability that one will have achieved say both cards 1 and 2 out of a set of 200 is one minus the probability that one will not have achieved either, and that latter probability is ((200-2)/200)^n, where n is the number of cards that have been drawn, as each card drawn independently must have been one of the other 198 cards out of the 200, to satisfy the criteria of the probability. Of course the pairs are equally probable, and there are C(200,2) pairs, so the combinations becomes part of the formula rather than taking each pair (triple, etc.) separately. (C(n,r) = n!/(r!(n-r)!))

The result is that the formula for having completed the set of 200 cards after n cards have been drawn (n = 5p, where p is the number of packets that have been drawn) is

∑{i=1 to 200} (1-((200-i)/200)^n) C(200,i) (-1)^(i-1)

where the raising of –1 to the i-1 power is to get the appropriate sign for the set of C(200,i) terms.
(... more on next post...)

Posted by Charlie on 2003-01-30 09:59:15