Inversions of a permutation

**hcir614** · September 28th 2008, 12:18 PM

How can I show that the number of inversions of a permutaion of $\{1, 2, \dots , n\}$ is $n(n-1)/2$

**ThePerfectHacker** · September 29th 2008, 01:22 PM

Originally Posted by hcir614

How can I show that the number of inversions of a permutaion of $\{1, 2, \dots , n\}$ is $n(n-1)/2$

I guess by inversion you mean transpositions i.e. $2$ -cycles. Note that any inversion has form $(ij)$ where $i<j$ and furthermore this is unique. Therefore the number of such inversions is ${n\choose 2} = \frac{n(n-1)}{2}$ .

Thread: Inversions of a permutation

LinkBack

Thread Tools

Display

Inversions of a permutation

Similar Math Help Forum Discussions

Number of inversions

Inversions

Proof regarding inversions

Proof related to inversions

Another IRV question... Inversions

Search Tags