Permutations of the positive integers

[Max Alekseyev]

There is two known objects related to the trace t that you may find helpful.

First is an inversion vector of p that equals to the vector t with
every element decreased by 1.
See http://mathworld.wolfram.com/InversionVector.html

Second is an inversion table of p that can be obtained by applying the
permutation p to the inversion vector.
See http://www.liafa.jussieu.fr/~rossin/Enseignement/MPRI/Cours1/index.php#htoc2

Max

On 6/17/07, Kimberling, Clark <ck6 at evansville.edu> wrote:
>
>
> Dear Seqfans -
>
> Suppose p is a permutation of the positive integers, N.  If we subtract 1
> from every term and then delete 0, what's left is another perm.  Iterate,
> and we get many perms.
>
> Now, let t(k) be the position of 1 in the kth iterate.
>
> Example:  p = (1,3,2,5,7,4,9,11,6,13,15,8,...) = A006369
> (related to 3X+1 problem)
> This choice of p yields trace sequence t = (1,2,1,3,1,4,1,5,1,6,1,7,...) =
> A057979 essentially.
>
> A sequence t of positive integers is the trace of a perm if and only if t
> has infinitely many 1's.  Let T be the set of all such t.
>
> Suppose t_p and t_q are traces of perms p and q.  Can someone find a decent
> formula for t_r, where r is the composite perm p-of-q?
>
> I'd like to see such a formula - it would define a group operation on the
> set T.
>
> Clark Kimberling