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
Keywords
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.
Programs
-
Mathematica
f[n_] := Block[{k = 1}, While[2StirlingS2[k, n]*n!/n^k < 1, k++ ]; k]; Table[ f[n], {n, 60}] -
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
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
Comments