Pokemon combinatorics

Collectable card games are incredibly popular. The cards for these games are typically sold in packages of several cards. The manufacturers print several sheets of cards, and include cards from the different sheets in these packages with different frequencies. They might include four cards from sheet A, two cards from sheet B and a single card from sheet C, calling the cards from sheet A “common,” the ones from sheet B “uncommon” and the cards from sheet C “rare.” Your ability to complete a collection of the entire set of cards is clearly limited by your ability to collect all of the rare cards.

How many packages of cards can you expect to have to buy before you complete a set?

A solution to this problem was described by Paul Erdős and Alfréd Rényi in 1961. Here’s roughly how their solution goes.

Suppose that we already have k different rare cards out of a total set of n possible cards. The next time we buy a pack of cards the probability to not get a new rare card is k/n so the probability that we need to buy exactly p packs of cards to get another new rare card is

(k/n)p-1 (1 - k/n)

so the expected number of packs of cards that we’ll need to buy to a new rare card is

Σp≥1 (k/n)p-1 (1 – k/n) p = 1 / (1 - k/n)

= n / ( nk)

So the expected number of packs of cards that we’ll need to buy to get all n rare cards is

Σk=0:n-1 n / ( nk) = n/n + n/(n - 1) + … + n/2 + n/1

= n (1/n + 1/(n – 1) + … + 1/2 + 1/1)

= n Hn

So you should expect to buy packs equal to about Hn times the number of rare cards to get a complete set. If there are 50 rare cards in a set, for example, you should expect to buy about H50 (approximately 4.5) times 50, or about 225 packs to get a complete set.

Here's how Hn grows as a function of n:

Image003

So for the number of rare cards in a typical set of collectable cards, a good rule of thumb is that you can expect to have to buy a number of packs of cards equal to between four and five times the number of rare cards to complete your set.

Leave a Reply

Your email address will not be published. Required fields are marked *