Results 1 to 4 of 4

Thread: Inversions

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Inversions

    Hello!

    I'm not quite understanding this idea of inversions. I know that if $\displaystyle \pi$ is a permutation, then a pair $\displaystyle (i,j)$ is an inversion if $\displaystyle (i-j)(\pi (i)- \pi (j))<0$.

    The graph of $\displaystyle \pi$ has $\displaystyle i$ and $\displaystyle j$ as adjacent iff $\displaystyle (i,j)$ is an inversion.

    I think I understand that. I have this big problem though:

    Suppose $\displaystyle \pi=(1234)$. These are the points $\displaystyle 1,2,3,4$ connected in a square shape. Clearly $\displaystyle 1$ and $\displaystyle 2$ are adjacent.

    But, the formula gives for $\displaystyle (1,2)$ (this is just a pair, it isn't permutation notation?), $\displaystyle (1-2)(2-3)>0$.

    I can't see why this is wrong, $\displaystyle \pi(1)=2$ and $\displaystyle \pi(2)=3$ since we're just following the path around the square.

    Can someone explain why this is wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    I think we need to double-check the definitions. This statement looks suspicious:

    The graph of has and as adjacent iff is an inversion.
    What is the graph of a permutation? Is it the directed graph with edges $\displaystyle \{(i,j)\mid\pi(i)=j\}$? If $\displaystyle (i, j)$ is an inversion according to your definition, it is not required that $\displaystyle \pi(i)=j$.

    By the way, how do you write permutations? E.g., is (1234) the identity permutation or a cycle 1->2->3->4->1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I normally write permutations as cycles. It was how I first learnt how to do them, and I think they usually show cycles better (or at least I think so anyway!).

    I have the definition in front of me:

    "The graph of permutation $\displaystyle \pi$, denoted $\displaystyle G[\pi]$, has $\displaystyle \{1,2, \ldots , n \}$ as it's vertex set with i and j being adjacent iff (i,j) is an inversion.

    So if i'm calculating inversions properly, the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph. Maybe that's what's going wrong? =S
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph.
    Yes, according to this definition, the graph of the permutation (1234) has edges (1,4), (2,4) and (3,4).
    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. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Mar 11th 2010, 02:12 PM
  3. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Feb 25th 2009, 03:49 PM
  4. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 29th 2008, 01:22 PM
  5. Using MergeSort to count Inversions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 17th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum