《Discrete Mathematics II教学-华南理工》Lecture 8 Groups of Permutations.pdfVIP

II.8 Groups of Permutations 1 Part II. Permutations, Cosets, and Direct Products Section II.8. Groups of Permutations Note. In this section, we introduce groups which consist of functions acting on sets of elements. In particular, we consider how a set of n elements can be permuted around. Recall that a permutation of a set on n elements is a way to arrange the n elements. The number of ways to arrange (or order) n elements from a set of size n is n! = n(n − 1)(n − 2) · · · (3)(2)(1). Note. A fundamental result of this section is that every group is related to a group of permutations (see Theorem 8.16, Cayley’s Theorem, for details). So there is something very fundamental about groups of permutations. Note. We use lower case Greek letters to represent permutations. First, by defi- nition, we have: Definition 8.3. A permutation of a set A is a function φ : A → A that is both one-to-one and onto. Lemma. If σ and τ are permutations on set A, then the composite function σ ◦ τ τ σ (defined as A → A → A) is a permutation on A. Normally we drop the composition symbol ◦ and write σ ◦ τ = στ . Notice that we must read this from right to left since στ is permutation τ first, followed by permutation σ. II.8 Groups of Permutations 2 Note. Since we can compose permutations on a given set A, then permutation composition (called permutation multiplication) is a binary operation on the set S of all permutations of set A. As we’ll see, this binary structure is, in fact, a group. Note. The standard notation for a permutation on a finite set is to write the elements of the set as the first row of a matrix and the corresponding images of the elements as the second ro