Permutations of the positive integers

[Max Alekseyev]

On 6/19/07, Kimberling, Clark <ck6 at evansville.edu> wrote:

> However, when you wrote that the inversion vector of p equals "the
> vector t with every element decreased by 1," did you mean for this t to
> be the same as the trace sequence (also denoted by t) of p?  If so,
> you're your t doesn't seem to be the t as originally given in the
> message copied below.
>
> Here is a "formula" for the kth term of the trace t (using the symbol P
> for the inverse of p):
>
> t(k) = the number of numbers p(i) such that 1<=i<=P(k) AND p(i)>=k.

Compare this to the definition of inversion vector i():

i(k) = the number of numbers p(i) such that 1<=i<P(k) AND p(i)>k.

It is easy to see that i(k) = t(k) - 1 for every k=1,2,3,...

So, if
t = (1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,...)
then
i = (0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,...)

Max