Permutations by total distance

[Jonathan Post]

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.

-- Jonathan Vos Post

On 12/7/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
>
> I was looking at http://www.research.att.com/~njas/sequences/A072949,
> which led me to search for and find
> http://www.research.att.com/~njas/sequences/A062869.  (There should
> really be a cross reference.)
>
> A062869 is a table with T(n,k) = the number of permutations of n where
> 2k = the total distance sum_i abs(i-p(i)).  (Equivalently, k = sum_i
> max(i-p(i),0).)
>
> A062869 contains two equivalent conjectures; these are obviously
> correct.
>
> A072949 also contains a conjecture (in question form).  Looking at
> A062869, I see a more general conjecture: T(n,k) is even whenever k >=
> n.  I don't see any start at a proof of this; but maybe somebody else
> can.  (Or compute some more values and show it's wrong.)
>
> Franklin T. Adams-Watters
>
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- 2 GB of storage and
> industry-leading spam and email virus protection.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061207/96aa145f/attachment-0003.htm>