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

2023年12月9日发(作者：第5单元的数学试卷)

第五章 Pólya计数理论

1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类.

解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|Sn|＝5。

(123)(234)(5)(14)(23)123451234512345

23145134254321512345123453412543215

1234521435

(12)(34)(5)

（5）（12）（34）的置换的型为1122而Sn中属于1122型的元素个数为个其共轭类为

（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,使得B{(a)|aA},则称A与B是等价的.求G的等价类的个数.

解：根据Burnside引理l的元素个数，则有

c1(σI)=n;

设在σ的作用下，A的元素在B中的个数为i，则

c2(σ)=n－2i；

若没有其他置换，则G诱出来的等价类个数为l=[n(n2i)]ni

3. 由0,1,6,8,9组成的n位数,如果把一个数调转过来读得到另一个数,则称这两个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n位数有多少个？

解：该题可理解为相当于n位数，0，1，6，8，9这5个数存在一定的置换关系

31

5!152!1!11221nc1(ai)，其中c1(ai)表示在置换ai作用下保持不变Gi112对于置换群G={g1,g2}

g1为不动点置换，型为1n；为5n；

nng2置换：（1n）(2(n-1))(3(n-2))…(22)

分为2种情况：

（1） n为奇数时12 ，但是只有中间的数字是0，1，8的时候，才可能调转过来的时候是相同的，所以这里的剩下的中间数字只能是有3种。

即：个数为3×5n2n12n2

n2（2） n为偶数时

2 ，个数为

5

该置换群的轮换指标为

1n122(55)5 n为偶数时，等价类的个数l=221nn为奇数时，等价类的个数l=(5352n12n3n)

4. 现有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）（α＋β＋γ）3

5. 对正立方体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）=等价类的个数为

1622223(x16x1x43x1x28x36x2)

2432

l=PG(3,3,…,3)=

16(363333232832633)=57

24下面计算全部着色模式。这里，R={c1,c2,c3}，w(c1)=r，w(c2)=b，w(c3)=g，于是

F的全部模式表

1[(rbg)66(rbg)2(r4b4g4)3(rbg)2(r2b2g2)224

333222238(rbg)6(rbg)]其中，红色、蓝色、绿色各出现2次的方案数就是上述展开式中r2b2g2项的系数，即

16!3!(326)6

242!2!2!1!1!1!6. 有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案？

解： 其置换群为：

不动置换：型为 19，1个

沿中间格子及其对角线方向做旋转的置换：型为1323，4个

旋转90°和240°时的置换：型为1142 ， 2个

旋转180°时的置换 型为1124， 1个

193234224P(x)=(1x)4(1x)(1x)2(1x)(1x)(1x)(1x)

8我们设定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） 对应于1142 2(1+x)(1+x4)2中x2项系数为0；

（4） 对应于1124 (1+x)(1+x2)4中x2项系数为C(4,1)=4；

1故x的系数为

(36244)8

827. 对正六角形的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个。

33 所以，该置换群的轮换指标为

PG（x1,x2,…,x6）=162223(x12x62x33x1x24x2)

12下面计算全部着色模式。这里，R={c1,c2,c3,c4,c5}，不妨设w(c1)=r，w(c2)=b，w(c3)=g，w(c4)=p，w(c3)=y，于是

F的全部模式表

1[(rbgpy)62(r6b6g6p6y6)2(r3b3g3p3y3)212

3(r2b2g2p2y2)(r2b2g2p2y2)24(r2b2g2p2y2)3]其中，用这5种颜色着色的方案数就是上述展开式中r2bgpy, rb2gpy,

rbg2py,rbgp2y, rbgpy2项的系数之和，即

16!(5)150

122!1!1!1!1!8. 在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可供选择的方案？（旋转木马只能转动不能翻转）

解： 设想另一个正7边形与不动的正7边形完全重合，并且顶点标记相同，那360么绕中心旋转i（1≤i≤7）角度，使得能够与不动的正7边形重合。它7对应的置换是：71 共6个。故其轮换指标为

17PG(x1,x2,…xn)=

(x16x7)

7777计算全部着色模式为[(x1x2...xn)76(x1x2...xn)]

1717!6!7!C(7,n)n<7时为

71!1!...[7(n1)]!(8n)!n!(7n)!

9. 一个圆圈上有n个珠子,用n种颜色对珠子着色,要求颜色数目不少于n的方案数是多少?

解：（1）不动点置换有一个；

