

A262970


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


1



1, 10, 117, 1648, 27425, 528336, 11581885, 284878336, 7772592897, 233010784000, 7614411069221, 269412832512000, 10261487793254113, 418636033893726208, 18213563455467238125, 841799936112774086656, 41189866031118283907585, 2127207204243268173103104
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 rholength


FORMULA

E.g.f.: T/(1T)^4, where T is the labeled tree function, average over all mappings and values asymptotic to sqrt(Pi*n/8).


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


PROG

(PARI) a(n) = n! * sum(q=0, n1, n^q*(n+1q)*(nq)/q!)/2;


CROSSREFS

Sequence in context: A251318 A083448 A024129 * A309582 A155622 A307695
Adjacent sequences: A262967 A262968 A262969 * A262971 A262972 A262973


KEYWORD

nonn


AUTHOR

Marko Riedel, Oct 05 2015


STATUS

approved



