A210024 Floor of the expected value of number of trials until all cells are occupied in a random distribution of 2n balls in n cells.

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, 116, 139, 167, 199, 239, 286, 342, 409, 489, 585, 700, 838, 1002, 1199, 1434, 1716, 2053, 2456, 2938, 3515, 4205, 5030, 6018, 7199, 8612, 10302, 12325, 14744, 17638

Offset: 1

Author

Washington Bomfim, Mar 16 2012

Keywords

• nonn

Comments

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.

From (2.3), see first reference,

p_0(2n,n)=Sum_{v=0..n-1}((-1)^v * binomial(n,v) * (n-v)^(2n)/n^(2n))

= 1/n^(2n).Sum_{v=0..n-1}( (-1)^v * binomial(n,v) * (n-v)^(2n)), so

the expected value 1/p_0(2n, n) =

1/(1/n^(2n).Sum_{v=0..n-1}( (-1)^v * binomial(n,v)*(n-v)^(2n)))

= n^(2n)/Sum_{v=0..n-1}( (-1)^v * binomial(n,v)*(n-v)^(2n) )

Examples

			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.
		

References

• W. Feller, An Introduction to Probability Theory and its Applications, 2nd ed, Wiley, New York, 1968, (2.3) p. 92. (Occupancy problems)

Links

• Washington Bomfim and T. D. Noe, Table of n, a(n) for n = 1..1000 (Washington Bomfim computed the first 100 terms)

Crossrefs

Cf. A209899, A209900.

Programs

Mathematica

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 *)

Formula

a(n) = floor(n^(2n)/Sum_{v=0..n-1}( (-1)^v * binomial(n,v) * (n-v)^(2n) ))