A208250 The sum of the largest preimage over all functions f:{1,2,...,n}->{1,2,...,n}.

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

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

Sequence in context: A346766 A305965 A255518 * A253097 A345259 A124565

Adjacent sequences: A208247 A208248 A208249 * A208251 A208252 A208253

Keyword

nonn

Author

Geoffrey Critzer, Jan 15 2013

Status

approved