login
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

%I #17 Feb 10 2020 06:15:02

%S 1,6,11,16,21,27,33,38,44,51,57,63,70,76,83,90,96,103,110,117,124,131,

%T 138,145,152,159,167,174,181,189,196,203,211,218,226,233,241,248,256,

%U 264,271,279,287,294,302,310,318,326,333,341,349,357,365,373,381,389

%N 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.

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

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

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

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

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

%Y Cf. A090582.

%K nonn

%O 1,2

%A _Alfred Heiligenbrunner_, Jul 25 2003

%E More terms from _Robert G. Wilson v_, Sep 07 2003