chapter  11
20 Pages

Permutations

Let n be a positive integer. A permutation is a one-to-one and onto function (i.e., a bijection) from the set {1,2, . . . ,n} to itself. The set of all permutations of this set is denoted Sn. One way to represent a permutation pi is as a list of values [pi(1),pi(2), . . . ,pi(n)].

For example, pi = [1,4,7,2,5,3,6] means pi ∈ S7 and pi(1) = 1, pi(2) = 4, pi(3) = 7, and so on, and pi(7) = 6. The disjoint cycle notation is an alternative way to write permutations. The permu-

tation pi = [1,4,7,2,5,3,6] is written (1)(2,4)(3,7,6,5). The (1) means pi(1) = 1. The (2,4) means pi(2) = 4 and pi(4) = 2. The (3,7,6,5) means pi(3) = 7, pi(7) = 6, pi(6) = 5, and pi(5) = 3. In other words, (1)(2,4)(3,7,6,5) means this: