组合数学习题5(共5章).pdf
《组合数学习题5(共5章).pdf》由会员分享,可在线阅读,更多相关《组合数学习题5(共5章).pdf(10页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
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 种 颜 色 着 色 的 方 案 数。我 们 可 以 计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 习题
限制150内