李凡长版组合数学课后习题答案习题.doc

《李凡长版组合数学课后习题答案习题.doc》由会员分享，可在线阅读，更多相关《李凡长版组合数学课后习题答案习题.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 Plya计数理论1.计算12323451423,并指出它的共轭类.解：题中消灭了 5 个不同的元素：分别是：1，2，3，4，5。即|Sn|5。 1234512345 12345 2314342321512345 12345 34123215(123)(234)(5)(14)(23)=515 4=5 4 21435= 12345= (12)(34)(5)4151234的置换的型为 1122 而 Sn中属于 1122 型的元素个数为5!= 152!1!11 22个其共轭类为51423，51324，12345，12435，12534，21345，21435，21534，31245，31425

2、，31524，41235，41325，415242. 设 D 是 n 元集合,G 是 D 上的置换群.对于 D 的子集 A 和 B,假设存在s G ,使得 B = s (a) | a A,则称 A 与 B 是等价的.求 G 的等价类的个数.G解：依据 Burnside 引理l =1 n c(a ) ，其中 c(a )表示在置换 a作用下保持不变的元素个数，则有1i1iii=1c1()=n;I设在 的作用下，A 的元素在 B 中的个数为 i，则c2( )=n2i；假设没有其他置换，则 G 诱出来的等价类个数为 l= 1 n + (n - 2i) = n - i23. 由 0,1,6,8,9 组成

