[经管营销]哈工大ftp资料Chap14课件.ppt

1、1Chapter 14 Polya counting 2Summary Permutation and symmetry groups Burnside theorem Polya counting formula Assignments 3Coloring a regular tetrahedron Suppose to color the four corners of a regular tetrahedron with two colors, red and blue, how many different colorings are there?Case a: the tetrahe

2、dron is fixed in space, then each corner is distinguished from the others by its position, and it matters which color each corner gets. Thus all 16 colors are different. 4Case b: the tetrahedron are allowed to move around. In other words, the corners are indistinguishable. The only way two colorings

3、 can be distinguished from one another is by the number of corners of each color. Thus there are total 5 different colorings. 5Coloring a square Suppose we color the 4 corners of a square with the colors red and blue. How many different colorings are there?6Equivalent and inequivalent coloringsFor b

4、oth the tetrahedron and square, if allowed to freely move around, the 16 ways to color its corners are partitioned into parts in such a way that two colorings in the same part are regarded as the same (the colorings are equivalent), and two colorings in different parts are regarded as different (the

5、 colorings are inequivalent). The number of inequivalent colorings is thus the number of different parts. 7Permutation and symmetry groups8Permutation and function Let X be a finite set. Without loss of generality, we take X to be the set 1, 2, 3, , n. Each permutation i1, i2, i3, , in of X can be v

6、iewed as a one-to-one function from X to itself defined by f: X X , where f(1) = i1, f(2) = i2, ., f(n) = in. A permutation is denoted by a 2-by-n array as follows: niiin21219Example The 3! = 6 permutations of 1, 2, 3 regarded as functions are 12332121332113232131232123132132132110Composition of per

