A262970 - OEIS

%I #41 Jul 20 2024 15:08:11

%S 1,10,117,1648,27425,528336,11581885,284878336,7772592897,

%T 233010784000,7614411069221,269412832512000,10261487793254113,

%U 418636033893726208,18213563455467238125,841799936112774086656,41189866031118283907585,2127207204243268173103104

%N Total cycle length of all iteration trajectories of all elements of random mappings from [n] to [n].

%C 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.

%H G. C. Greubel, <a href="/A262970/b262970.txt">Table of n, a(n) for n = 1..380</a>

%H P. Flajolet and A. M. Odlyzko, <a href="https://hal.inria.fr/inria-00075445">Random Mapping Statistics</a>, INRIA RR 1114, 1989.

%H Math StackExchange, <a href="http://math.stackexchange.com/questions/1463544/">Generating functions for tail length and rho-length</a>

%F 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).

%F a(n) = e^n * n * Gamma(n + 1, n) / 2. - _Peter Luschny_, Jul 20 2024

%p proc(n) 1/2*n!*add(n^q*(n + 1 - q)*(n - q)/q!, q = 0 .. n - 1) end proc

%t Table[n!/2 Sum[n^q (n + 1 - q) (n - q)/q!, {q, 0, n - 1}], {n, 21}] (* _Michael De Vlieger_, Oct 06 2015 *)

%t a[n_] := E^n n Gamma[n + 1, n] / 2;

%t Table[a[n], {n, 1, 19}]  (* _Peter Luschny_, Jul 20 2024 *)

%o (PARI) a(n) = n! * sum(q=0, n-1, n^q*(n+1-q)*(n-q)/q!)/2;

%Y Cf. A036360.

%K nonn

%O 1,2

%A _Marko Riedel_, Oct 05 2015