3、的 n 位数,假设把一个数调转过来读得到另一个数,则称这两个数是相等的.例如,0168 和 8910,0890 与 0680 是相等的.问不相等的 n 位数有多少个？解：该题可理解为相当于n 位数，0，1，6，8，9 这 5 个数存在确定的置换关系对于置换群 G=g1,g2g1 为不动点置换，型为 1n；为 5n；g 置换：1n(2(n-1)(3(n-2)( n n )2 2 2 分为 2 种状况：n（1） n 为奇数时12 2，但是只有中间的数字是 0，1，8 的时候，才可能调转过来的时候是一样的，所以这里的剩下的中间数字只能是有 3 种。即：个数为 3 5n -1 2n（2） n 为偶数时

4、 2 2n，个数为 52该置换群的轮换指标为1n13nn 为偶数时，等价类的个数 l= 2 (5n+ 52 ) =5 221n 为奇数时，等价类的个数 l= 2 (5n+ 3 5n-12 )4. 现有 8 个人打算去访问 3 个城市,其中有 3 个人是一家,另外有 2 个人是一家. 假设一家人必需去同一个城市,问有多少种方案？写出它们的模式.解：令 D=d1,d2,d8，其中，d1,d2,d3 为一家，d4,d5 为一家。R=c1,c2,c3,w(c1)= ,w(c )= ,w(c )= .f:DR 是一种安排方案。依据题意，做 D 的一个 523分划 d1,d2,d3,d4,d5,d6,d7

5、,d8,要求 f 在每块中的元素取值一样。对于d1,d2,d3，可以取 3 3 3 模式； 对于d4,d5 ，可以取 2 2 2 模式；对于d6,d7,d8，可以取 模式.所以，总的模式为 3 3 3 2 2 2 35. 对正立方体 6 个面用红、蓝、绿 3 种颜色进展着色,问有多少种不同的方案？ 又问 3 种颜色各消灭 2 次的着色方案有多少种？解：正立方体 6 个面的置换群G 有 24 个元素，它们是：（1） 不动的置换，型为 16，有一个；（2） 绕相对两面中心轴旋转 90，270的置换，型为 1241，有 6 个；旋转 180的置换，型为 1222，有 3 个；（3） 绕相对两顶点连线

6、旋转 120，240的置换，型为 32，有 8 个；（4） 绕相对两边中点连线旋转 180的置换，型为 23，有 6 个。所以，该置换群的轮换指标为xPG 1,x2,x6= 124(x 6 + 6x 2 x 114+3x 2 x122 + 8x32 + 6x 3 )2等价类的个数为l=PG(3,3,3)=1(3624+ 6 33 + 3 32 32 + 8 32 + 6 33 ) =57下面计算全部着色模式。这里， R=c1,c2,c3，w(c1)=r，w(c2)=b，w(c3)=g， 于是F 的全部模式表1(r + b + g) 6 + 6(r + b + g) 2 (r 4 + b 4 +

7、 g 4 ) + 3(r + b + g) 2 (r 2 + b 2 + g 2 ) 224+ 8(r 3+ b 3 + g 3 ) 2+ 6(r 2+ b 2+ g 2 ) 3 其中，红色、蓝色、绿色各消灭2 次的方案数就是上述开放式中 r2b2g2 项的系数，即1 (6!+ 3 2 + 6 3! ) = 6242!2!2!1!1!1!6. 有一个 33 的正方形棋盘,假设用红蓝两色对这 9 个方格进展着色,要求两个位红色,其余为蓝色,问有多少种方案？解： 其置换群为：不动置换：型为 19，1 个沿中间格子及其对角线方向做旋转的置换：型为 1323，4 个旋转 90和 240时的置换：型为

8、1142 ， 2 个旋转 180时的置换 型为 1124， 1 个1 P(x)= 8(1+ x)9+ 4(1+ x)3 (1+ x 2 )3+ 2(1+ x)(1+ x 4 ) 2+ (1+ x)(1+ x 2 ) 4我们设定 x 为红色，1 为蓝色，即转化为求 x2 的系数1 对应于 19，1x9 中 x2 项系数为 C(9,2)=36；2 对应于 1323，4(1x)3(1+x2)3 中x2 项系数为： 4C(3,2)C(3,0)+C(3,0)C(3,1)=24；3 对应于 11422(1+x)(1+x4)2 中x2 项系数为 0；4 对应于 1124(1+x)(1+x2)4 中x2 项系

9、数为C(4,1)=4；故 x2 的系数为1 (36 + 24 + 4) = 887. 对正六角形的 6 个顶点用 5 种颜色进展着色.试问有多少种不同的方案,旋转使之重合作为一样处理.解：对该正六角形的 6 的顶点的置换群有 12 个，它们分别是：(1) 不动点置换，型为 16，有 1 个；(2) 旋转 60和 300的置换，型为 61，有 2 个；旋转 120和 240的置换， 型为 32，有 2 个； 旋转 180的置换型为 23 有 1 个；(3) 绕对角连线旋转 180的置换 ，型为 1222，有 3 个；(4) 绕对边中点连线旋转 180的置换，型为 23，有 3 个。所以，该置换群

10、的轮换指标为1P x ,x ,x =(x 6 + 2x+ 2x 2 + 3x 2 x 2 + 3x 3 )G12612163122下面计算全部着色模式。这里，R=c1,c2,c3,c4,c5，不妨设 w(c1)=r，w(c2)=b， w(c3)=g，w(c4)=p，w(c3)=y，于是F 的全部模式表1(r + b + g + p + y)6 + 2(r 6 + b6 + g 6 + p 6 + y 6 ) + 2(r 3 + b3 + g 3 + p3 + y 3 )212+ 3(r 2 + b2 + g 2 + p 2 + y 2 )(r 2 + b2 + g 2 + p 2 + y 2

11、)2 + 3(r 2 + b2 + g 2 + p 2 + y 2 )3 其中，用这 5 种颜色着色的方案数就是上述开放式中r2bgpy, rb2gpy, rbg2py,rbgp2y, rbgpy2 项的系数之和，即1 (5 6!) = 150122!1!1!1!1!8. 在一个有7 匹马的旋转木马上用n 种颜色着色,问有多少种可供选择的方案？旋转木马只能转动不能翻转解： 设想另一个正 7 边形与不动的正 7 边形完全重合，并且顶点标记一样，那么绕中心旋转 360o7i 1i7角度，使得能够与不动的正7 边形重合。它对应的置换是：71 共 6 个。故其轮换指标为1PG(x1,x2,xn)=(x

12、 771+ 6x )7计算全部着色模式为 1 (x + x+ . + x ) 7 + 6(x7 + x 7 + . + x7 )711 7!2n C(7, n) =12n6!7! n7 时为 71!1!.7 - (n -1)!(8 - n)!n!(7 - n)!9. 一个圆圈上有 n 个珠子,用 n 种颜色对珠子着色,要求颜色数目不少于 n 的方案数是多少?解：1不动点置换有一个；（2） 绕中心旋转360oni 1in角度，使得能够与不动的环重合。它对应的置换是：n1 共(n1)个；（3） 把 n 为奇数、偶数分两种状况分析：i) n 为奇数时：沿一颗珠子和其他剩余珠子的平分线绕 180，对应

13、的置n-1换是112 2 共 n 个；nii) n 为偶数时：沿珠子平分线绕 180，对应的置换是 2 22故其轮换指标为，共 n 个。2PG(x1,x2,xn)=1 (x n2n1+ (n -1)xn+ nx x12n-1 ) n 为奇数时；P (x,x ,x )= 2 (xnn + (n -1)x+xn ) n 为偶数时；G12n3n1n22 210. 骰子的 6 个面上分别标有 1,2,6,问有多少种不同的骰子？ 解：下面有 3 种方法求解：方法 1 6 个面分别标上不同的点数，相当于用 6 种不同的颜色对它着色， 并且每种颜色消灭且只消灭一次，共有 6！种方案。但这种方案经过正立方体的

