A permutation is even when it can be written as to composition of an even number of swaps, a swap being a permutation that exchanges two items and leaves the rest fixed. An odd permutation can be written as an odd number of swaps.

Every permutation that permutes only a finite number of elements is either even or odd, not both.

One way to see this is as follows.

  1. Let f be the function on sequences of natural numbers that
    • does nothing if the sequence is strictly increasing;
    • for the first number that is not smaller than the next:
      • removes it if they are equal
      • swaps them otherwise
    Every finite sequence of numbers will turn into an increasing one by applying f a certain number of times. We will manipulate sequences of swaps in the same way.
  2. Consider all permutations on a finite set X. Any ordering of X given by i: X -< {1 ... |X|} also orders swaps of elements in X in the obvious way: (a b) < (c d) iff min(i(a),i(b)) < min(i(c),i(d)) or (min(i(a),i(b)) = min(i(c),i(d)) and max(i(a),i(b)) < max(i(c),i(d))). Note that this is indeed a total ordering.
  3. For any sequence of swaps s of elements in X let p(s) be its longest prefix of which all consecutive swaps are ordered according to i. Now let f be the function that associates with each sequence of swaps s
    • s if if p(s) = s
    • p(s) y if s = p(s) (a b) (c d) y and |{a,b,c,d}| < 3
    • p(s) (c d) (a b) y if s = p(s) (a b) (c d) y and |{a,b,c,d}| = 4 and (c d) < (a b)
    • p(s) (b c) (a b) y if s = p(s) (a b) (a c) y and (b c) < (a b)
    Then
    • for every s, the permutations expressed by s and f(s) are the same
    • after some number of applications of f we have a sequence t that is equal to p(t); denote this sequence as f*(s)
    • two sequences s1 and s2 express the same permutation iff f*(s1) = f*(s2)
    • for every s, the length of s is even iff the length of f*(s) is even
There are faster ways to prove this ...

Log in or register to write something here or to contact authors.