OFFSET
1,2
COMMENTS
An iteration trajectory is the directed graph obtained by iterating the mapping starting from one of the n elements until a cycle appears and consists of a tail attached to a cycle.
LINKS
G. C. Greubel, Table of n, a(n) for n = 1..380
P. Flajolet and A. M. Odlyzko, Random Mapping Statistics, INRIA RR 1114, 1989.
Math StackExchange, Generating functions for tail length and rho-length
FORMULA
E.g.f.: T/(1-T)^4, where T is the labeled tree function, average over all mappings and values asymptotic to sqrt(Pi*n/8).
a(n) = e^n * n * Gamma(n + 1, n) / 2. - Peter Luschny, Jul 20 2024
MAPLE
proc(n) 1/2*n!*add(n^q*(n + 1 - q)*(n - q)/q!, q = 0 .. n - 1) end proc
MATHEMATICA
Table[n!/2 Sum[n^q (n + 1 - q) (n - q)/q!, {q, 0, n - 1}], {n, 21}] (* Michael De Vlieger, Oct 06 2015 *)
a[n_] := E^n n Gamma[n + 1, n] / 2;
Table[a[n], {n, 1, 19}] (* Peter Luschny, Jul 20 2024 *)
PROG
(PARI) a(n) = n! * sum(q=0, n-1, n^q*(n+1-q)*(n-q)/q!)/2;
CROSSREFS
KEYWORD
nonn
AUTHOR
Marko Riedel, Oct 05 2015
STATUS
approved