Permutations, Cycle Structure and Symmetric Groups

A permutation of a set X is a bijection from X to itself. In high school mathematics, a permutation of a set X is defined as a rearrangement of its elements. For example, there are six rearrangements of X = {1, 2, 3}: 123; 132; 213; 231; 312; 321. Now let X = {1, 2, . . . , n}. A rearrangement is a list, with no repetitions, of all the elements of X. All we can do with such lists is count them, and there are exactly n! permutations of the n-element set X. Now a rearrangement i1, i2, . . . , in of X determines a function α : X →X, namely, α(1) = i1, α(2) = i2, . . . , α(n) = in. For example, the rearrangement 213 determines the function α with α(1) = 2, α(2) = 1, and α(3) = 3. We use a two-rowed notation to denote the function corresponding to a rearrangement; if α( j) is the jth item on the list, then α = 1 . . . j . . . n α(1) α(2) . . . α( j) . . . α(n) . That a list contains all the elements of X says that the corresponding function α is surjective, for the bottom row is im α; that there are no repetitions on the list says that distinct points have distinct values; that is, α is injective. Thus, each list determines a bijection α : X →X; that is, each rearrangement determines a permutation. Conversely, every permutation α determines a rearrangement, namely, the list α(1), α(2), . . . , α(n) displayed as the bottom row. Therefore, rearrangement and permutation are simply different ways of describing the same thing.

The family of all the permutations of a set X, denoted by SX, is called the symmetric group on X. When X = {1, 2, . . . , n}, SX is usually denoted by Sn, and it is called the symmetric group on n letters. Let us simplify notation by writing βα instead of β ◦α and (1) instead of 1X. Notice that composition in S3 is not commutative. Aside from being cumbersome, there is a major problem with the two-rowed notation for permutations. It hides the answers to elementary questions such as, Do two permutations commute? Is the square of a permutation the identity? The special permutations introduced next will remedy this defect. Permutations

Two permutations α, β ∈Sn are disjoint if every i moved by one is fixed by the other: If α(i) ̸= i, then β(i) = i, and if β( j) ̸= j, then α( j) = j. A family β1 . . . , βt of permutations is disjoint if each pair of them is disjoint.

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, the complete factorization of the 3-cycle α = (1 3 5) in S5 is α = (1 3 5)(2)(4). There is a relation between 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 k < r.

A permutation α ∈Sn is even if it can be factored into a product of an even number of transpositions; otherwise, α is odd. The parity of a permutation is whether it is even or odd. On the other hand, we do not yet have any examples of odd permutations! If α is a product of an odd number of transpositions, perhaps it also has some other factorization into an even number of transpositions. The definition of odd permutation α, after all, says that there is no factorization of α into an even number of transpositions.

If α ∈Sn and α = β1 · · · βt is a complete factorization into disjoint cycles, then signum α is defined by sgn(α) = (−1)n−t.

A binary operation on a set G is a function ∗: G × G →G. In more detail, a binary operation assigns an element ∗(x, y) in G to each ordered pair (x, y) of elements in G. It is more natural to write x ∗y instead of ∗(x, y); thus, composition of functions is the function (g, f ) ↦g ◦f ; multiplication, addition, and subtraction are, respectively, the functions (x, y) ↦xy, (x, y) ↦x + y, and (x, y) ↦ x −y. The examples of composition and subtraction show why we want ordered pairs, for x ∗y and y ∗x may be distinct. As with any function, a binary operation is well-defined; when one says this explicitly, it is usually called the law of substitution: If x = x′ and y = y′, then x ∗y = x′ ∗y′.

A group is a set G equipped with a binary operation ∗such that (i) the associative law holds: for every x, y, z ∈G, x ∗(y ∗z) = (x ∗y) ∗z; (ii) there is an element e ∈G, called the identity, with e ∗x = x = x ∗e for all x ∈G; (iii) every x ∈G has an inverse; there is x′ ∈G with x ∗x′ = e = x′ ∗x.

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 .

(i) The inverse of the cycle α = (i1 i2 . . . ir) is the cycle (ir ir−1 . . . i1): (i1 i2 . . . ir)−1 = (ir ir−1 . . . i1). (ii) If γ ∈Sn and γ = β1 · · · βk, then γ −1 = β−1 k · · · β−1 1 .

If γ, α ∈Sn, then αγ α−1 has the same cycle structure as γ . In more detail, if the complete factorization of γ is γ = β1β2 · · · (i1 i2 . . . ) · · · βt, then αγ α−1 is the permutation that is obtained from γ by applying α to the symbols in the cycles of γ .

Permutations γ and σ in Sn have the same cycle structure if and only if there exists α ∈Sn with σ = αγ α−1.

shows that sgn is a (well-defined) function, for the number t is uniquely determined by α. Notice that sgn(ε) = 1 for every 1-cycle ε because t = n. If τ is a transposition, then it moves two numbers, and it fixes each of the n −2 other numbers; therefore, t = (n −2) + 1 = n −1, and so sgn(τ) = (−1)n−(n−1) = −1.

(i) Let α ∈Sn; if sgn(α) = 1, then α is even, and if sgn(α) = −1, then α is odd. (ii) A permutation α is odd if and only if it is a product of an odd number of transpositions.

Let α, β ∈Sn. If α and β have the same parity, then αβ is even, while if α and β have distinct parity, then αβ is odd.

(i) The types of permutations in G = S4 are counted in Table 2.1. Cycle Structure Number (1) (1 2) (1 2 3) (1 2 3 4) (1 2)(3 4) Table 2.1. Permutations in S4 Permutations (ii) The types of permutations in G = S5 are counted in Table 2.2. Cycle Structure Number (1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2)(3 4 5) (1 2)(3 4) Table 2.2. Permutations in S5 ◀ Here is a computational aid. We illustrate its statement in the following example before stating the general result.

An analysis of the 15-puzzle in Example 2.11 shows that if α ∈S16 is the starting position, then the game can be won if and only if α is an even permutation that fixes 16. The proof in one direction is fairly clear, however. The blank 16 starts in position 16. Each simple move takes 16 up, down, left, or right. Thus, the total number m of moves is u + d + l + r, where u is the number of up moves, and so on. If 16 is to return home, each one of these must be undone: There must be the same number of up moves as down moves (i.e., u = d) and the same number of left moves as right moves (i.e., r = l). Thus, the total number of moves is even: m = 2u + 2r. That is, if τm · · · τ1α = (1), then m is even; hence, α = τ1 · · · τm (because τ −1 = τ for every transposition τ), and so α is an even permutation. In Example 2.11, α = (1 3 4 8 9 2 15 14 7)(5 10)(6 11 13)(12)(16) [(12) and (16) are 1-cycles]. Now sgn(α) = (−1)16−5 = −1, so that α is an odd permutation. Therefore, it is impossible to win this game. ◀