Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recognizing even or odd permutation easily?

  1. Aug 16, 2013 #1
    Hello folks, I'm not even sure if this is the place to put this but with some luck it might be.

    I just have a general question about permutations. I understand the concept of even and odd permutations of a set of numbers, what I am hoping for is an easy way to figure out if (given a scrambled arrangement of the original set) the new set is even or odd? Obviously other than the trivial solution of going through it permutation by permutation and counting.

    Thanks for any input!
  2. jcsd
  3. Aug 17, 2013 #2


    User Avatar
    Homework Helper

    The most basic odd permutations are those that swap 2 numbers. So count how many of those permutations must be applied to reach the identity. For example, 321 is odd (swap 3 and 1) but 312 is even (two swaps are required). It's a simple as that.
  4. Aug 17, 2013 #3
    I understand what odd and even permutations are, my question makes more sense if I use an example perhaps. Imagine that instead of 1,2,3 you have a set that's 1,2,3,4,5,6 . Now tell me, is 5,2,1,4,6,3 even or odd without taking forever haha :P
  5. Aug 17, 2013 #4
    Hi, vulpe,
    I'd attempt the swaps that put each peg in place. In your example,
    1,2,5,4,6,3 (1,5)
    1,2,3,4,6,5 (3,5)
    1,2,3,4,5,6 (5,6)
    hence this one is odd. At worst, you'd do as many swaps as elements are (minus 1, actually).
  6. Aug 25, 2013 #5


    User Avatar
    Science Advisor

    Go through all 2-element subsets of the numbers in the permutation and see for how many of these the greater number comes before the smaller in the permutation, call it an inversion if this is the case. If the number of inversions is odd, the permutaion is odd, otherwise even.

    For example, in the permutation given by (2 6 1 4 3 5), (that is: 1 is mapped to 2, 2 to 6, 3 to 1, etc.) there are 6 inversions: (2,1), (6,1), (6,4), (6,3), (6,5), (4,3). 6 is en even number, so the permutation is even.
  7. Aug 25, 2013 #6
    Another approach using the cycle structure.

    In your example: the permutation taking 1, 2, 3, 4, 5, 6 to 5, 2, 1, 4, 6, 3 has cycle structure (1 5 6 3) (2) (4). (If you don't know how to write down the cycle structure of a permutation, learn!) Now, a 4-cycle is odd and a 1-cycle is even, so we have odd × even × even = odd, so the permutation is odd.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook