Results 1 to 2 of 2

Math Help - Inversions of a permutation

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    2

    Inversions of a permutation

    How can I show that the number of inversions of a permutaion of  \{1, 2, \dots , n\} is  n(n-1)/2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by hcir614 View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of inversions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 14th 2010, 12:04 PM
  2. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2010, 02:12 PM
  3. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 02:12 PM
  4. Proof related to inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 9th 2010, 05:19 AM
  5. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 25th 2009, 03:49 PM

Search Tags


/mathhelpforum @mathhelpforum