OFFSET
0,3
COMMENTS
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.
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
a(n) was "not easy to estimate" in 1953 according to the Metropolis-Ulam reference. - David Callan, Jun 15 2018
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..150
N. Metropolis and S. Ulam, A Property of Randomness of an Arithmetical Function, American Mathematical Monthly, Vol. 60, No. 4 (Apr., 1953), pp. 252-253.
FORMULA
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
a(n) = Sum_{k=1..n} (k-1)!*C(n,k)*n^(n-k). - Geoffrey Critzer, Dec 26 2012
a(n) ~ n^n*(log(2*n) + gamma)/2, where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 08 2013
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
a(n) = n! * [x^n] -exp(n*x)*log(1 - x). - Ilya Gutkovskiy, Jan 18 2018
a(n) = Sum_{k=1..n} k * A060281(n,k). - Alois P. Heinz, Dec 15 2021
Conjectures from Velin Yanev, Apr 14 2024: (Start)
a(n) = (n^n)*Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^(n*t)) dt for n > 0.
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)
EXAMPLE
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
MAPLE
a:= n-> add((k-1)!*binomial(n, k)*n^(n-k), k=1..n):
seq(a(n), n=0..20); # Alois P. Heinz, Dec 26 2012
MATHEMATICA
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}]]]
nmax = 20; CoefficientList[Series[-Log[1 + LambertW[-x]]/(1 + LambertW[-x]), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 09 2019 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, May 08 2011
STATUS
approved