组合数学习题5(共5章)

31第五章Pólya计数理论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），（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×215n（2）n为偶数时22n，个数为25n该置换群的轮换指标为n为偶数时，等价类的个数l=232521)55(21nnnn为奇数时，等价类的个数l=)535(2121nn4.现有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(2416.有一个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(817.对正六角形的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）=)4322(12132222123661xxxxxx下面计算全部着色模式。这里，R={c1,c2,c3,c4,c5}，不妨设w(c1)=r，w(c2)=b，w(c3)=g，w(c4)=p，w(c3)=y，于是F的全部模式表])(4))((3)(2)(2)[(12132222222222222222233333666666ypgbrypgbrypgbrypgbrypgbrypgbr其中，用这5种颜色着色的方案数就是上述展开式中r2bgpy,rb2gpy,rbg2py,rbgp2y,rbgpy2项的系数之和，即150)!1!1!1!1!2!65(1218.在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可供选择的方案？（旋转木马只能转动不能翻转）解：设想另一个正7边形与不动的正7边形完全重合，并且顶点标记相同，那么绕中心旋转i7360（1≤i≤7）角度，使得能够与不动的正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）绕中心旋转in360（1≤i≤n）角度，使得能够与不动的环重合。它对应的置换是：n1共(n－1)个；（3）把n为奇数、偶数分两种情况分析：i)n为奇数时：沿一颗珠子和其他剩余珠子的平分线绕180°，对应的置换是21121n共n个；ii)n为偶数时：沿珠子平分线绕180°，对应的置换是22n，共2n个。35故其轮换指标为PG(x1,x2,…xn)=))1((2121211nnnxnxxnxn（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=1812122nln3013231233nnln6814243412344nnnln7515253545123455nnnnln3016263646561234566nnnnnln方法3令R={c1,c2,…,c6}，w(ci)=wi(1≤i≤6)。正立方体6个面上的置换群G的轮换指标为36PG(x1,x2,…,x6)=)6836(2413223222142161xxxxxxx于是F的全部模式表为))(,,)(,)((62RrRrRrGrwrwrwP])(6)(8)()(3))((6)[(241326212363122621261464161661其中，w1w2w3w4w5w6项的系数就是用6种颜色对6个面着色的方案数，等于30!1!1!1!624111.将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？解：令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)12.将2个红球和2个蓝球放在正六面体的顶点上,问有多少种不同的方案？解：正立方体8个点的置换群G有24个元