OFFSET
0,3
COMMENTS
n labeled balls are placed in n labeled urns. The maximum number of balls in an urn is summed over all n^n possible configurations. a(n) is this sum.
REFERENCES
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 435.
LINKS
Robert Gerbicz, Table of n, a(n) for n = 0..386
D. R. L. Brown, Bounds on surmising remixed keys, IACR, Report 2015/375, 2015-2016. See Table 1.
Sela Fried, The expected degree of noninvertibility of compositions of functions and a related combinatorial identity, arXiv:2202.13061 [math.CO], 2022.
Robert Gerbicz, a(n) for n = 0..1024 (an a-file)
Robert Gerbicz, gmp code
G. H. Gönnet, Expected length of the longest probe sequence in hash code searching, Journal of the ACM, 28:2 (1981), pp. 289-304.
Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman, The Power of Two Random Choices: A Survey of Techniques and Results
FORMULA
E.g.f.: Sum_{j>=0} exp(x)^n - (Sum_{i=0..j} x^i/i!)^n.
a(n) ~ n^n log n/log log n. More precisely, a(n)/n^n = Gamma^(-1)(n) - 3/2 + o(1) where Gamma^(-1) is the inverse of the gamma function. See Gönnet section 4 or Mitzenmacher et al. - Charles R Greathouse IV, Feb 20 2013
EXAMPLE
a(2) = 6. The functions f:{1,2}->{1,2} written as words are: 11, 12, 21, 22 and we sum respectively 2 + 1 + 1 + 2 = 6.
MATHEMATICA
f[n_] := n! Coefficient[ Series[ Sum[ Exp[n*x] - Sum[x^i/i!, {i, 0, j}]^n, {j, 0, n}], {x, 0, n}], x^n]; f[0] = 0; Array[f, 19, 0] (* modified by Robert G. Wilson v, Feb 20 2013 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jan 15 2013
STATUS
approved