《组合数学习题5(共5章).pdf》由会员分享，可在线阅读，更多相关《组合数学习题5(共5章).pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-WORD 格式-可编辑-专业资料-完整版学习资料分享-第五章 Plya计数理论 1.计算（123）（234）（5）（14）（23）,并指出它的共轭类.解：题中出现了 5 个不同的元素：分别是：1，2，3，4，5。即|Sn|5。512345432152431543215413254321)23)(14)(5)(234)(123(51234543215214354321 5341254321)5)(34)(12(（5）（12）（34）的置换的型为1122而 Sn中属于 1122型的元素个数为1521!1!2!521个其共轭类为（5）（14）（23），（5）（13）（24），（1）（23）（45）
2、，（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
3、 中的个数为 i，则 c2()=n2i；若没有其他置换，则 G 诱出来的等价类个数为 l=ininn)2(21 3.由 0,1,6,8,9 组成的 n 位数,如果把一个数调转过来读得到另一个数,则称这两个数是相等的.例如,0168 和 8910,0890与 0680 是相等的.问不相等的 n 位数有多少个？解：该题可理解为相当于 n 位数，0，1，6，8，9 这 5 个数存在一定的置换关系 对于置换群 G=g1,g2 g1为不动点置换，型为 1n；为 5n；-WORD 格式-可编辑-专业资料-完整版学习资料分享-g2置换：（1n）(2(n-1)(3(n-2)(22nn)分为 2 种情况：（1）
4、n 为奇数时212n，但是只有中间的数字是 0，1，8 的时候，才可能调转过来的时候是相同的，所以这里的剩下的中间数字只能是有 3 种。即：个数为 3215n（2）n 为偶数时 22n，个数为 25n 该置换群的轮换指标为 n 为偶数时，等价类的个数 l=232521)55(21nnn n 为奇数时，等价类的个数 l=)535(2121nn 4.现有 8 个人计划去访问 3 个城市,其中有 3 个人是一家,另外有 2 个人是一家.如果一家人必须去同一个城市,问有多少种方案？写出它们的模式.解：令 D=d1,d2,d8，其中，d1,d2,d3为一家，d4,d5为一家。R=c1,c2,c3,w(c
5、1)=,w(c2)=,w(c3)=.f:DR 是一种安排方案。根据题意，做 D 的一个 5 分划 d1,d2,d3,d4,d5,d6,d7,d8,要求 f 在每块中的元素取值相同。对于d1,d2,d3，可以取333模式；对于d4,d5，可以取222模式；对于d6,d7,d8，可以取模式.所以，总的模式为（333）（222）（）3 5.对正立方体 6 个面用红、蓝、绿 3 种颜色进行着色,问有多少种不同的方案？又问 3种颜色各出现 2 次的着色方案有多少种？解：正立方体 6 个面的置换群 G 有 24 个元素，它们是：（1）不动的置换，型为 16，有一个；（2）绕相对两面中心轴旋转 90，270
6、的置换，型为 1241，有 6 个；旋转 180的置换，型为 1222，有 3 个；（3）绕相对两顶点连线旋转 120，240的置换，型为 32，有 8 个；（4）绕相对两边中点连线旋转 180的置换，型为 23，有 6 个。所以，该置换群的轮换指标为 PG（x1,x2,x6）=)6836(2413223222142161xxxxxxx 等价类的个数为 l=PG(3,3,3)=)3638333363(241322236=57 下面计算全部着色模式。这里，R=c1,c2,c3，w(c1)=r，w(c2)=b，w(c3)=g，于是 F 的全部模式表-WORD 格式-可编辑-专业资料-完整版学习资料
7、分享-)(6)(8)()(3)()(6)(241322223332222244426gbrgbrgbrgbrgbrgbrgbr 其中，红色、蓝色、绿色各出现 2 次的方案数就是上述展开式中 r2b2g2项的系数，即 6)!1!1!1!3623!2!2!2!6(241 6.有一个 33 的正方形棋盘,若用红蓝两色对这 9 个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案？解：其置换群为：不动置换：型为 19，1 个 沿中间格子及其对角线方向做旋转的置换：型为1323，4 个 旋转 90和 240时的置换：型为1142，2 个 旋转 180时的置换 型为 1124，1 个 P(x)=42
8、243239)1)(1()1)(1(2)1()1(4)1(81xxxxxxx 我们设定 x 为红色，1 为蓝色，即转化为求 x2的系数（1）对应于 19，（1x）9中 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）对应于 1142 2(1+x)(1+x4)2中 x2项系数为 0；（4）对应于 1124 (1+x)(1+x2)4中 x2项系数为 C(4,1)=4；故 x2的系数为 8)42436(81 7.对正六角形的6 个顶点用 5 种颜色进行着色.试问有多少种不同的方案,
9、旋转使之重合作为相同处理.解：对该正六角形的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 个。所以，该置换群的轮换指标为 PG（x1,x2,x6）=)4322(12132222123661xxxxxx 下面计算全部着色模式。这里，R=c1,c2,c3,c4,c5，不妨设 w(c1)=r，
10、w(c2)=b，w(c3)=g，w(c4)=p，w(c3)=y，于是 F 的全部模式表-WORD 格式-可编辑-专业资料-完整版学习资料分享-)(4)(3)(2)(2)(12132222222222222222233333666666ypgbrypgbrypgbrypgbrypgbrypgbr 其中，用这5 种颜色着色的方案数就是上述展开式中 r2bgpy,rb2gpy,rbg2py,rbgp2y,rbgpy2项的系数之和，即 150)!1!1!1!1!2!65(121 8.在一个有 7 匹马的旋转木马上用 n 种颜色着色,问有多少种可供选择的方案？（旋转木马只能转动不能翻转）解：设想另一个正
11、 7 边形与不动的正7 边形完全重合，并且顶点标记相同，那么绕中心旋转i7360（1i7）角度，使得能够与不动的正 7 边形重合。它对应的置换是：71 共 6 个。故其轮换指标为 PG(x1,x2,xn)=)6(71771xx 计算全部着色模式为).(6).(7177271721nnxxxxxx n7 时为)!7(!7)!8(!6),7()!1(7!.1!1!771nnnnCn 9.一个圆圈上有 n 个珠子,用 n 种颜色对珠子着色,要求颜色数目不少于 n 的方案数是多少?解：（1）不动点置换有一个；（2）绕中心旋转in360（1in）角度，使得能够与不动的环重合。它对应的置换是：n1 共(n
12、1)个；（3）把 n 为奇数、偶数分两种情况分析：i)n 为奇数时：沿一颗珠子和其他剩余珠子的平分线绕 180，对应的置换是21121n共 n 个；ii)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 种方法求解：-WORD 格式-可编辑-专业资料-完整版学习资料分享-方法 1 6 个面分别标上不同的点数，相当于
13、用 6 种不同的颜色对它着色，并且每种颜色出现且只出现一次，共有 6！种方案。但这种方案经过正立方体的旋转可能会发生重合，全部方案上的置换群 G 显然有 24 个元素。由于每个面的着色全不相同，只有恒等置换I 保持 6！种方案不变，即 c1(I)=6!，c1(p)=0（pI）。由Burnside 引理知 GcGl)(11=30)00!6(241 方法 2 在习题 5 中已求出关于正立方体 6 个面的置换群轮换指标，如果用 m 种颜色进行着色，则不同的着色方案数为)8123(2412346mmmmlm 严 格 的 说，lm是 至 多 用 m 种 颜 色 着 色 的 方 案 数。我 们 可 以 计
14、 算 出l1=1,l2=10,l3=57,l4=240,l5=800,l6=2226。现令 ni表示恰好用 i 种颜色着色的方案数，则由容斥原理知 n1=l1=1 812122nln 3013231233nnln 6814243412344nnnln 7515253545123455nnnnln 3016263646561234566nnnnnln 方法 3 令 R=c1,c2,c6，w(ci)=wi(1i6)。正立方体 6 个面上的置换群 G 的轮换指标为 PG(x1,x2,x6)=)6836(2413223222142161xxxxxxx 于是 F 的全部模式表为 )(,)(,)(62Rr
15、RrRrGrwrwrwP)(6)(8)()(3)(6)(241326212363122621261464161661wwwwwwwwwwwwww-WORD 格式-可编辑-专业资料-完整版学习资料分享-其中，w1w2w3w4w5w6项的系数就是用 6 种颜色对 6 个面着色的方案数，等于 30!1!1!1!6241 11.将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？解：令 D=w1,w2,b1,b2,R=盒 1，盒 2，四个球往两个盒子里放的放法是 F：DR。由于 w1,w2是两个相同的白球，b1,b2是两个相同的黑
16、球，由此确定出 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+
17、2x3y+3x2y2+2xy3+y4 盒 1 与盒 2 中各放两个球的方案数是x2y2项的系数，即为3。具体方案为(ww,bb),(wb,wb),(bb,ww)12.将 2 个红球和 2 个蓝球放在正六面体的顶点上,问有多少种不同的方案？解：正立方体 8 个点的置换群 G 有 24 个元素，它们是：（1）不动的置换，型为 18，有 1 个；（2）绕相对两面中心轴旋转 90，270的置换，型为 42，有 6 个；旋转 180的置换，型为 24，有 3 个；（3）绕相对两顶点连线旋转 120，240的置换，型为 1232，有 8 个；（4）绕相对两边中点连线旋转 180的置换，型为 24，有 6
18、个。所以，该置换群的轮换指标为 PG（x1,x2,x6）=)986(2414223212481xxxxx 下面计算全部着色模式。这里，假设除了红色和蓝色外我们放绿球，则 R=c1,c2,c3，w(c1)=r，w(c2)=b，w(c3)=g，于是 F 的全部模式表)(9)()(8)(6)(24142222333224448gbrgbrgbrgbrgbr-WORD 格式-可编辑-专业资料-完整版学习资料分享-其中，红色、蓝色各出现 2 次的方案数就是上述展开式中 r2b2g4项的系数，即)!2!1!1!49!4!2!2!8(24122 13.长为 n 的透明的方格,用红、蓝、黄、绿4 种颜色进行着
19、色,试问有多少种不同的方案？解：问题相当于用 r,b,y,g 构成长为 n 的字符串，将从左向右的字符顺序和从右向左的字符顺序看作时相同的，例如，yggrbr 和 rbrggy 看作是相同的。群 G：1211212121nnnnnn 根据 Plya 定理，不同的方案数应为：N)44(2121 nn 14.用两种颜色对正六面体的 6 个面、8 个顶点进行着色,问有多少种不同方案？转动使之一致作为一类处理.解：对正六面体的6 个面的置换群设为 G，G 的循环指数多项式为：P(G)=23322221421618636SSSSSSS 设正六面体 8 个顶点的置换群为 H，H 的循环指数多项式为 P(H
20、)=2321422481896SSSSS P(GH)=P(G)P(H)=896 8636)24(1232142248123322221421612SSSSSSSSSSSS 647248848543662427183485436 6896)24(143214342242323812332217224323281232241622124222122101432414422134211012381426124611412SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS所求的不同等价类数为 28292622826232625761442823436 28144242
21、5632484848645761 2305522405761 15.一个正八面体,用红、蓝两色对6 个顶点进行着色；用黄、绿两种颜色对 8 个面进行着色,试求其中 4 个顶点为红,两个顶点为蓝,黄和绿的面各 4 面的方案数.注：正八面体可以看作是正方体的对偶，每一面用中心代表一个顶点，相交于一个顶点的 3 个面对应过 3 个中心的三角形，由此构成的6 个顶点，8 个面的几何图形。即可得到我们需要的正八面体的形状。-WORD 格式-可编辑-专业资料-完整版学习资料分享-解：通过刚才我们的提示可以得到如下结论：可以把问题转换成对于正六面体的顶点和面的着色问题，转换成为要求给这个正六面体着色：用红、
22、蓝两色对6 个面进行着色；用黄、绿两种颜色对 8 个顶点进行着色,试求其中 4 个面为红,2 个面为蓝；黄和绿的顶点各 4 个的方案数.对正六面体的 6 个面的置换群设为 G，G 的循环指数多项式为：P(G)=23322221421618636SSSSSSS 设正六面体 8 个顶点的置换群为 H，H 的循环指数多项式为 P(H)=2321422481896SSSSS P(GH)=P(G)P(H)=896 8636)24(1232142248123322221421612SSSSSSSSSSSS 所求的不同等价类数为 )(8)(6)()(3)()(6)(24123332222224426brbr
23、brbrbrbrbr)(9)()(8)(6)(24142223322448gygygygygy 所得的r4b2y4g4的系数即为所求：!2!2!49)!1!1!2!1!1!2(8!1!1!26!4!4!8241!1!2!36)1!1!21(316!2!4!6241！=2714 所以符合题意的方案数为 14 种。16.用 Plya 定理求多重集合 12,nMaaa的 r 圆排列数.解：可转化为有 r 颗珠子的项链可以着 n 种颜色的方法数。（1）不动点置换有 1 个；（2）绕中心旋转ir360（1ir）角度，使得能够与不动的环重合。它对应的置换是：r1 共(r1)个；（3）把 r 为奇数、偶数分
24、两种情况分析：i)r 为奇数时：沿一颗珠子和其他剩余珠子的平分线绕 180，对应的置换是21121r共 r 个；ii)r 为偶数时：沿珠子平分线绕 180，对应的置换是22r，共2r个。故其轮换指标为 PG(x1,x2,xn)=)1(2121211rrrxrxxrxr（r 为奇数时）；=)1(2121rrnrnnrnr-WORD 格式-可编辑-专业资料-完整版学习资料分享-=)1(2121rrrnnrnr PG(x1,x2,xn)=)2)1(32221rrrxrxrxr（r 为偶数时）；=)2)1(322rrnrnrnr 17.求 n 个顶点的简单图有多少个？解：简单图指的是过两个顶点没有多于
25、一条的边，而且不存在圈的图形。问题相当于对 n 个无标志顶点的完全图的)1(2nn条边，用两种颜色进行着色，求不同方案数的问题。比如两种颜色 x,y，令着上色 y 的边从图中消去，得到一 n 个顶点的简单图。例如 3 个顶点的无向图，有 G=(v1)(v2)(v3)，(v1v2v3)，(v3v2v1)，(v1)(v2v3)，(v2)(v1v3)，(v3)(v1v2)P(x,y)=)(2)(3)(6133223yxyxyxyx=x3+y3+xy2+x2y v1 v2 v3 从 P(x,y)可知，对上图的三角形的边着色，其中 3 条边都用 x 着色的有 1；同样 用 x 着色两条的、着色一条的、无
26、一条着色的方案各为 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上的置换，后者构成边集合上的置换群 G.G 中有 16型的置换 1 个，1222型的置换 9 个，32型的置换 8 个，2141型的置换 6 个.G 的轮换指标为：PG(x1,x2,x6)=)689(2414223222161xxxxxx 令 R=x,y，w(x)=r,w(y)=1 则 PG(r+1,r2+1,r6+1)=)1)(1(6)1(8)1()1(9)1(24142232226rrrrrr =r6+r5+2r4+3r3+2r2+r+1 故 4 个结点的简单图共有 11 个，如图所示：-WORD 格式-可编辑-专业资料-完整版学习资料分享-