login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262973 Total tail length of all iteration trajectories of all elements of random mappings from [n] to [n]. 0
0, 2, 36, 624, 11800, 248400, 5817084, 150660608, 4285808496, 133010784000, 4475982692500, 162419627132928, 6324111407554824, 263067938335913984, 11645155099754347500, 546652030933421260800, 27126781579050558916576, 1418971858887930496745472 (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

Table of n, a(n) for n=1..18.

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^2/(1-T)^4 where T is the labeled tree function, average over all mappings and values is asymptotic to sqrt(Pi*n/8).

MAPLE

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

MATHEMATICA

Table[n!/2 Sum[n^q (n - q) (n - 1 - q)/q!, {q, 0, n - 2}], {n, 21}] (* Michael De Vlieger, Oct 06 2015 *)

CROSSREFS

Sequence in context: A064030 A228790 A124104 * A207832 A112036 A093530

Adjacent sequences:  A262970 A262971 A262972 * A262974 A262975 A262976

KEYWORD

nonn

AUTHOR

Marko Riedel, Oct 05 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 21:28 EDT 2017. Contains 287257 sequences.