Chapter 39

Cycle decompositions

39.1 The disjoint cycle decomposition of a permutation

Theorem 39.1.Every permutation can be decomposed into a product of
disjoint cycles.

For example, the permutation

(

123456 7 8 9XJQK

698342 K 7 Q 51 JX

)

decomposes into the two disjoint cycles(1629QJ)(387KX54).

Theorem 39.2.Every cycle decomposes into a product of transpositions.

Theorem 39.3. A permutation can be decomposed into a product of
transpositions. The parity (of the number of transpositions) of the per-
mutation is independent of the decomposition.

Thus, permutations are classified into even and odd permutations.
Even (respectively odd) permutations are said to have parity+1(respec-
tively− 1 ).

Corollary 39.4.A cycle of lengthkhas parity(−1)k−^1. More generally,
a permutation ofnobjects has parity

(−1)n−number of disjoint cycles in a decomposition.

In using this formula, the fixed points are counted as 1-cycles, though
we usually do not write them in the cycle decomposition of a permuta-
tion.