Lesson 6

To prove that a permutation cannot be both even and odd, we first introduce the notion of a neighbor transposition. A neighbor transposition is a transposition that swaps two adjacent elements. In other words, it has the form \((i,j)\), where \(|i-j|=1\).

It is not difficult to see that any permutation can be transformed into any other permutation using only neighbor transpositions. Indeed, every transposition can be written as a sequence of neighbor transpositions. This is best illustrated by an example. Suppose we want to swap the elements \(7\) and \(2\). We first move \(7\) toward \(2\), then swap \(7\) and \(2\), and finally move \(2\) back to the original position of \(7\).