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.