Lesson 4

There are many ways to get one permutation from another.

Interestingly, any sequence of transpositions that transforms one permutation into another has the same parity. In other words, for any two permutations \(\pi_{1}\) and \(\pi_{2}\), it is impossible to transform \(\pi_{1}\) into \(\pi_{2}\) using an odd number of transpositions and also using an even number of transpositions. We will prove this shortly. For now, observe that this fact allows us to define the parity of a permutation as follows.

We say that a permutation is even if it can be obtained from the identity permutation (that is, \((0, 1, \dotsc, n-1)\)) by an even number of transpositions. Otherwise, the permutation is called odd.