7、mutationsLet are two permutations of 1, 2, , n. Then their composition, in the order f followed by g, is the permutationwhere (g 。f) (k) = g(f(k) = jik. nnjjjngandiiinf21212121nniiinjjjnfg2121212111Binary operation We denote the set of all n! permutations of 1, 2, , n by Sn. Composition of functions

8、 defines a binary operation on Sn: if f and g are in Sn, then g 。f is also in Sn.12Example Let f and g be the permutations in S4 defined by Then, (g。f)(1) = 3, (g 。f)(2) = 4, (g 。f)(3) = 1, (g 。f)(4) = 2, and thus 1342432114234321gandf3412432121434321gfhavealsowefg13Laws on composition operation Ass

9、ociative law: (f 。g) 。h = f 。(g 。h) Commutative law: f 。g g 。f Identity permutation: l(k) = k for all k = 1, 2, , n; Inverse f-1: f-1(k) = s provided f(s) = k. f。f-1 = f-1 。f = l. Composition with itself: f1 = f, f2 = f 。f, , fk = f 。f 。f 。f (k fs)14Getting inverse from the arrayStep 1: interchange

10、rows 1 and 2Step 2: rearrange columns so that the integers 1, 2, , n in the first row occur in the natural orderDefine f0 = l. The inverse of the identity permutation is itself: l-1 = l. 15Example Consider the permutation in S6 given byThen interchange rows 1 and 2, we get Rearranging columns we get

11、 .421365654321f.654321421365.2163546543211f16Permutation groupA permutation group, is defined to be a non-empty subset G of permutations in Sn, satisfying the following three properties:(i)(closure under composition) For all permutations f and g in G, f。g is also in G.(ii) (identity) The identity pe

12、rmutation l of Sn belongs to G.(iii) (closure under inverses) For each permutation f in G, the inverse f-1 is also in G.17Symmetric groupThe set Sn of all permutations of X = 1, 2, , n is a permutation group, called the semmetric group of order n. The set G =l consisting only of the identity permuta

13、tion is a permutation group.18Cancellation lawEvery permutation group satisfies the cancellation law This is because we may apply f-1 to both sides of the equation and, using the association law. hghfgf19Examples let n be a positive integer and let pn denote the permutation of 1,2,n defined by thus

14、pn(i) = i+1 for i = 1, 2, , n-1 and pn(n) = 1. think of the integers from 1 to n as evenly spaced around a circle or on the corners of a regular n-gon, as shown, for n = 8, in the figure.14321321nnnn20 Indeed we may consider pn as the rotation of the circle by an angle of 360/n degree. The permutati

15、on pn2 is then the rotation by 2 (360/n) degree, and more generally, for each non-nagative integer k, pnk is the rotation by k (360/n) degree. 1234567821If r equals k mod n, then pnr = pnk. Thus there are only n distinct powers of pn, namely, pn0 = l, pn, pn2, , pnn-1. Also pn-1 = pnn-1, and more ge

16、nerally, (pnk)-1 = pnn-k for k = 0, 1, , n-1.We thus conclude that Cn = pn0 = l, pn, pn2,pnn-1 is a permutation group. It is an example of a cyclic group of order n.22Symmetry Let Q be a geometrical figure. A symmetry of Q is a (geometric) motion that brings the figure Q onto itself. The geometric f

17、igures like a square, a tetrahedron, and a cube are composed of corners (or vertices) and edges, and in the case of three-dimensional figure, of faces (or sides). As a result, each symmetry acts as a permutation on the corners, on the edges, and in the case of three dimensional figures, on the faces

18、. 23Symmetry groupsWe conclude that the symmetries of Q act as a permutation group GC on its corners (called corner-symmetry group), a permutation group GE on its edges (called edge-symmetry group), and in the case Q is three dimensional, a permutation group GF on its faces (called face-symmetry gro

19、up).24Example Consider the following square Q with its corners labeled 1, 2, 3, 4 and edges labeled a, b, c and d. There are 8 symmetries of Q and they are of two types. There are the 4 rotations about the corner of the square through the angles of 0, 90, 180, and 270 degrees. 1243abcdThese 4 symmet

20、ries constitute the planer symmetries of Q, the symmetries where the motion takes place in the plane containing Q. The planer symmetries by themselves form a group. 25The other symmetries are the four reflections about the lines joining opposite corners and the lines joining the midpoints of opposit

21、e sides. For these symmetries the motion takes place in space since to “flip” the square one needs to go outside of the plane containing it.The rotations acting on the corners give the four permutations1243abcd.321443212143432114324321432143213424404l26 The reflections acting on the corners give the

22、 four permutations Thus the corner-symmetry group of a square is GC = p40=l, p4, p42, p43, r1, r2, r3, r4. .123443213412432141234321234143214321rrrr1243abcd27 Consider the edges of Q to be labeled a, b, c and d in the figure. The edge-symmetry group GE is obtained from the corner-symmetry group GC b

23、y replacing 1, with a, 2 with b, 3 with c and 4 with d. Thus, for instance, doing this replacement in r2, we get and this is the permutation of the edges that results when the square is reflected about the midpoints of the lines b and d.dabcdcba1243abcd28Dihedral group In a similar way we can obtain

24、 the symmetry group of a regular n-gon for any n 3. Besides the n rotations pn0=l, pn, pn2, ,pnn-1, we have n reflections r1, r2, , rn. If n is even, then there are n/2 reflections about opposite corners and n/2 reflections about the lines joining the midpoints of opposite sides. If n is odd, then t

25、he reflections are the n reflections about the lines joining a corner to the side opposite it. The resulting group GC = pn0=l, pn, pn2, pnn-1, r1, r2, , rn of 2n permutations of 1, 2, , n is an instance of a dihedral group of order 2n.29Example Consider the regular pentagon with its vertices labeled

26、 1, 2, 3, 4 and 5. Its corner symmetry group D5 contains 5 rotations. The 5 rotations are .43215543213215454321215435432115432543215432154321453525505l1234530Let ri denote the reflection about the line joining corner i to the side opposite it (i = 1, 2, 3, 4, 5). Then we have .5123454321345125432112

27、345543214512354321234515432154321rrrrr1234531Coloring Suppose we have a group G of permutations of a set X where X = 1, 2, , n. A coloring of X is an assignment of a color to each element of X. Let C be a collection of colorings of X.32Equivalent coloring Let G be a group of permutations acting on a

28、 set X. Let C be a collection of colorings of X such that for all f in G and all c in C, the coloring f*c of X is also in C. Thus G acts on C in the sense that it takes colorings in C to colorings in C. Let c1 and c2 be two colorings in C. c1 is equivalent (under the action of G) to c2 provided ther

29、e is a permutation f in G such that f*c1 = c2. 33Example Consider the previous example where GC = p40=l, p4, p42, p43, r1, r2, r3, r4. Let c = R, B, B, R)b1243abcdp4*c43c12abdl*c= cb1243acdp42*c1243abcdp43*cb1243acdr1*c1243acdr2*c4c312adr3*c4123acdr4*c34Burnsides theorem 35Stabilizer Let G(c) = f: f

30、 in G, f*c = c, that is G(c) is the set of all permutations that fix the coloring c. we call G(c) the stabilizer of c. E.g., in the previous example, G(c) = l, r4 is a stabilizer of coloring c = R, B, B, R. We denote C(f) = c: c in C, f*c = c.36Theorem 14.2.1 For each coloring c, the stabilizer G(c)

31、 of c is a permutation group. Moreover, for any permutations f and g in G, g*c = f*c if and only if f-1。g is in G(c).37Corollary 14.2.2 Let c be a coloring in C. the number |f*c: f in G| of colorings that are equivalent to c equals the number |G|/|G(c)| obtained by dividing the number of permutation

32、s in G by the number of permutations in the stabilizer of c.38Burnsides theorem Let G be a group of permutations of X and let C be a set of colorings of X such that f*c is in C for all f in G and all c in G. Then the number N(G, C) of inequivalent colorings in C is given by In words, the number of i