360（2）绕中心旋转i（1≤i≤n）角度，使得能够与不动的环重合。它对应n的置换是：n1 共(n－1)个；

（3）把n为奇数、偶数分两种情况分析：

i) n为奇数时：沿一颗珠子和其他剩余珠子的平分线绕180°，对应的置换是121n12共n个；

n2ii) n为偶数时：沿珠子平分线绕180°，对应的置换是2，共个。

34

n2故其轮换指标为

n11n(x(n1)xnxxPG(x1,x2,…xn)= ；

1n122)（n为奇数时）2n2nnn(x1(n1)xnx22)（n为偶数时）PG(x1,x2,…xn)= ；

3n210. 骰子的6个面上分别标有1,2,…,6,问有多少种不同的骰子？

解：下面有3种方法求解：

方法1 6个面分别标上不同的点数，相当于用6种不同的颜色对它着色，并且每种颜色出现且只出现一次，共有6！种方案。但这种方案经过正立方体的旋转可能会发生重合，全部方案上的置换群G显然有24个元素。由于每个面的着色全不相同，只有恒等置换σI 保持6！种方案不变，即c1(σI)=6!，c1(p)=0（p≠σI）。由Burnside引理知

l11c1()=(6!00)30

GG24方法2 在习题5中已求出关于正立方体6个面的置换群轮换指标，如果用m种颜色进行着色，则不同的着色方案数为

lm1(m63m412m38m2)

24严格的说，lm是至多用m种颜色着色的方案数。我们可以计算出l1=1,l2=10,l3=57,l4=240,l5=800,l6=2226。现令ni表示恰好用i种颜色着色的方案数，则由容斥原理知

n1=l1=1

2n2l21n18

33n3l3n221n130

444n4l4nn33221n168

5555n5l5nnn4433221n175

66666n6l6nnnn554433221n130

方法3 令R={c1,c2,…,c6}，w(ci)=wi(1≤i≤6)。正立方体6个面上的置换群G的轮换指标为

35 1622223(x6xx3xx8x6x1141232) PG(x1,x2,…,x6) =24于是F的全部模式表为

PG(w(r),w2(r),,w6(r))rRrRrR

14422[(w1w6)66(w1w6)(w1w6)3(w1w6)2(w1w6)224

3322238(w1w6)6(w1w6)]其中，w1w2w3w4w5w6项的系数就是用6种颜色对6个面着色的方案数，等于

16!30

241!1!1!11. 将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？

解： 令D={w1,w2,b1,b2},R={盒1，盒2}，四个球往两个盒子里放的放法是F：D→R。由于w1,w2是两个相同的白球，b1,b2是两个相同的黑球，由此确定出D上的置换群为

G={σI,(w1w2),(b1b2),(w1w2)(b1b2)}

其轮换指标为

1422PG(x1,x2,x3,x4) =(x12x1x2x2)

4于是F上的等价类个数为

l=PG(2,2,2,2)=

14(2222222)9

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上的全部模式表为

PG(x+y,x2+y2,x3+y3,x4+y4) =((xy)42(xy)2(x2y2)(x2y2)2)

=x4+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个；

36

14（3） 绕相对两顶点连线旋转120°，240°的置换，型为1232，有8个；

（4） 绕相对两边中点连线旋转180°的置换，型为24，有6个。

所以，该置换群的轮换指标为

182224PG（x1,x2,…,x6）=(x16x48x1x39x2)

24下面计算全部着色模式。这里，假设除了红色和蓝色外我们放绿球，则R={c1,c2,c3}，w(c1)=r，w(c2)=b，w(c3)=g，于是

F的全部模式表

1[(rbg)86(r4b4g4)28(rbg)2(r3b3g3)29(r2b2g2)4]

24其中，红色、蓝色各出现2次的方案数就是上述展开式中r2b2g4项的系数，即

18!4!(9)22

242!2!4!1!1!2!13. 长为n的透明的方格,用红、蓝、黄、绿4种颜色进行着色,试问有多少种不同的方案？

解：问题相当于用r,b,y,g构成长为n的字符串，将从左向右的字符顺序和从右向左的字符顺序看作时相同的，例如，yggrbr和rbrggy看作是相同的。

2n1n12n1群G：nn12

12n1根据 Pólya定理，不同的方案数应为：

1nN＝(442n12)

14. 用两种颜色对正六面体的6个面、8个顶点进行着色,问有多少种不同方案？转动使之一致作为一类处理.

解：对正六面体的6个面的置换群设为G，G的循环指数多项式为：

