您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 李凡长版组合数学课后习题答案习题5
31第五章Pólya计数理论1.计算(123)(234)(5)(14)(23),并指出它的共轭类.解:题中出现了5个不同的元素:分别是:1,2,3,4,5。即|Sn|=5。512345432152431543215413254321)23)(14)(5)(234)(123(512345432152143543215341254321)5)(34)(12((5)(12)(34)的置换的型为1122而Sn中属于1122型的元素个数为1521!1!2!521个其共轭类为(5)(14)(23),(5)(13)(24),(1)(23)(45),(1)(24)(35),(1)(25)(34),(2)(13)(45),(2)(14)(35),(2)(15)(34),(3)(12)(45),(3)(14)(25),(3)(15)(24),(4)(12)(35),(4)(13)(25),(4)(15)(24)2.设D是n元集合,G是D上的置换群.对于D的子集A和B,如果存在G,使得}|)({AaaB,则称A与B是等价的.求G的等价类的个数.解:根据Burnside引理niiacGl11)(1,其中c1(ai)表示在置换ai作用下保持不变的元素个数,则有c1(σI)=n;设在σ的作用下,A的元素在B中的个数为i,则c2(σ)=n-2i;若没有其他置换,则G诱出来的等价类个数为l=ininn)]2([213.由0,1,6,8,9组成的n位数,如果把一个数调转过来读得到另一个数,则称这两个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n位数有多少个?解:该题可理解为相当于n位数,0,1,6,8,9这5个数存在一定的置换关系32对于置换群G={g1,g2}g1为不动点置换,型为1n;为5n;g2置换:(1n)(2(n-1))(3(n-2))…(22nn)分为2种情况:(1)n为奇数时212n,但是只有中间的数字是0,1,8的时候,才可能调转过来的时候是相同的,所以这里的剩下的中间数字只能是有3种。即:个数为3×215n(2)n为偶数时22n,个数为25n该置换群的轮换指标为n为偶数时,等价类的个数l=232521)55(21nnnn为奇数时,等价类的个数l=)535(2121nn4.现有8个人计划去访问3个城市,其中有3个人是一家,另外有2个人是一家.如果一家人必须去同一个城市,问有多少种方案?写出它们的模式.解:令D={d1,d2,…,d8},其中,d1,d2,d3为一家,d4,d5为一家。R={c1,c2,c3},w(c1)=α,w(c2)=β,w(c3)=γ.f:D→R是一种安排方案。根据题意,做D的一个5分划{d1,d2,d3},{d4,d5},{d6},{d7},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)绕相对两顶点连线旋转120°,240°的置换,型为32,有8个;(4)绕相对两边中点连线旋转180°的置换,型为23,有6个。所以,该置换群的轮换指标为PG(x1,x2,…,x6)=)6836(2413223222142161xxxxxxx等价类的个数为33l=PG(3,3,…,3)=)3638333363(241322236=57下面计算全部着色模式。这里,R={c1,c2,c3},w(c1)=r,w(c2)=b,w(c3)=g,于是F的全部模式表])(6)(8)()(3)()(6)[(241322223332222244426gbrgbrgbrgbrgbrgbrgbr其中,红色、蓝色、绿色各出现2次的方案数就是上述展开式中r2b2g2项的系数,即6)!1!1!1!3623!2!2!2!6(2416.有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案?解:其置换群为:不动置换:型为19,1个沿中间格子及其对角线方向做旋转的置换:型为1323,4个旋转90°和240°时的置换:型为1142,2个旋转180°时的置换型为1124,1个P(x)=42243239)1)(1()1)(1(2)1()1(4)1(81xxxxxxx我们设定x为红色,1为蓝色,即转化为求x2的系数(1)对应于19,(1+x)9中x2项系数为C(9,2)=36;(2)对应于1323,4(1+x)3(1+x2)3中x2项系数为:4[C(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项系数为C(4,1)=4;故x2的系数为8)42436(817.对正六角形的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个。34所以,该置换群的轮换指标为PG(x1,x2,…,x6)=)3322(12132222123661xxxxxx下面计算全部着色模式。这里,R={c1,c2,c3,c4,c5},不妨设w(c1)=r,w(c2)=b,w(c3)=g,w(c4)=p,w(c3)=y,于是F的全部模式表])(3))((3)(2)(2)[(12132222222222222222233333666666ypgbrypgbrypgbrypgbrypgbrypgbr其中,用这5种颜色着色的方案数就是上述展开式中r2bgpy,rb2gpy,rbg2py,rbgp2y,rbgpy2项的系数之和,即150)!1!1!1!1!2!65(1218.在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可供选择的方案?(旋转木马只能转动不能翻转)解:设想另一个正7边形与不动的正7边形完全重合,并且顶点标记相同,那么绕中心旋转i7360(1≤i≤7)角度,使得能够与不动的正7边形重合。它对应的置换是:71共6个。故其轮换指标为PG(x1,x2,…xn)=)6(71771xx计算全部着色模式为)]...(6)...[(7177271721nnxxxxxxn7时为)!7(!!7)!8(!6),7()]!1(7!...[1!1!771nnnnCn9.一个圆圈上有n个珠子,用n种颜色对珠子着色,要求颜色数目不少于n的方案数是多少?解:(1)不动点置换有一个;(2)绕中心旋转in360(1≤i≤n)角度,使得能够与不动的环重合。它对应的置换是:n1共(n-1)个;(3)把n为奇数、偶数分两种情况分析:i)n为奇数时:沿一颗珠子和其他剩余珠子的平分线绕180°,对应的置换是21121n共n个;35ii)n为偶数时:沿珠子平分线绕180°,对应的置换是22n,共2n个。故其轮换指标为PG(x1,x2,…xn)=))1((2121211nnnxnxxnxn(n为奇数时);PG(x1,x2,…xn)=)2)1((32221nnnxnxnxn(n为偶数时);10.骰子的6个面上分别标有1,2,…,6,问有多少种不同的骰子?解:下面有3种方法求解:方法16个面分别标上不同的点数,相当于用6种不同的颜色对它着色,并且每种颜色出现且只出现一次,共有6!种方案。但这种方案经过正立方体的旋转可能会发生重合,全部方案上的置换群G显然有24个元素。由于每个面的着色全不相同,只有恒等置换σI保持6!种方案不变,即c1(σI)=6!,c1(p)=0(p≠σI)。由Burnside引理知GcGl)(11=30)00!6(241方法2在习题5中已求出关于正立方体6个面的置换群轮换指标,如果用m种颜色进行着色,则不同的着色方案数为)8123(2412346mmmmlm严格的说,lm是至多用m种颜色着色的方案数。我们可以计算出l1=1,l2=10,l3=57,l4=240,l5=800,l6=2226。现令ni表示恰好用i种颜色着色的方案数,则由容斥原理知n1=l1=1812122nln3013231233nnln6814243412344nnnln7515253545123455nnnnln363016263646561234566nnnnnln方法3令R={c1,c2,…,c6},w(ci)=wi(1≤i≤6)。正立方体6个面上的置换群G的轮换指标为PG(x1,x2,…,x6)=)6836(2413223222142161xxxxxxx于是F的全部模式表为))(,,)(,)((62RrRrRrGrwrwrwP])(6)(8)()(3))((6)[(241326212363122621261464161661其中,w1w2w3w4w5w6项的系数就是用6种颜色对6个面着色的方案数,等于30!1!1!1!624111.将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法?列出全部方案.又问每盒中有两个球的方法有多少种?解:令D={w1,w2,b1,b2},R={盒1,盒2},四个球往两个盒子里放的放法是F:D→R。由于w1,w2是两个相同的白球,b1,b2是两个相同的黑球,由此确定出D上的置换群为G={σI,(w1w2),(b1b2),(w1w2)(b1b2)}其轮换指标为PG(x1,x2,x3,x4)=)2(412222141xxxx于是F上的等价类个数为l=PG(2,2,2,2)=9)22222(41224这9个不同方案分别为(ø,wwbb),(w,wbb),(b,wwb),(ww,bb),(wb,wb),(wwbb,ø),(wbb,w),(wwb,b),(bb,ww)令w(盒1)=x,w(盒2)=y,则F上的全部模式表为PG(x+y,x2+y2,x3+y3,x4+y4)=))()()(2)((412222224yxyxyxyx=x4+2x3y+3x2y2+2xy3+y4盒1与盒2中各放两个球的方案数是x2y2项的系数,即为3。具体方案为(ww,bb),(wb,wb),(bb,ww)3712.将2个红球和2个蓝球放在正六面体的顶点上,问有多少种不同的方案?解:正立方体8个点的置换群G有24
本文标题:李凡长版组合数学课后习题答案习题5
链接地址:https://www.777doc.com/doc-2381985 .html