|
|
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.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
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) )
|
|
REFERENCES
|
W. Feller, An Introduction to Probability Theory and its Applications, 2nd ed, Wiley, New York, 1968, (2.3) p. 92. (Occupancy problems)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = floor(n^(2n)/Sum_{v=0..n-1}( (-1)^v * binomial(n,v) * (n-v)^(2n) ))
|
|
EXAMPLE
|
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.
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|