|
%I #23 Jun 03 2022 01:12:59
%S 1,2,5,7,10,13,17,20,23,27,31,35,38,42,46,51,55,59,63,67,72,76,81,85,
%T 90,94,99,104,108,113,118,123,128,133,137,142,147,152,157,162,167,173,
%U 178,183,188,193,198,204,209,214,219,225,230,235,241,246,251,257,262
%N 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.
%C A version of the coupon collector's problem (A178923).
%D W. Feller, An Introduction to Probability Theory and Its Applications: Volume 1.
%D S. Ross, A First Course in Probability, Prentice-Hall, 3rd ed., Chapter 7, Example 3g.
%H Jens Kruse Andersen, <a href="/A073593/b073593.txt">Table of n, a(n) for n = 1..1000</a>
%H P. Erdős and A. Rényi, <a href="https://www.renyi.hu/~p_erdos/1961-09.pdf">On a classical problem of probability theory</a>, Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 1961
%H Sci.math.probability newsgroup, <a href="https://groups.google.com/forum/#!topic/alt.sci.math.probability/dn5FeQtsHGs">Collecting a deck of cards on the street</a>, Aug 2002.
%H Math.stackexchange, <a href="https://math.stackexchange.com/questions/976636/the-smallest-number-of-boxes-to-buy-to-have-probability-at-least-1-2-of-collecti">The smallest number of boxes to buy to have probability at least 1/2 of collecting all pictures</a>, Oct 2014.
%F 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
%F c likely to be closer to -log(log(2)) about 0.3665. - _Henry Bottomley_, Jun 01 2022
%t f[n_] := Block[{k = 1}, While[2StirlingS2[k, n]*n!/n^k < 1, k++ ]; k]; Table[ f[n], {n, 60}]
%o (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)
%o (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
%Y Cf. A090582, A178923 (Coupon Collector's Problem).
%K nonn
%O 1,2
%A _Robert G. Wilson v_, Aug 28 2002
|
