inversion of a permutation

## Primary tabs

# inversion of a permutation

Submitted by Euklid123 on Tue, 12/14/2010 - 02:00

Forums:

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).

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Re: inversion of a permutation

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

and the values I show here are double.

Sorry

## Re: inversion of a permutation

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