cp's OEIS Frontend

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

%I A208250 #67 Aug 09 2025 22:35:18
%S A208250 0,1,6,51,544,7145,112356,2066323,43574336,1036922769,27486891100,
%T A208250 803137535321,25642631336400,888148407804853,33165208812574216,
%U A208250 1328185604750416875,56783630865774075136,2581268127178259819297,124322489582200453748268,6324172127062894070727625
%N A208250 The sum of the largest preimage over all functions f:{1,2,...,n}->{1,2,...,n}.
%C A208250 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.
%D A208250 R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 435.
%H A208250 Robert Gerbicz, <a href="/A208250/b208250.txt">Table of n, a(n) for n = 0..386</a>
%H A208250 D. R. L. Brown, <a href="https://ia.cr/2015/375">Bounds on surmising remixed keys</a>, IACR, Report 2015/375, 2015-2016. See Table 1.
%H A208250 Sela Fried, <a href="https://arxiv.org/abs/2202.13061">The expected degree of noninvertibility of compositions of functions and a related combinatorial identity</a>, arXiv:2202.13061 [math.CO], 2022.
%H A208250 Robert Gerbicz, <a href="/A208250/a208250.txt">a(n) for n = 0..1024</a> (an a-file)
%H A208250 Robert Gerbicz, <a href="/A208250/a208250.c.txt">gmp code</a>
%H A208250 G. H. Gönnet, <a href="https://cs.uwaterloo.ca/research/tr/1978/CS-78-46.pdf">Expected length of the longest probe sequence in hash code searching</a>, Journal of the ACM, 28:2 (1981), pp. 289-304.
%H A208250 Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman, <a href="http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf">The Power of Two Random Choices: A Survey of Techniques and Results</a>
%F A208250 a(n) = n! * [x^n] Sum_{j>=0} (exp(x)^n - (Sum_{i=0..j} x^i/i!)^n).
%F A208250 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
%e A208250 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.
%t A208250 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 *)
%Y A208250 Main diagonal of A265080.
%K A208250 nonn
%O A208250 0,3
%A A208250 _Geoffrey Critzer_, Jan 15 2013