|
%I #15 Aug 03 2014 14:01:40
%S 1,1,1,1,1,2,2,3,3,4,5,6,7,9,11,13,16,19,23,27,33,39,47,57,68,81,97,
%T 116,139,167,199,239,286,342,409,489,585,700,838,1002,1199,1434,1716,
%U 2053,2456,2938,3515,4205,5030,6018,7199,8612,10302,12325,14744,17638
%N Floor of the expected value of number of trials until all cells are occupied in a random distribution of 2n balls in n cells.
%C Also floor of the expected value of number of trials until we have n distinct symbols in a random sequence on n symbols of length 2n.
%C From (2.3), see first reference,
%C p_0(2n,n)=Sum_{v=0..n-1}((-1)^v * binomial(n,v) * (n-v)^(2n)/n^(2n))
%C = 1/n^(2n).Sum_{v=0..n-1}( (-1)^v * binomial(n,v) * (n-v)^(2n)), so
%C the expected value 1/p_0(2n, n) =
%C 1/(1/n^(2n).Sum_{v=0..n-1}( (-1)^v * binomial(n,v)*(n-v)^(2n)))
%C = n^(2n)/Sum_{v=0..n-1}( (-1)^v * binomial(n,v)*(n-v)^(2n) )
%D W. Feller, An Introduction to Probability Theory and its Applications, 2nd ed, Wiley, New York, 1968, (2.3) p. 92. (Occupancy problems)
%H Washington Bomfim and T. D. Noe, <a href="/A210024/b210024.txt">Table of n, a(n) for n = 1..1000</a> (Washington Bomfim computed the first 100 terms)
%F a(n) = floor(n^(2n)/Sum_{v=0..n-1}( (-1)^v * binomial(n,v) * (n-v)^(2n) ))
%e For n=2, with symbols 0 and 1, the 2^4 sequences on 2 symbols of length 4 can be represented by 0000, 0001, 0010, 0011, 0100, 0101,0110, 0111, 1000, 1001, 1010, 1011, 1100, 1110, and 1111. We have 2 sequences with a unique symbol, and 14 sequences with 2 distinct symbols, so a(2) = floor(16/14) = floor(8/7) = 1.
%t Table[Floor[n^(2 n)/Sum[((-1)^v*Binomial[n, v]*(n - v)^(2 n)), {v, 0, n - 1}]], {n, 100}] (* _T. D. Noe_, Mar 16 2012 *)
%Y Cf. A209899, A209900.
%K nonn
%O 1,6
%A _Washington Bomfim_, Mar 16 2012
|
