Results 1 to 2 of 2

Thread: 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 $\displaystyle \{1, 2, \dots , n\} $ is $\displaystyle 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
    10
    Quote Originally Posted by hcir614 View Post
    How can I show that the number of inversions of a permutaion of $\displaystyle \{1, 2, \dots , n\} $ is $\displaystyle n(n-1)/2 $
    I guess by inversion you mean transpositions i.e. $\displaystyle 2$-cycles. Note that any inversion has form $\displaystyle (ij)$ where $\displaystyle i<j$ and furthermore this is unique. Therefore the number of such inversions is $\displaystyle {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: Nov 14th 2010, 12:04 PM
  2. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 31st 2010, 02:12 PM
  3. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Mar 11th 2010, 02:12 PM
  4. Proof related to inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Mar 9th 2010, 05:19 AM
  5. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Feb 25th 2009, 03:49 PM

Search Tags


/mathhelpforum @mathhelpforum