login
A208250
The sum of the largest preimage over all functions f:{1,2,...,n}->{1,2,...,n}.
2
0, 1, 6, 51, 544, 7145, 112356, 2066323, 43574336, 1036922769, 27486891100, 803137535321, 25642631336400, 888148407804853, 33165208812574216, 1328185604750416875, 56783630865774075136, 2581268127178259819297, 124322489582200453748268, 6324172127062894070727625
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
D. R. L. Brown, Bounds on surmising remixed keys, IACR, Report 2015/375, 2015-2016. See Table 1.
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
Sequence in context: A346766 A305965 A255518 * A253097 A345259 A124565
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jan 15 2013
STATUS
approved