|
|
A210112
|
|
Floor of the expected value of number of trials until exactly one cell is empty in a random distribution of n balls in n cells.
|
|
5
|
|
|
2, 1, 1, 2, 4, 7, 14, 29, 61, 129, 282, 623, 1400, 3189, 7347, 17101, 40167, 95110, 226841, 544555, 1314983, 3192458, 7788521, 19086807, 46968280, 116019696, 287602234, 715281652, 1784383956, 4464139806
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
Also floor of the expected value of number of trials until we have n-1 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 = 1, 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=2, with symbols 0 and 1, the 2^2 sequences on 2 symbols of length 2 can be represented by 00, 01, 10, and 11. We have 2 sequences with a unique symbol, so a(2) = floor(4/2) = 2.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|