14、旋转可能会发生重合，全部方案上的置换群 G 明显有 24 个元素。由于每个面的着色全不一样，只有恒等置换 I 保持 6！种方案不变，即 c1( I)=6!，Ic1(p)=0p 。由 Burnside 引理知Gl = 1 cpG 1(p ) = 124(6!+0 + 0) = 30方法 2在习题 5 中已求出关于正立方体 6 个面的置换群轮换指标，假设用m 种颜色进展着色，则不同的着色方案数为1l=m24(m6 + 3 m 4 +12 m3 + 8 m 2 )严格的说， lm是至多用 m种颜色着色的方案数。我们可以计算出351246l =1,l =10,l =57,l =240,l=800,l=

15、2226。现令ni表示恰好用 i 种颜色着色的方案数，则由容斥原理知11n =l =122 1 1n= l- 2 n= 8 3 3n3 = l3 - 2 n2 - 1= 30n1 4 4 4n4 = l4 - 3 n3 - 2 -= 68nn2 1 1 5 5 5 5n5 = l5 - 4 n4 - 3-= 75nnn3 2 21 1 6 6 6 6 6 n6 = l6 - 5 n5 - 4 n4 - 3 n3 - 2 n2 - 1 n1 = 30方法 3 令 R=c ,c ,c ，w(c )=w (1i6)。正立方体 6 个面上的置换126ii群 G 的轮换指标为1) =PG(x1,x2,x

16、6(x 6241+ 6x 2 x14+3x 2 x 212+ 8x 23+ 6x 3 )2于是 F 的全部模式表为LP ( w(r), w 2 (r), w 6 (r)GrRrRrR 1LLLLL=(w 241+ + w6) 6 + 6(w1+ + w6)(w 41+ + w64 ) + 3(w1+ + w6) 2 (w 21+ + w62 ) 2L+ 8(w 3 + w163 ) 2+ 6(w 21+ + wL62 )3 其中，w1w2w3w4w5w6 项的系数就是用 6 种颜色对 6 个面着色的方案数，等于1 6!= 3024 1!1!L1!11. 将两个一样的白球和两个一样的黑球放入两个

17、不同的盒子里 ,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？解： 令 D=w1,w2,b1,b2,R=盒 1，盒2，四个球往两个盒子里放的放法是F：DR。由于 w1,w2 是两个一样的白球，b1,b2 是两个一样的黑球，由此确定出D 上的置换群为G=I,(w1w2),(b1b2),(w1w2)(b1b2)其轮换指标为PG(x1,x2,x3,x4) = 1 (x 441+ 2x 2 x12+x 2 )2于是 F 上的等价类个数为1l=P(2,2,2,2)=(24+ 2 22 2 + 22 ) = 9G4这 9 个不同方案分别为(， wwbb), ( w,wbb), (b

18、,wwb), (ww,bb), (wb,wb), (wwbb, ), (wbb,w), (wwb,b), (bb,ww)令 w(盒 1)x，w(盒 2)y，则 F 上的全部模式表为P (x+y,x2+y2,x3+y3,x4+y4) = 1 (x + y) 4 + 2(x + y) 2 (x 2 + y 2 ) + (x 2 + y 2 ) 2 )G4=x4+2x3y+3x2y2+2xy3+y4盒 1 与盒 2 中各放两个球的方案数是 x2y2 项的系数，即为 3。具体方案为(ww,bb), (wb,wb), (bb,ww)12. 将 2 个红球和 2 个蓝球放在正六面体的顶点上,问有多少种不同

19、的方案？ 解： 正立方体 8 个点的置换群G 有 24 个元素，它们是：（1） 不动的置换，型为 18，有 1 个；（2） 绕相对两面中心轴旋转 90，270的置换，型为 42，有 6 个；旋转180的置换，型为 24，有 3 个；（3） 绕相对两顶点连线旋转 120，240的置换，型为 1232，有 8 个；（4） 绕相对两边中点连线旋转 180的置换，型为 24，有 6 个。所以，该置换群的轮换指标为P x ,x ,x= 1 (x8 + 6x2 + 8x 2 x 2 + 9x 4 )G1262414132下面计算全部着色模式。这里，假设除了红色和蓝色外我们放绿球，则R=c1,c2,c3，w

20、(c1)=r，w(c2)=b，w(c3)=g，于是F 的全部模式表1(r + b + g)8 + 6(r 4 + b 4 + g 4 ) 2 + 8(r + b + g) 2 (r 3 + b3 + g 3 ) 2 + 9(r 2 + b 2 + g 2 ) 4 24其中，红色、蓝色各消灭 2 次的方案数就是上述开放式中 r2b2g4 项的系数， 即 1 ( 8!+ 9 4! ) = 22242!2!4!1!1!2!13. 长为 n 的透亮的方格,用红、蓝、黄、绿 4 种颜色进展着色,试问有多少种不同的方案？解：问题相当于用 r,b,y,g 构成长为 n 的字符串，将从左向右的字符挨次和从右向

21、左的字符挨次看作时一样的，例如，yggrbr 和 rbrggy 看作是一样的。12Ln 12Ln -1n 群 G： 12Ln nn -1L21 依据 Plya 定理，不同的方案数应为：1 n +1 n2N (4+ 4 ) 214. 用两种颜色对正六面体的 6 个面、8 个顶点进展着色,问有多少种不同方案？ 转动使之全都作为一类处理.解：对正六面体的 6 个面的置换群设为G，G 的循环指数多项式为：P(G)= S 6 + 6S 2 S+ 3S 2 S 2 + 6S 3 + 8S 21141223设正六面体 8 个顶点的置换群为 H，H 的循环指数多项式为P(H)= S 8 + 6S 2 + 9S

22、 4 + 8S 2 S 214213 1P(G H)=P(G)P(H)= S 6 + 6S 2 S+ 3S 2 S 2+ 6S 3 + 8S 2 S 8 + 6S 2+ 9S 4+ 8S 2 S 2 (24) 2114122314213=1 S 14(24) 21+ 6S 6 S 2 + 9S 6 S 4 + 8S 8 S 2 + 6S 101412131+ 36S 2 S 3 + 54S 2 S 4 S 14124+ 48S 4 S 3 S+ 3S 10 S 2 12412+18S 2 S 2 S 2+ 27S 2 S 6 + 24S 4 S 2 S 2 + 6S 8 S 3 + 36S 3

23、 S 2+ 54S 7 + 48S 2 S 3 S 2 + 8S 8 S 2 + 48S 2 S 212412123122421231334+ 72S 4 S 4 + 64S 2 S 4 2313所求的不同等价类数为157626 + 6 23 + 3 24 + 6 23 + 8 22 28 + 6 22 + 9 24 + 8 24 = 1 64 + 48 + 48 + 48 + 32256 + 24 +144 + 28576= 1 240 552 = 230 57615. 一个正八面体,用红、蓝两色对 6 个顶点进展着色；用黄、绿两种颜色对 8 个面进展着色,试求其中 4 个顶点为红,两个顶点

24、为蓝,黄和绿的面各 4 面的方案数.注：正八面体可以看作是正方体的对偶，每一面用中心代表一个顶点，相交于一个顶点的 3 个面对应过 3 个中心的三角形，由此构成的 6 个顶点，8 个面的几何图形。即可得到我们需要的正八面体的外形。解：通过刚刚我们的提示可以得到如下结论：可以把问题转换成对于正六面体的顶点和面的着色问题，转换成为要求给这个正六面体着色：用红、蓝两色对6 个面进展着色；用黄、绿两种颜色对 8 个顶点进展着色,试求其中 4 个面为红,2 个面为蓝；黄和绿的顶点各 4 个的方案数.对正六面体的 6 个面的置换群设为 G，G 的循环指数多项式为：P(G)= S 6 + 6S 2 S+ 3

25、S 2 S 2 + 6S 3 + 8S 21141223设正六面体 8 个顶点的置换群为 H，H 的循环指数多项式为P(H)= S 8+ 6S 2+ 9S 4+ 8S 2 S 214213 1P(G H)=P(G)P(H)= S 6 + 6S 2 S+ 3S 2 S 2+ 6S 3 + 8S 2 S 8 + 6S 2+ 9S 4+ 8S 2 S 2 (24) 21所求的不同等价类数为114122314213(r + b) 6 + 6(r + b) 2 (r 4 + b 4 ) + 3(r + b) 2 (r 2 + b 2 ) 2 + 6(r 2 + b 2 )3 + 8(r 3 + b 3

26、) 2 124( y + g)8 + 6( y 4 + g 4 ) 2 + 8( y + g) 2 ( y 3 + g 3 ) 2 + 9( y 2 + g 2 ) 4 24所得的 r4b2y4g4 的系数即为所求：1 6!+ 6 1 + 3(1 +2! ) + 6 3! 1 8!+ 6 2! + 8( 2! 2! ) + 94! =271424 4!2!1!1！2!1!24 4!4!1!1!1!1! 1!1!2!2!所以符合题意的方案数为 14 种。16. 用 Plya 定理求多重集合M = a , a , a 的 r 圆排列数.12n解：可转化为有 r 颗珠子的项链可以着n 种颜色的方法数

27、。1不动点置换有 1 个；360（2） 绕中心旋转i 1ir角度，使得能够与不动的环重合。它对r应的置换是：r1 共(r1)个；（3） 把 r 为奇数、偶数分两种状况分析：i) r 为奇数时：沿一颗珠子和其他剩余珠子的平分线绕 180，对应的置换r -1是112 2 共 r 个；rii) r 为偶数时：沿珠子平分线绕 180，对应的置换是 2 2故其轮换指标为，共 r 个。21PG(x1,x2,xn)=2r1(x r1+ (r -1)x+ rx x r -1 ) r 为奇数时； r12 2r -1= 2r (nr+ (r -1)n + rn n 2 )1= 2r(nr+ (r -1)n + r

28、nr +12 )2rrPG(x1,x2,xn)=(x r31+ (r -1)x+x) r 为偶数时；2r2r22rr=(nr + (r -1)n +n 2 )3r217. 求 n 个顶点的简洁图有多少个？解：简洁图指的是过两个顶点没有多于一条的边，而且不存在圈的图形。问题相当于对 n 个无标志顶点的完全图的 n (n -1) 条边，用两种颜色进展着色，求不2同方案数的问题。比方两种颜色 x,y，令着上色 y 的边从图中消去，得到一n 个顶点的简洁图。例如 3 个顶点的无向图，有G=(v1)(v2)(v3)，(v1v2v3)，(v3v2v1)，(v1)(v2v3)，(v2)(v1v3)，(v3)

