Lesson 3

A \(3\)-cycle is a permutation in which all objects except three remain fixed, while those three are permuted cyclically.

If we apply several \(3\)-cycles in sequence, then each of them can be replaced by two transpositions, so the resulting permutation is even. The following theorem shows that every even permutation can be obtained in this way.

Theorem. Every even permutation of \(n\) objects can be represented as a sequence of \(3\)-cycles.

Note that this theorem is vacuously true for \(n=1\) and \(n=2\): in these cases, the identity permutation is the only even permutation, and it is obtained by an empty sequence of \(3\)-cycles. Although \(3\)-cycles do not exist when \(n=1\) or \(n=2\), this does not prevent us from considering an empty sequence of \(3\)-cycles.

Proof. Earlier, we proved that every permutation can be decomposed into transpositions by filling the positions one by one with the required objects. A similar argument works for \(3\)-cycles instead of transpositions, provided that at least three objects remain available: we need a third spare object to form a cycle.

Thus, compared with the previous argument for transpositions, we need one spare object, and so we must stop when only two positions remain unfilled. There are then two possibilities. In the good case, the two remaining objects are already in their correct positions. In the bad case, they are not, and one additional transposition is needed to obtain the required permutation. But then the permutation would be the composition of several \(3\)-cycles and one transposition, and hence would be odd, contrary to the assumption that it is even.◼