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

Author

Geoffrey Critzer, Jan 15 2013

Keywords

• nonn

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.

Examples

			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.
		

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

Crossrefs

Main diagonal of A265080.

Programs

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 *)

Formula

a(n) = n! * [x^n] 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