29、(v1v2)P(x,y)= 1 (x + y)3 + 3(x + y)(x 2 + y 2 ) + 2(x 3 + y 3 ) 6=x3+y3+xy2+x2yv1v2v3从 P(x,y)可知，对上图的三角形的边着色，其中 3 条边都用 x 着色的有 1； 同样用 x 着色两条的、着色一条的、无一条着色的方案各为 1多项式各项的系数。把用 y 着色的边消退得到以下的图形。再看 n=4 的状况.令 e1=(v1v2)，e2=(v2v3)，e3=(v3v4)，e4=(v4v1)，e5=(v1v3)， e6=(v2v4)，则v1,v2,v3,v4上的每个置换确定了e1,e2,e3,e4,e5,e6上的

30、置换，后者构成边集合上的置换群 G. G 中有 16 型的置换 1 个，1222 型的置换 9 个，32 型的置换 8 个，2141 型的置换 6 个.G 的轮换指标为：PG(x1,x2,x6)= 124(x 6 + 9x 2 x 1122 + 8x32 + 6x x )2 4令 R=x, y，w(x)=r, w(y)=1 则P (r+1,r2+1, r6+1)= 1 (r +1) 6 + 9(r +1) 2 (r 2 +1) 2 + 8(r 3 +1) 2 + 6(r 2 +1)(r 4 +1)G24=r6+r5+2r4+3r3+2r2+r+1故 4 个结点的简洁图共有 11 个，如以下图：