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

In case A, within each packet of 5, the probability of a further non-match (after preceding cards in the packet fail to match) decrease, so unlike case B, where each card is essentially independent, case A requires a lowering probability of non-match for any given card, or as the inclusion/exclusion formula requires multiple ORed cards, any given set of cards, the formula changes from

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

∑{i=1 to 200} (1-(((200-i)/200)*((200-i-1)/199) *((200-i-2)/198) *((200-i-3)/197) *((200-i-4)/196))^p C(200,i) (-1)^(i-1)
for case A. Note we now use p, the number of packets, rather than n, the number of cards drawn previously.

Explicitly stated then, the formula for the Expected number of packets drawn in case A is:
∑{p=40 to infinity} p * ∑{i=1 to 200} (1-(((200-i)/200)*((200-i-1)/199) *((200-i-2)/198) *((200-i-3)/197) *((200-i-4)/196))^p C(200,i) (-1)^(i-1)
This comes out to 233.158145… when evaluated up to p=3000, which is sufficient, as explained in a previous post, using UBASIC with a setting of 120-decimal-digit accuracy, to get around the loss of 60 decimal digits due to additions of numbers with 60 digits before the decimal point, alternating positive and negative, for the probabilities.

The explicit formula for part B is
∑{p=40 to infinity} p * ∑{i=1 to 200} (1-((200-i)/200)^(5*p)) C(200,i) (-1)^(i-1)
which turns out to be 235.5212379…
(where C(n,r) is the combinations of n taken r at a time)

Posted by Charlie on 2003-01-31 08:33:22