Fork me on GitHub
Math for the people, by the people.

User login

inversion of a permutation

Primary tabs

inversion of a permutation

I want to proof that inv(p)=inv(p)^(-1)

inv(p) is the number of all inversions of p. For example p = 24153, the inversions are (2,1),(4,1)(4,3)(5,3). So I would like to show, for all inversion (i,j) every (p(j),p(i)) is an inversion for p^(-1).


On second thought, you might want to define f(x) = 0 if x = 0

and the values I show here are double.

Sorry

I am not sure I understand the notation, so apologies in advance if my answer is incorrect.

Let's define f(x) = 0 if x > 0 and = 1 if x < 0

The number of inversions is

\sum _{i,j} f[ (i-j) . (p(i) - p(j) ]

Where the indices i and j are over all possible values. But if we do that, we can also sum over all the inverse values (I use s to denote the inverse of p). We have the exact same terms, just in a different order.

\sum _{i,j} f[ (s(i)-s(j)) . (p(s(i)) - p(s(j)) ]

But since s is the inverse of p

\sum _{i,j} f[ (s(i)-s(j)) . (i - j) ]

\sum _{i,j} f[ (i - j) . (s(i)-s(j)) ]

Which is the number of inversions in s.

Please double check what I wrote because I am not sure at all.

Tony Bruguier

Subscribe to Comments for "inversion of a permutation"