33、nequivalent colorings in C equals the average of the number of colorings fixed by the permutations in G.GffCGCGN. | )(|1),(39Example 1 (counting circular permutations). How many ways are there to arrange n distinct objects in a circle? Hints: the answer is the number of ways to color the corners of

34、a regular n-gon Q with n different colors which are inequivalent with respect to the group of rotations of Q. 40 Let C consist of all n! ways to color the n corners of Q in which each of the n colors occurs once. Then the cyclic group Cn = pn0 = l, pn, pn2, , pnn-1 acts on C, and the number of circu

35、lar permutations equals the number of inequivalent colorings in C. The identity permutation l in Cn fixes all n! colorings in C. every other permutation in C does not fix any coloring in C since in the colorings of C every corner has a different color. Hence, by Burnsides theorem, N(Cn, C) = 1/n (n!

36、+0+0) = (n-1)!.41Example 2 (counting necklaces). How many ways are there to arrange n 3 differently colored beads in a necklace? Hints: it is almost the same as previous example except that necklace can be flipped over. The group G of permutations now has to be taken to be the entire vertex-symmetry

37、 group of a regular n-gon. Thus in this case G is the dihedral group Dn of order 2n. The only permutation that can fix a coloring is the identity and it fixes all n! colorings. Hence, N(Dn, C) = 1/2n (n!+0+0) = (n-1)!/2.42Example 3 How many inequivalent ways are there to color the corners of a regul

38、ar 5-gon with the colors red and blue? Hints: The group of symmetries of a regular 5-gon is the dihedral group D5=p50=l, p5, p52, p53, p54, r1, r2, r3, r4, r5 (see the example in page 29-30). Let C be the set of all 25 = 32 colorings of the corners of a regular 5-gon. We compute the number of colori

39、ngs left fixed by each permutation in D5 and then apply Burnsides theorem.43 The identity l fixes all colorings. Each of the other 4 rotations fixes only two colorings, namely, the coloring in which all corners are red, and the coloring in which all corners are blue. Thus, |C(p50)| = 32 and |C(p5i)|

40、 = 2 where i = 1, 2, 3, 4. Now consider any of the reflections, say r1. In order that a coloring be fixed by r1, corners 2 and 5 must have the same color and corners 3 and 4 must have the same color. Hence, the colorings fixed by r1 are obtained by picking a color for corner 1 (two choice), picking

41、a color for 2 and 5 (two choice) and picking a color for corners 3 and 4 (again two choices). Hence the number of colorings fixed by r1 equals 8. A similar calculation holds for each reflection and hence |C(rj)| = 8 for eac hj = 1, 2, 3, 4, 5. Therefore, the number of inequivalent colorings is N(D5,

42、 C) = 1/10 (32+24 + 8 5) = 8.44Example 4 How many inequivalent ways are there to color the corners of a regular 5-gon with the colors red, blue, and green? Hints: refer to example 3. now the set C of all colorings number 35 = 243. The identity fixes all 243 colorings. Every other rotation fixes only

43、 3 colorings. Each reflection fixes 333=27 colorings. Hence N(D5, C) = 1/10 (243+34+275) = 39.45Exercise How many inequivalent ways are there to color the corners of a regular 5-gon with p colors? Answer: 1/10 (p5+4p+5p3)46Example 5 Let S = r, b, g, y be multiset of four distinct objects r, b, g, y,

44、 each with an infinite repetition number. How many n-permutations of S are there if we do not distinguish between a permutation read from left to right and the permutation read from right to left? Thus for instance, r, g, g, g, b, y, y is regarded as equivalent to y, y, b, g, g, g, r.47Solution The

45、answer is the number of inequivalent ways to color the integers from 1 to n with the four colors red, blue, green and yellow under the action of the group of permutations G = l, r, where .1211212121nnnnrandnnl48 Note that G is a group. Why? Let C be the set of all 4n ways to color the integers from

46、1 to n with the given four colors. Then l fixes all colorings in C. The number of colorings fixed by r depends on whether n is even or odd. First, suppose n is even. Then a coloring is fixed by r iff 1 and n have the same color, 2 and n-1 have the same color, ., n/2 and n/2+1 have the same color. He

47、nce r fixes 4n/2 colorings in C. Now suppose that n is odd. Then a coloring is fixed by r iff 1 and n have the same color, 2 and n-1 have the same color, , (n-1)/2 and (n+3)/2 have the same color. 244),(21 nnCGN Hence the number of colorings fixed by r is 4(n-1)/24 = 4(n+1)/2. Thus 49Exercise If ins

48、tead of four color, we have p colors, what is the number of inequivalent colorings? Answer: 2),(21 nnppCGN50Polyas counting formula51Factorization Let be a permutation of the set 1,2,3,4,5,6,7,8. Then f has a factorization as follows:7231458687654321f.478253617231458687654321f52Cycle factorization L

49、et f be any permutation of the set X. Then with respect to the operation of composition f has a factorization f = i1 i2 ip。j1 j2 . jq 。l1 l2lr into cycles where each integer in X occurs in exactly one of the cycles. We call it cycle factorization of f. The cycle factorization of f is unique apart fr

50、om the order in which the cycles appear, and this order is arbitrary. Every element of X occurs exactly once in the cycle factorization.53Example 1 Determine the cycle factorization of each permutation in the dihedral group D4 of order 8 (the corner symmetry group of a square).D4Cycle factorizationp