复旦大学：《离散数学 Discrete Mathematics（上）》英文课件（赵一鸣）23/30

Theorem 6.6: Let G; be a group and let a and b be elements of g. then ()ac=bc, implies that a=b(right cancellation property) (2)ca=cb, implies that a=bo (left cancellation property) s=a1ym,÷) Thus there can be no repeats in any row or column

Theorem 6.6: Let [G;] be a group and let a and b be elements of G. Then (1)ac=bc, implies that a=b(right cancellation property)。 (2)ca=cb, implies that a=b。(left cancellation property) S={a1 ,…,an }, al*aial*aj (ij)， Thus there can be no repeats in any row or column

Theorem 6.7: Let G; be a group and let a. b and c be elements of g. then (lThe equation a*x=b has a unique solution in g (2)The equation y*a=b has a unique solution in g

Theorem 6.7: Let [G;] be a group and let a, b, and c be elements of G. Then (1)The equation ax=b has a unique solution in G. (2)The equation ya=b has a unique solution in G

Let [G; be a group. We define a=e a-k=(a-k, ak-a*ak-l(k21 Theorem 6.8: Let G; be a group and a ∈G,m,n∈Z.Then (amran=aman (2)(am)=am ata+.ta=ma ma+na=(m+n)a n(ma=(nm)a

Let [G;] be a group. We define a 0=e， a -k=(a-1 ) k ， a k=a*ak-1 (k≥1) Theorem 6.8: Let [G;] be a group and a G, m,n Z. Then (1)a m*a n=am+n (2)(am) n=amn a+a+…+a=ma, ma+na=(m+n)a n(ma)=(nm)a

6.3 Permutation groups and cyclic groups Exampl ole: Consider the equilateral triangle with vertices 1, 2, and3. Let l1, L2, and l3 be the angle bisectors of the corresponding angles, and let o be their point of intersection Counterclockwise rotation of the triangle about o through120°,240°,360°(0

6.3 Permutation groups and cyclic groups Example: Consider the equilateral triangle with vertices 1，2，and 3. Let l1 , l2 , and l3 be the angle bisectors of the corresponding angles, and let O be their point of intersection。 Counterclockwise rotation of the triangle about O through 120°,240°,360° (0°)

f2:1→>2,2)3,3→1 3:1→)3,2-1,3-)2 f1:1-1,2-)2,3-3 reflect the lines l1, l2, and L3. g1:1→>1,2-~3,3>2 g2:1→3,2→>2,3-+1 83:1→>2,2→1,3)3

f2 :1→2，2→3，3→1 f3 :1→3，2→1，3→2 f1 :1→1，2→2，3→3 reflect the lines l1 , l2 , and l3 . g1 :1→1，2→3，3→2 g2 :1→3，2→2，3→1 g3 :1→2，2→1，3→3

6.3.1 Permutation groups Definition 9: A bijection from a set S to itself is called a permutation of s Lemma 6.1: lets be a set (1) Let and g be two permutations of s. Then the composition off and g is a permutation of s. (2) Let f be a permutation of s. Then the inverse off is a permutation of s

6.3.1 Permutation groups Definition 9: A bijection from a set S to itself is called a permutation of S Lemma 6.1：Let S be a set. (1) Let f and g be two permutations of S. Then the composition of f and g is a permutation of S. (2) Let f be a permutation of S. Then the inverse of f is a permutation of S

Theorem 6.9: Let s be a set. The set of all permutations of S, under the operation of composition of permutations, forms a group A(S) Proof: Lemma 6.1 implies that the rule of multiplication is well-defined associative the identity function from S to s is identity element The inverse permutation g off is a permutation of s

Theorem 6.9：Let S be a set. The set of all permutations of S, under the operation of composition of permutations, forms a group A(S). Proof: Lemma 6.1 implies that the rule of multiplication is well-defined. associative. the identity function from S to S is identity element The inverse permutation g of f is a permutation of S

Theorem 6.10: Let s be a finite set with n elements. Then A(S) has n! elements Definition 10: The group s is the set of permutations of the first n natural numbers. The group is called the symmetric group on n letters, is called also the permutation group

Theorem 6.10: Let S be a finite set with n elements. Then A(S) has n! elements. Definition 10: The group Sn is the set of permutations of the first n natural numbers. The group is called the symmetric group on n letters, is called also the permutation group

(1)a(2)…(m) σ(1)a(2)…σ(m)(o(i)(2)…σ(ln)

        = (1) (2) ( ) 1 2 n n               =        = (1) (2) ( ) ( ) ( ) ( ) 1 2 1 2 1 2 n n i i i i i i n n           

12 n identity permutation e 12 σ(1)a(2)…a(n) inverse permutation of oo 12 2 σ4(1)a-(2)…a(n)

        =         =         = − − − − − σ (1) σ (2) σ (n) 1 2 n σ 1 2 n σ(1) σ(2) σ(n) σ 1 2 n 1 2 n e 1 1 1 1 1       inverse permutation of  identity permutation