A073593 Number of cards needed to be drawn (with replacement) from a deck of n cards to have a 50% or greater chance of seeing each card at least once.

1, 2, 5, 7, 10, 13, 17, 20, 23, 27, 31, 35, 38, 42, 46, 51, 55, 59, 63, 67, 72, 76, 81, 85, 90, 94, 99, 104, 108, 113, 118, 123, 128, 133, 137, 142, 147, 152, 157, 162, 167, 173, 178, 183, 188, 193, 198, 204, 209, 214, 219, 225, 230, 235, 241, 246, 251, 257, 262

Offset

1,2

Comments

A version of the coupon collector's problem (A178923).

References

W. Feller, An Introduction to Probability Theory and Its Applications: Volume 1.

S. Ross, A First Course in Probability, Prentice-Hall, 3rd ed., Chapter 7, Example 3g.

Links

Jens Kruse Andersen, Table of n, a(n) for n = 1..1000

P. Erdős and A. Rényi, On a classical problem of probability theory, Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 1961

Sci.math.probability newsgroup, Collecting a deck of cards on the street, Aug 2002.

Math.stackexchange, The smallest number of boxes to buy to have probability at least 1/2 of collecting all pictures, Oct 2014.

Formula

a(n) seems to be asymptotic to n*(log(n)+c) with c=0.3(6)...and maybe c=1/e. - Benoit Cloitre, Sep 07 2002

c likely to be closer to -log(log(2)) about 0.3665. - Henry Bottomley, Jun 01 2022

Mathematica

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

Prog

(PARI) S2(n, k) = if(k<1 || k>n, 0, if(n==1, 1, k*S2(n-1, k)+S2(n-1, k-1))); a(n)=if(n<0, 0, k=1; while( 2*S2(k, n)*n!/n^k<1, k++); k)
(PARI) a(n)=v=vector(n+1); k=1; v[n]=1.0; while(v[1]<0.5, k++; for(i=1, n, v[i]=v[i]*(n+1-i)/n+v[i+1]*i/n)); k \\ Faster program. Jens Kruse Andersen, Aug 03 2014

Crossrefs

Cf. A090582, A178923 (Coupon Collector's Problem).

Sequence in context: A376959 A189757 A094065 * A364451 A241510 A088947

Adjacent sequences: A073590 A073591 A073592 * A073594 A073595 A073596

Keyword

nonn

Author

Robert G. Wilson v, Aug 28 2002

Status

approved