|
|
A210113
|
|
Floor of the expected value of number of trials until exactly two cells are empty in a random distribution of n balls in n cells.
|
|
5
|
|
|
9, 3, 2, 1, 2, 3, 4, 7, 12, 21, 40, 75, 147, 292, 594, 1229, 2582, 5499, 11859, 25868, 57008, 126814, 284523, 643401, 1465511, 3360493, 7753730, 17993787, 41982506, 98445184, 231932762, 548839352, 1304155087
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
Also floor of the expected value of number of trials until we have n-2 distinct symbols in a random sequence on n symbols of length n. A055775 corresponds to zero cells empty.
|
|
REFERENCES
|
W. Feller, An Introduction to Probability Theory and its Applications, 2nd ed, Wiley, New York, 1965, (2.4) p. 92. (Occupancy problems)
|
|
LINKS
|
|
|
FORMULA
|
With m = 2, a(n) = floor(n^n/(binomial(n,m)*_Sum{v=0..n-m-1}((-1)^v*binomial(n-m,v)*(n-m-v)^n)))
|
|
EXAMPLE
|
For n=3, there are 3^3 = 27 sequences on 3 symbols of length 3. Only 3 sequences has a unique symbol, so a(3) = floor(27/3) = 9.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|