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

0, 1, 5, 38, 390, 5049, 78960, 1447886, 30461872, 723267369, 19130274880, 557794986814, 17775137850624, 614607897664305, 22917282895782912, 916671255921364950, 39152092883971954688, 1778431981539189344177, 85607684151779322519552, 4353142694568849287025142, 233169669255877689516032000

Offset: 0

Author

Geoffrey Critzer, May 08 2011

Keywords

• nonn

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

Examples

			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
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..150
• Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See p. 23.
• 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.

Crossrefs

Cf. A060281.

Programs

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

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)