Permutations are a special case (isomorphism) of endomorphisms,
themselves enumerated in various ways in OEIS.  For random
endomorphisms, we asymptotically know [Flajolet & Odlyzko] the mean
cycle length, and the mean number of precedecessors of a random point
in a random endomorphism. Predecessors in the directed graph
sense.  The adjacency matrix A(G)[i,j] of a directed graph G,
raised to an integer power k =< n, namely A^k(n) is the number of
directed walks from points i to point j in G. Flajolet & Odlyzko's
work has been extended to various kinds of restrictions to the
randomness, including for example random binary directed graphs.
There's quite a bit of related research.  I have many references,
if this actually amtetrs to answering your question.  I was at
Caltech the same time as Andy Odlyzko, the footnotes of whose papers I
am not worthy to touch.<br>
<br>
-- Jonathan Vos Post<br><br><div><span class="gmail_quote">On 12/7/06, <b class="gmail_sendername"><a href="mailto:franktaw@netscape.net">franktaw@netscape.net</a></b> <<a href="mailto:franktaw@netscape.net">franktaw@netscape.net
</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I was looking at <a href="http://www.research.att.com/~njas/sequences/A072949">
http://www.research.att.com/~njas/sequences/A072949</a>,<br>which led me to search for and find<br><a href="http://www.research.att.com/~njas/sequences/A062869">http://www.research.att.com/~njas/sequences/A062869</a>.  (There should
<br>really be a cross reference.)<br><br>A062869 is a table with T(n,k) = the number of permutations of n where<br>2k = the total distance sum_i abs(i-p(i)).  (Equivalently, k = sum_i<br>max(i-p(i),0).)<br><br>A062869 contains two equivalent conjectures; these are obviously
<br>correct.<br><br>A072949 also contains a conjecture (in question form).  Looking at<br>A062869, I see a more general conjecture: T(n,k) is even whenever k >=<br>n.  I don't see any start at a proof of this; but maybe somebody else
<br>can.  (Or compute some more values and show it's wrong.)<br><br>Franklin T. Adams-Watters<br><br>________________________________________________________________________<br>Check Out the new free AIM(R) Mail -- 2 GB of storage and
<br>industry-leading spam and email virus protection.<br><br></blockquote></div><br>