A085813 Number of cards that need to be drawn (with replacement) from a deck of n cards to have a 95% or greater chance of seeing each card at least once.

1, 6, 11, 16, 21, 27, 33, 38, 44, 51, 57, 63, 70, 76, 83, 90, 96, 103, 110, 117, 124, 131, 138, 145, 152, 159, 167, 174, 181, 189, 196, 203, 211, 218, 226, 233, 241, 248, 256, 264, 271, 279, 287, 294, 302, 310, 318, 326, 333, 341, 349, 357, 365, 373, 381, 389

Offset: 1

Author

Alfred Heiligenbrunner, Jul 25 2003

Keywords

• nonn

Comments

The probability that there are at most k different cards in t drawings is (k/m)^t * binomial(m,k). This also includes the cases with k-1 different cards, which we want to subtract. Inclusion and exclusion leads to the formula Sum_{k=1..m} (-1)^(m-k) * (k/m)^t * binomial(m,k).

Examples

			a(2)=6 because you have to throw a coin 6 times to get both sides at least once with probability greater than or equal to 0.95. (The probability of getting only one side in a series of 6 throws is (1/2)^6 * 2 = 1/32 = 0.03125 < 0.05.)
a(6)=27 because you have to roll a die 27 times to see all 6 possible outcomes with a probability over 0.95. (If you roll a die 27 times, the probability of getting all 6 sides at least once is 0.95658638... . If you roll the die only 26 times, the probability is 0.94798274... .)
		

Crossrefs

Cf. A073593 (number of drawings for a 50% probability of seeing each card, = median) and A060293 (expected value of the number of drawings until each card is drawn once).

Cf. A090582.

Programs

Mathematica

f[1] = 1; f[n_] := f[n] = Block[{k = f[n - 1]}, While[ 2StirlingS2[k, n]*n!/n^k < 19/10, k++ ]; k]; Table[ f[n], {n, 1, 56}]

Extensions

More terms from Robert G. Wilson v, Sep 07 2003