Section 1.2. Permutations 9 Usually we suppress the 1-cycles in the factorization of a permutation in Propo- sition 1.4 [for 1-cycles equal the identity function]. However, a factorization of α in which we display one 1-cycle for each i fixed by α, if any, will arise several times. Definition. A complete factorization of a permutation α is a factorization of α into disjoint cycles that contains exactly one 1-cycle (i) for every i fixed by α. For example, a complete factorization of the 3-cycle α = (1 3 5) in S5 is α = (1 3 5)(2)(4). There is a relation between the notation for an r-cycle β = (i1 i2 . . . ir) and its powers βk, where βk denotes the composite of β with itself k times. Note that i2 = β(i1), i3 = β(i2) = β(β(i1)) = β2(i1), i4 = β(i3) = β(β2(i1)) = β3(i1), and, more generally, ik+1 = βk(i1) for all positive k r. Theorem 1.6. Let α ∈ Sn and let α = β1 · · · βt be a complete factorization into disjoint cycles. This factorization is unique except for the order in which the cycles occur . Proof. Since every complete factorization of α has exactly one 1-cycle for each i fixed by α, it suﬃces to consider (not complete) factorizations into disjoint cycles of lengths ≥ 2. Let α = γ1 · · · γs be a second factorization of α into disjoint cycles of lengths ≥ 2. The theorem is proved by induction on , the larger of t and s. The inductive step begins by noting that if βt moves i1, then βt k(i1) = αk(i1) for all k ≥ 1. Some γj must also move i1 and, since disjoint cycles commute, we may assume that γs moves i1. It follows that βt = γs (Exercise 1.15 on page 15) right multiplying by βt −1 gives β1 · · · βt−1 = γ1 · · · γs−1, and the inductive hypothesis applies. • Definition. Two permutations α, β ∈ Sn have the same cycle structure if, for each r ≥ 1, their complete factorizations have the same number of r-cycles. According to Exercise 1.12 on page 15, there are 1 r [n(n − 1) · · · (n − r + 1)] r-cycles in Sn. This formula can be used to count the number of permutations having any given cycle structure if we are careful about factorizations having several cycles of the same length. For example, the number of permutations in S4 of the form (a b)(c d) is 1 2 1 2 (4 × 3) × 1 2 (2 × 1) = 3, the “extra” factor 1 2 occurring so that we do not count (a b)(c d) = (c d)(a b) twice. The types of permutations in S4 and in S5 are counted in Tables 1 and 2. Here is a computational aid. Lemma 1.7. If γ, α ∈ Sn, then αγα−1 has the same cycle structure as γ. In more detail, if the complete factorization of γ is γ = β1β2 · · · (i1 i2 . . . ) · · · βt,

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.