李凡长版 组合数学课后习题答案 习题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的等价类的个数.

1n?c1(ai)，其中c1(ai)表示在置换ai作用下保持不变解：根据Burnside引理l?Gi?15!?152!1!1122的元素个数，则有 c1(σI)=n;

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

c2(σ)=n－2i；

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

23. 由0,1,6,8,9组成的n位数,如果把一个数调转过来读得到另一个数,则称这两

个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n位数有多少个？

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

31

对于置换群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×5n2n2n?12

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

82

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个。

33

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

162223(x?2x?2x?3xx?3xPG（x1,x2,…,x6）=163122) 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?3(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个。故其轮换指标为 PG(x1,x2,…xn)=

17(x1?6x7) 717777计算全部着色模式为[(x1?x2?...?xn)7?6(x1?x2?...?xn)]

17!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个；

34

ii) n为偶数时：沿珠子平分线绕180°，对应的置换是2，共个。 故其轮换指标为

n?11n(x1?(n?1)xn?nx1x22)（n为奇数时）PG(x1,x2,…xn)= ； 2nn2n22nnn(x?(n?1)x?x22)（n为偶数时）PG(x1,x2,…xn)= ； 1n3n210. 骰子的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 ???????? 35

?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的轮换指标为

1622223(x1?6x1x4?3x1x2?8x3?6x2) 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)}

其轮换指标为 PG(x1,x2,x3,x4) =

1422(x1?2x1x2?x2) 4于是F上的等价类个数为

14(2?2?22?2?22)?9 4这9个不同方案分别为

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

(?，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)

36

1412. 将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个。 所以，该置换群的轮换指标为

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看作是相同的。

群G：??2?n?1n??12?n??1?????nn?1?? 12?n21????根据 Pólya定理，不同的方案数应为：

N＝

1n(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)=

12324{ S16?6S12S4?3S12S2?6S2?8S32 }{S18?6S4?9S2?8S12S32} 2(24)37

?11424210343102{ S1?6S16S4?9S16S2?8S18S3?6S1 ?36S12S4?54S12S2S4?48S14S2S4?3S1S22(24)22622332732222?18S12S2S4?27S12S2?24S14S2S3?6S18S2?36S2S4?54S2?48S12S2S3?8S18S3?48S3S4444?72S2S3?64S12S3}所求的不同等价类数为

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)=

12324{ S16?6S12S4?3S12S2?6S2?8S32 }{S18?6S4?9S2?8S12S32} 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种。

38

16. 用Pólya定理求多重集合M?{??a1,??a2,?,??an}的r圆排列数. 解：可转化为有r颗珠子的项链可以着n种颜色的方法数。

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

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

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

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(x1?(r?1)xr?x22)（r为偶数时）PG(x1,x2,…xn)= ； 3r22rr =(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

39

n216

v2 v3

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

用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

本文来源：https://www.bwwdw.com/article/fhpr.html