622232 P(G)=S16S1S43S1S26S28S3

设正六面体8个顶点的置换群为H，H的循环指数多项式为

82422P(H)=S16S49S28S1S3

P(GH)=P(G)P(H)=1232242{ S166S12S43S12S26S28S3 }{S186S49S28S12S3}

2(24)02{ S16S16S49S16S28S18S326S1 36S12S454S12S2S448S14S2S43S1S22(24)22622332732218S12S2S427S12S224S14S2S36S18S236S2S454S248S12S2S38S18S3248S32S44472S2S364S12S34}

37 所求的不同等价类数为

1{26623324623822}{28622924824}

5761{6448484832}{2562414428}

5761240552230

57615. 一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜色对8个面进行着色,试求其中4个顶点为红,两个顶点为蓝,黄和绿的面各4面的方案数.

注：正八面体可以看作是正方体的对偶，每一面用中心代表一个顶点，相交于一个顶点的3个面对应过3个中心的三角形，由此构成的6个顶点，8个面的几何图形。即可得到我们需要的正八面体的形状。

解：通过刚才我们的提示可以得到如下结论：可以把问题转换成对于正六面体的顶点和面的着色问题，转换成为要求给这个正六面体着色：用红、蓝两色对6个面进行着色；用黄、绿两种颜色对8个顶点进行着色,试求其中4个面为红,2个面为蓝；黄和绿的顶点各4个的方案数.

对正六面体的6个面的置换群设为G，G的循环指数多项式为：

622232 P(G)=S16S1S43S1S26S28S3

设正六面体8个顶点的置换群为H，H的循环指数多项式为

82422P(H)=S16S49S28S1S3

P(GH)=P(G)P(H)=1232242{ S166S12S43S12S26S28S3 }{S186S49S28S12S3}

2(24)所求的不同等价类数为

1[(rb)66(rb)2(r4b4)3(rb)2(r2b2)26(r2b2)38(r3b3)2]

241[(yg)86(y4g4)28(yg)2(y3g3)29(y2g2)4]

24所得的r4b2y4g4的系数即为所求：

16!2!3!18!2!2!2!4!613(1)668()9=2×7＝14

244!2!1!1！2!1!1!1!1!1!1!1!2!2!244!4! 所以符合题意的方案数为14种。

16. 用Pólya定理求多重集合M{a1,a2,,an}的r圆排列数.

解：可转化为有r颗珠子的项链可以着n种颜色的方法数。

（1）不动点置换有1个；

38

360i（1≤i≤r）角度，使得能够与不动的环重合。它对（2）绕中心旋转r应的置换是：r1 共(r－1)个；

（3）把r为奇数、偶数分两种情况分析：

i) r为奇数时：沿一颗珠子和其他剩余珠子的平分线绕180°，对应的置换是121r12共r个；

r2ii) r为偶数时：沿珠子平分线绕180°，对应的置换是2，共个。

故其轮换指标为

r11r(x1(r1)xrrx1x22)（r为奇数时）PG(x1,x2,…xn)= ；

2rr21r =(n(r1)nrnn2rr12)

1r =(n(r1)nrn2rr12)

2rrr(x(r1)xx22)（r为偶数时）PG(x1,x2,…xn)= ；

1r3r22rr =(n(r1)nn2)

3r2r17. 求n个顶点的简单图有多少个？

解：简单图指的是过两个顶点没有多于一条的边，而且不存在圈的图形。问题相当于对n个无标志顶点的完全图的(n1)条边，用两种颜色进行着色，求不同方案数的问题。比如两种颜色x,y，令着上色y的边从图中消去，得到一n个顶点的简单图。

例如3个顶点的无向图，有

G={(v1)(v2)(v3)，(v1v2v3)，(v3v2v1)，(v1)(v2v3)，(v2)(v1v3)，(v3)(v1v2)}

P(x,y)=[(xy)33(xy)(x2y2)2(x3y3)]

=x3+y3+xy2+x2y v1

v2 v3

从P(x,y)可知，对上图的三角形的边着色，其中3条边都用x着色的有1；同样

39

n216用x着色两条的、着色一条的、无一条着色的方案各为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)=16222(x19x1x28x36x2x4)

24令R={x, y}，w(x)=r, w(y)=1则

PG(r+1,r2+1,…, r6+1)=1[(r1)69(r1)2(r21)28(r31)26(r21)(r41))

24 =r6+r5+2r4+3r3+2r2+r+1

故4个结点的简单图共有11个，如图所示：

40