《李凡长版 组合数学课后习题答案 习题5》由会员分享，可在线阅读，更多相关《李凡长版 组合数学课后习题答案 习题5（10页珍藏版）》请在金锄头文库上搜索。
1、31第五章 Plya计数理论1. 计算（123） （234） （5） （14） （23）,并指出它的共轭类.解：题中出现了 5 个不同的元素：分别是：1，2，3，4，5。即|S n|5。 51234523154321)()( 53412)(（5） （12） （34）的置换的型为 1122 而 Sn 中属于 1122 型的元素个数为个其共轭类为12!（5） （14） （23） ， （5） （13） （24） ， （1） （23） （45） ， （1） （24） （35） ，（1） （25） （34） ， （2） （13） （45） ， （2） （14） （35） ， （2） （15） （34）
2、，（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使得 ,则称 A 与 B 是等价的.求 G 的等价类的个数.|)(aB解：根据 Burnside 引理 ，其中 c1(ai)表示在置换 ai 作用下保持不niiacl1)(变的元素个数，则有c1( I)=n;设在 的作用下，A 的元素在 B 中的个数为 i，则c2( )=n2i；若没有其他置换，则 G 诱出来的等价
3、类个数为 l= inin)2(13. 由 0,1,6,8,9 组成的 n 位数,如果把一个数调转过来读得到另一个数,则称这两个数是相等的.例如,0168 和 8910,0890 与 0680 是相等的.问不相等的 n 位数有多少个？32解：该题可理解为相当于 n 位数，0，1，6，8，9 这 5 个数存在一定的置换关系对于置换群 G=g1,g2g1 为不动点置换，型为 1n；为 5n；g2 置换：（1n）(2(n-1)(3(n-2)( )2分为 2 种情况：（1） n 为奇数时 ，但是只有中间的数字是 0，1，8 的时候，才可能21n调转过来的时候是相同的，所以这里的剩下的中间数字只能是有 3
4、种。即：个数为 3 215n（2） n 为偶数时 ，个数为 2n25n该置换群的轮换指标为n 为偶数时，等价类的个数 l= 23251)5(1nnn 为奇数时，等价类的个数 l= )3(221nn4. 现有 8 个人计划去访问 3 个城市,其中有 3 个人是一家,另外有 2 个人是一家.如果一家人必须去同一个城市,问有多少种方案？写出它们的模式.解：令 D=d1,d2,d8，其中，d 1,d2,d3 为一家，d 4,d5 为一家。R=c 1,c2,c3,w(c1)=,w(c 2)=,w(c 3)=.f:DR 是一种安排方案。根据题意，做 D 的一个5 分划 d 1,d2,d3,d4,d5,d6
5、,d7,d8,要求 f 在每块中的元素取值相同。对于d 1,d2,d3，可以取 3 3 3模式；对于d 4,d5 ，可以取 2 2 2模式；对于d 6,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 个；（
6、3） 绕相对两顶点连线旋转 120，240的置换，型为 32，有 8 个；（4） 绕相对两边中点连线旋转 180的置换，型为 23，有 6 个。所以，该置换群的轮换指标为33PG（x 1,x2,x6）= )6836(24132321421 xxx等价类的个数为l=PG(3,3,3)= =57)3( 32236 下面计算全部着色模式。这里，R=c 1,c2,c3，w(c 1)=r，w(c 2)=b，w(c 3)=g，于是F 的全部模式表 )(6)(8 )()(3)(24132233 22244gbrgbr gbrgbr 其中，红色、蓝色、绿色各出现 2 次的方案数就是上述展开式中 r2b2g2
7、项的系数，即 6)!13!26(416. 有一个 33 的正方形棋盘,若用红蓝两色对这 9 个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案？解： 其置换群为：不动置换：型为 19，1 个沿中间格子及其对角线方向做旋转的置换：型为 1323，4 个旋转 90和 240时的置换：型为 1142 ， 2 个旋转 180时的置换 型为 1124， 1 个P(x)= 4224339 )1)()()()1(4)1(8 xxxx 我们设定 x 为红色，1 为蓝色，即转化为求 x2 的系数（1） 对应于 19， （1x） 9 中 x2 项系数为 C(9,2)=36；（2） 对应于 1323，4(1
8、x) 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 的系数为 836(87. 对正六角形的 6 个顶点用 5 种颜色进行着色.试问有多少种不同的方案,旋转使之重合作为相同处理.解：对该正六角形的 6 的顶点的置换群有 12 个，它们分别是：(1) 不动点置换，型为 16，有 1 个；(2) 旋转 60和 300的置换，型为 61，有 2 个；旋转 120和 240的3
9、4置换， 型为 32，有 2 个； 旋转 180的置换型为 23 有 1 个；(3) 绕对角连线旋转 180的置换 ，型为 1222，有 3 个；(4) 绕对边中点连线旋转 180的置换，型为 23，有 3 个。所以，该置换群的轮换指标为PG（x 1,x2,x6）= )2(1 322136 xxx下面计算全部着色模式。这里，R=c 1,c2,c3,c4,c5，不妨设 w(c1)=r，w(c 2)=b，w(c 3)=g， w(c4)=p，w(c 3)=y，于是F 的全部模式表 )(3)(3 2212 322222 3666 ypgbrypgbrypgbr 其中，用这 5 种颜色着色的方案数就是上
10、述展开式中 r2bgpy, rb2gpy, rbg2py,rbgp2y, rbgpy2 项的系数之和，即 150)!265(18. 在一个有 7 匹马的旋转木马上用 n 种颜色着色,问有多少种可供选择的方案？（旋转木马只能转动不能翻转）解： 设想另一个正 7 边形与不动的正 7 边形完全重合，并且顶点标记相同，那么绕中心旋转 （1i7）角度，使得能够与不动的正 7 边形重合。360o它对应的置换是：7 1 共 6 个。故其轮换指标为PG(x1,x2,xn)= )(771x计算全部着色模式为 ).(6).( 7721721 nn xxn7 时为 )!7(!)8(),()!(7!.1Cn 9. 一
11、个圆圈上有 n 个珠子,用 n 种颜色对珠子着色,要求颜色数目不少于 n 的方案数是多少?解：（1）不动点置换有一个；（2）绕中心旋转 （1in）角度，使得能够与不动的环重合。它对o360应的置换是：n 1 共(n1)个；（3）把 n 为奇数、偶数分两种情况分析：35i) n 为奇数时：沿一颗珠子和其他剩余珠子的平分线绕 180，对应的置换是 共 n 个；21ii) n 为偶数时：沿珠子平分线绕 180，对应的置换是 ，共 个。2n故其轮换指标为PG(x1,x2,xn)= （n 为奇数时） ；)1(121nnxxPG(x1,x2,xn)= （n 为偶数时） ；)(321nn10. 骰子的 6
12、个面上分别标有 1,2,6,问有多少种不同的骰子？解：下面有 3 种方法求解：方法 1 6 个面分别标上不同的点数，相当于用 6 种不同的颜色对它着色，并且每种颜色出现且只出现一次，共有 6！种方案。但这种方案经过正立方体的旋转可能会发生重合，全部方案上的置换群 G 显然有 24 个元素。由于每个面的着色全不相同，只有恒等置换 I 保持 6！种方案不变，即 c1( I)=6!，c 1(p)=0（p I） 。由 Burnside 引理知=Gl)(1 30)0!6(24L方法 2 在习题 5 中已求出关于正立方体 6 个面的置换群轮换指标，如果用m 种颜色进行着色，则不同的着色方案数为 )8123
13、(2412346 mml 严格的说，l m 是至多用 m 种颜色着色的方案数。我们可以计算出l1=1,l2=10,l3=57,l4=240,l5=800,l6=2226。现令 ni 表示恰好用 i 种颜色着色的方案数，则由容斥原理知n1=l1=1 8212nl 301233ln68434124 nnl36751253455 nnln 30665612346 l方法 3 令 R=c1,c2,c6，w(c i)=wi(1i6)。正立方体 6 个面上的置换群 G 的轮换指标为PG(x1,x2,x6) = )83(4 3232142161 xxx于是 F 的全部模式表为)(,)(,)(62RrRrrG
14、wwL)(6)(8 )()(3)(241326212331 2621614641 ww LL LLL其中，w 1w2w3w4w5w6 项的系数就是用 6 种颜色对 6 个面着色的方案数，等于 30!124L11. 将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？解： 令 D=w1,w2,b1,b2,R=盒 1，盒 2，四个球往两个盒子里放的放法是F：D R。由于 w1,w2 是两个相同的白球，b 1,b2 是两个相同的黑球，由此确定出 D 上的置换群为G= I,(w1w2),(b1b2),(w1w2)(b1b2)其轮换
15、指标为PG(x1,x2,x3,x4) = )2(2141xx于是 F 上的等价类个数为l=PG(2,2,2,2)= 9)22(4这 9 个不同方案分别为(， wwbb), ( w,wbb), (b,wwb), (ww,bb), (wb,wb), (wwbb, ), (wbb,w), (wwb,b), (bb,ww)令 w(盒 1) x，w(盒 2) y，则 F 上的全部模式表为37PG(x+y,x2+y2,x3+y3,x4+y4) = )()()2)(1 2224 yxyxyx=x4+2x3y+3x2y2+2xy3+y4盒 1 与盒 2 中各放两个球的方案数是 x2y2 项的系数，即为 3。具体方案为(ww,bb), (wb,wb), (bb,ww)12. 将 2 个红球和 2 个蓝球放在正六面体的顶点上,问有多少种不同的方案？解： 正立方体 8
