%I #55 Apr 25 2024 14:06:10

%S 0,1,5,38,390,5049,78960,1447886,30461872,723267369,19130274880,

%T 557794986814,17775137850624,614607897664305,22917282895782912,

%U 916671255921364950,39152092883971954688,1778431981539189344177,85607684151779322519552,4353142694568849287025142,233169669255877689516032000

%N The number of cycles in the digraph representation of all endofunctions on {1,2,...,n}.

%C Equivalently, since each component contains exactly one cycle, a(n) is the number of connected components in all endofuntions on {1,2,...,n}. An endofunction on {1,2,...,n} is a function from {1,2,...,n} into {1,2,...,n}. Here we are counting self loops as a cycle.

%C The total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j). - _Geoffrey Critzer_, Dec 26 2012

%C a(n) was "not easy to estimate" in 1953 according to the Metropolis-Ulam reference. - _David Callan_, Jun 15 2018

%H Alois P. Heinz, <a href="/A190314/b190314.txt">Table of n, a(n) for n = 0..150</a>

%H N. Metropolis and S. Ulam, <a href="http://www.jstor.org/stable/2307436">A Property of Randomness of an Arithmetical Function</a>, American Mathematical Monthly, Vol. 60, No. 4 (Apr., 1953), pp. 252-253.

%F E.g.f.: Log[1/(1-T(x))]/(1-T(x)) where T(x) is the e.g.f. for A000169. - _Geoffrey Critzer_, Mar 22 2012

%F a(n) = Sum_{k=1..n} (k-1)!*C(n,k)*n^(n-k). - _Geoffrey Critzer_, Dec 26 2012

%F a(n) ~ n^n*(log(2*n) + gamma)/2, where gamma is the Euler-Mascheroni constant (A001620). - _Vaclav Kotesovec_, Oct 08 2013

%F a(n) = Sum_{k=1..n} A066324(n,k)*H(k) where H(k) is the k-th harmonic number. - _Geoffrey Critzer_, Nov 02 2014

%F a(n) = n! * [x^n] -exp(n*x)*log(1 - x). - _Ilya Gutkovskiy_, Jan 18 2018

%F a(n) = Sum_{k=1..n} k * A060281(n,k). - _Alois P. Heinz_, Dec 15 2021

%F Conjectures from _Velin Yanev_, Apr 14 2024: (Start)

%F a(n) = (n^n)*Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^(n*t)) dt for n > 0.

%F a(n) = (e^n)*Gamma(n) + (n^n)*(n*hypergeom([1, 1], [2, n + 2], n)/(n + 1) - ((-1)^n)*Gamma(n)*Gamma(1 - n, -n) + log(n) - polygamma(n) - 1/n + i*Pi) for n > 0, where polygamma is the digamma function and the bivariate gamma function is the upper incomplete gamma function. (End)

%e a(2) = 5 because there are four functions from {1,2} into {1,2} but only one of these is not connected: 1->1,2->2 so there is a total of 5 components in all. - _Geoffrey Critzer_, Mar 22 2012

%p a:= n-> add((k-1)!*binomial(n, k)*n^(n-k), k=1..n):

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Dec 26 2012

%t f[list_] := Total[Table[i * list[[i]], {i,1,Length[list]}]]; t=Sum[n^(n-1)x^n/n!, {n,1,20}]; Map[f,Transpose[Table[Drop[Range[0,20]! CoefficientList[Series[Log[1/(1-t)]^k/k!, {x,0,20}], x], 1], {k,0,20}]]]

%t nmax = 20; CoefficientList[Series[-Log[1 + LambertW[-x]]/(1 + LambertW[-x]), {x, 0, nmax}], x] * Range[0, nmax]! (* _Vaclav Kotesovec_, Jun 09 2019 *)

%Y Cf. A060281.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, May 08 2011