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,2

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).

Links

Table of n, a(n) for n=1..56.

Example

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... .)

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}]

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.

Sequence in context: A315475 A315476 A315477 * A315478 A315479 A315480

Adjacent sequences: A085810 A085811 A085812 * A085814 A085815 A085816

Keyword

nonn

Author

Alfred Heiligenbrunner, Jul 25 2003

Extensions

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

Status

approved