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

-----WORD格式--可编辑--专业资料-----

第五章 Pólya计数理论

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

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

n

(123)(234)(5)(14)(23)



123451234512345







231451342543215





1234512345







3412543215





12345







21435



(12)(34)(5)

（5）（12）（34）的置换的型为12而S中属于12型的元素个数为个

1212

n

其共轭类为

（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的等价类的个数.

5!

15

2!1!12

12

1

n



c(a)l

1i

，其中c(a)表示在置换a作用下保持不变的元素解：根据Burnside引理

1ii

G

i1

个数，则有

c(σ)=n;

1

I

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

c(σ)=n－2i；

2

1

若没有其他置换，则G诱出来的等价类个数为l=

[n(n2i)]ni

2

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

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

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

对于置换群G={g,g}

12

g为不动点置换，型为1；为5；

1

nn

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

nn



g置换：（1n）(2(n-1))(3(n-2))…()

2



22



分为2种情况：

（1） n为奇数时 ，但是只有中间的数字是0，1，8的时候，才可能调转过来

12

的时候是相同的，所以这里的剩下的中间数字只能是有3种。

即：个数为3×

5

n

2

n

2

n1

2

n

2

（2） n为偶数时 ，个数为

2

5

该置换群的轮换指标为

11

n

n为偶数时，等价类的个数l=

(55)5

22

22

1

n

n为奇数时，等价类的个数l=

(535)

2

n1

2

n3n

4. 现有8个人计划去访问3个城市,其中有3个人是一家,另外有2个人是一家.如果一

家人必须去同一个城市,问有多少种方案？写出它们的模式.

解：令D={d,d,…,d}，其中，d,d,d为一家，d,d为一家。R={c,c,c},w(c)=α,w(c)=

128123451231

2

β,w(c)=γ.f:D→R是一种安排方案。根据题意，做D的一个5分划

3

{d,d,d},{d,d},{d},{d},d},

12345678

要求f在每块中的元素取值相同。对于{d,d,d}，可以取α＋β＋γ模式；对于

123

333

{d,d }，可以取α＋β＋γ模式；对于{d},{d},{d}，可以取α＋β＋γ模式.

45678

222

所以，总的模式为

（α＋β＋γ）（α＋β＋γ）（α＋β＋γ）

333222

3

5. 对正立方体6个面用红、蓝、绿3种颜色进行着色,问有多少种不同的方案？又问3

种颜色各出现2次的着色方案有多少种？

解：正立方体6个面的置换群G有24个元素，它们是：

（1） 不动的置换，型为1，有一个；

6

（2） 绕相对两面中心轴旋转90°，270°的置换，型为14，有6个；旋转180°

21

的置换，型为12，有3个；

22

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

2

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

3

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

P（x,x,…,x）=

G126

等价类的个数为

l=P(3,3,…,3)= =57

G

1

632223

(3633338363)

24

1

622223

(x6xx3xx8x6x)

1141232

24

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

123123

F的全部模式表

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

1

[(rbg)6(rbg)(rbg)3(rbg)(rbg)

6244422222

24

33322223

8(rbg)6(rbg)]

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

222

即

16!3!

(326)6

242!2!2!1!1!1!

6. 有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位红色,

其余为蓝色,问有多少种方案？

解： 其置换群为：

不动置换：型为 1，1个

9

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

33

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

12

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

14

1

93234224

P(x)=

(1x)4(1x)(1x)2(1x)(1x)(1x)(1x)

8

我们设定x为红色，1为蓝色，即转化为求x的系数

2

（1） 对应于1，（1＋x）中x项系数为C(9,2)=36；

992

（2） 对应于12，4(1＋x)(1+x)中x项系数为：

333232

4[C(3,2)C(3,0)+C(3,0)C(3,1)]=24；

（3） 对应于14 2(1+x)(1+x)中x项系数为0；

12422

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

14242



1

故x的系数为

(36244)8

8

2

7. 对正六角形的6个顶点用5种颜色进行着色.试问有多少种不同的方案,旋转使之重

合作为相同处理.

解：对该正六角形的6的顶点的置换群有12个，它们分别是：

(1) 不动点置换，型为1，有1个；

6

(2) 旋转60°和300°的置换，型为6，有2个；旋转120°和240°的置换，

1

型为3，有2个； 旋转180°的置换型为2有1个；

23

(3) 绕对角连线旋转180°的置换 ，型为12，有3个；

22

(4) 绕对边中点连线旋转180°的置换，型为2，有3个。

3

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

1

62223

P（x,x,…,x）=

G126

(x2x2x3xx4x)

163122

12

下面计算全部着色模式。这里，R={c,c,c,c,c}，不妨设w(c)=r，w(c)=b，w(c)=g，

12345123

w(c)=p，w(c)=y，于是

43

F的全部模式表

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

1

[(rbgpy)2(rbgpy)2(rbgpy)

666666333332

12

22222222222222223

3(rbgpy)(rbgpy)4(rbgpy)]

其中，用这5种颜色着色的方案数就是上述展开式中rbgpy, rbgpy, rbgpy,rbgpy,

2222

rbgpy项的系数之和，即

2

16!

(5)150

122!1!1!1!1!

8. 在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可供选择的方案？（旋

转木马只能转动不能翻转）

解： 设想另一个正7边形与不动的正7边形完全重合，并且顶点标记相同，那么绕中

360



心旋转角度，使得能够与不动的正7边形重合。它对应的置换是：（1≤i≤7）

i

7

7 共6个。故其轮换指标为

1

1

7

P(x,x,…x)=

G12n

(x6x)

17

7

777

计算全部着色模式为

[(xx...x)6(xx...x)]

12n12n

7

1

7

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）绕中心旋转（1≤i≤n）角度，使得能够与不动的环重合。它对应的置

i

n

换是：n 共(n－1)个；

1

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

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

12

1

n1

2

共n个；

n

2

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

2

故其轮换指标为

n1

1

n

(x(n1)xnxx)

1n12

2

（n为奇数时）P(x,x,…x)= ；

G12n

2n

n

2

2n

n

n

(x(n1)xx)

1n2

2

（n为偶数时）P(x,x,…x)= ；

G12n

3n2

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

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

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

方法1 6个面分别标上不同的点数，相当于用6种不同的颜色对它着色，并且每

种颜色出现且只出现一次，共有6！种方案。但这种方案经过正立方体的旋转可能

会发生重合，全部方案上的置换群G显然有24个元素。由于每个面的着色全不相

同，只有恒等置换σ 保持6！种方案不变，即c(σ)=6!，c(p)=0（p≠σ）。由

I1I1I

Burnside引理知

=

lc()

1

1



1



(6!00)30

G



G

24

方法2 在习题5中已求出关于正立方体6个面的置换群轮换指标，如果用m种颜

色进行着色，则不同的着色方案数为

l(m3m12m8m)

m

1

6432

24

严格的说，l是至多用m种颜色着色的方案数。我们可以计算出

m

l=1,l=10,l=57,l=240,l=800,l=2226。现令n表示恰好用i种颜色着色的方案数，

123456i

则由容斥原理知

n=l=1

11



2

nln8

221





1





33



nlnn30

3321



21





444



nlnnn68

44321



321





5555



nlnnnn75

554321



4321





66666



nlnnnnn30

6654321



54321



方法3 令R={c,c,…,c}，w(c)=w(1≤i≤6)。正立方体6个面上的置换群G的

126ii

轮换指标为

1

622223

(x6xx3xx8x6x)

1141232

P(x,x,…,x) =

G126

24

于是F的全部模式表为

P(w(r),w(r),,w(r))

G



26

rRrRrR

1

4422

[(ww)6(ww)(ww)3(ww)(ww)

1616161616



622

24

3322

23

8(ww)6(ww)]

1616



--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

其中，wwwwww项的系数就是用6种颜色对6个面着色的方案数，等于

123456

16!

30

241!1!1!



11. 将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方

法？列出全部方案.又问每盒中有两个球的方法有多少种？

解： 令D={w,w,b,b},R={盒1，盒2}，四个球往两个盒子里放的放法是F：D→R。

1212

由于w,w是两个相同的白球，b,b是两个相同的黑球，由此确定出D上的置换

1212

群为

G={σ,(ww),(bb),(ww)(bb)}

I12121212

其轮换指标为

1

422

P(x,x,x,x) =

G1234

(x2xxx)

1122

4

于是F上的等价类个数为

1

422

l=P(2,2,2,2)=

G

(22222)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上的全部模式表为

P(x+y,x+y,x+y,x+y) =

G

223344

((xy)2(xy)(xy)(xy))

4222222

=x+2xy+3xy+2xy+y

432234

盒1与盒2中各放两个球的方案数是xy项的系数，即为3。具体方案为

22

(ww,bb), (wb,wb), (bb,ww)

12. 将2个红球和2个蓝球放在正六面体的顶点上,问有多少种不同的方案？

解： 正立方体8个点的置换群G有24个元素，它们是：

（1） 不动的置换，型为1，有1个；

8

（2） 绕相对两面中心轴旋转90°，270°的置换，型为4，有6个；旋转180°

2

的置换，型为2，有3个；

4

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

22

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

4

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

P（x,x,…,x）=

G126

1

82224

(x6x8xx9x)

14132

24

1

4

下面计算全部着色模式。这里，假设除了红色和蓝色外我们放绿球，则R={c,c,c}，

123

w(c)=r，w(c)=b，w(c)=g，于是

123

F的全部模式表

1

[(rbg)6(rbg)8(rbg)(rbg)9(rbg)]

84442233322224

24

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

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

224

18!4!

(9)

22

242!2!4!1!1!2!

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

案？

解：问题相当于用r,b,y,g构成长为n的字符串，将从左向右的字符顺序和从右向左的

字符顺序看作时相同的，例如，yggrbr和rbrggy看作是相同的。

2n1n12n1







群G：



nn112n21





根据 Pólya定理，不同的方案数应为：



1

n



N＝

(44)

2



n1

2

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

之一致作为一类处理.

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

622232

P(G)=

S6SS3SS6S8S

1141223

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

24228

9S8SSS6S

21314

P(H)=

P(GH)=P(G)P(H)=



{ S6SS9SS8SS6S 36SS54SSS48SSS3SS

1

23246222822

{ S6SS3SS6S8S }{S6S9S8SS}

114122314213

2

(24)

1

1424210343102668224

114121311412412412

2

(24)

22622332732222224828

18SSS27SS24SSS6SS36SS54S48SSS8SS48SS

12412123122421231334

所求

4442

72SS64SS}

2313

的不同等价类数为

1

{262326282}{2629282}

634328244

576

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

1

576

1

240552230

576

15. 一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜色对8个面进

行着色,试求其中4个顶点为红,两个顶点为蓝,黄和绿的面各4面的方案数.

注：正八面体可以看作是正方体的对偶，每一面用中心代表一个顶点，相交于一个顶

点的3个面对应过3个中心的三角形，由此构成的6个顶点，8个面的几何图形。

即可得到我们需要的正八面体的形状。

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

解：通过刚才我们的提示可以得到如下结论：可以把问题转换成对于正六面体的顶点

和面的着色问题，转换成为要求给这个正六面体着色：用红、蓝两色对6个面进

行着色；用黄、绿两种颜色对8个顶点进行着色,试求其中4个面为红,2个面为蓝；

黄和绿的顶点各4个的方案数.

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

622232

P(G)=

S6SS3SS6S8S

1141223

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

82422

P(H)=

S6S9S8SS

14213

P(GH)=P(G)P(H)=



1

23246222822

{ S6SS3SS6S8S }{S6S9S8SS}

114122314213

2

(24)

所求的不同等价类数为

1

[(rb)6(rb)(rb)3(rb)(rb)6(rb)8(rb)]

62442222223332

24

[(yg)6(yg)8(yg)(yg)9(yg)]

1

84422332224

24

所得的rbyg的系数即为所求：

4244

16!2!3!18!2!2!2!4!



613(1)668()9



4!4!244!2!1!1！2!1!241!1!1!1!1!1!2!2!

=2×7＝14



所以符合题意的方案数为14种。

16. 用Pólya定理求多重集合

Maaa



{,,,}

12

n

的r圆排列数.

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

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

360



i

（1≤i≤r）角度，使得能够与不动的环重合。它对应的置（2）绕中心旋转

r

换是：r 共(r－1)个；

1

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

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

r1

2

12

1

共r个；

r

2

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

2

故其轮换指标为

r1

1

r

(x(r1)xrxx)

1r12

2

（r为奇数时）P(x,x,…x)= ；

G12n

2r

r

2

1

r

=

(n(r1)nrnn)

2r

r1

2

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

1

r

=

(n(r1)nrn)

2r

r1

2

2r

r

r

(x(r1)xx)

1r2

2

（r为偶数时）P(x,x,…x)= ；

G12n

3r2

2r

r

2

(n(r1)nn)

=

3r2

r

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

解：简单图指的是过两个顶点没有多于一条的边，而且不存在圈的图形。问题相当于

对n个无标志顶点的完全图的条边，用两种颜色进行着色，求不同方案数

(n1)

的问题。比如两种颜色x,y，令着上色y的边从图中消去，得到一n个顶点的简单

图。

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

G={(v)(v)(v)，(vvv)，(vvv)，(v)(vv)，(v)(vv)，(v)(vv)}

123123321123213312

P(x,y)=

[(xy)3(xy)(xy)2(xy)]

32233

=x+y+xy+xy v

3322

1

v v

23

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

用x着色两条的、着色一条的、无一条着色的方案各为1（多项式各项的系数）。

把用y着色的边消除得到以下的图形。

再看n=4的情况.令e=(vv)，e=(vv)，e=(vv)，e=(vv)，e=(vv)，e=(vv)，

112223334441513624

则{v,v,v,v}上的每个置换确定了{e,e,e,e,e,e}上的置换，后者构成边集合上的

1234123456

置换群G. G中有1型的置换1个，12型的置换9个，3型的置换8个，24型

622211

的置换6个.G的轮换指标为：

P(x,x,…,x)=

G126

1

6222

(x9xx8x6xx)

112324

24

n

2

1

6

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

P(r+1,r+1,…, r+1)=

G

26

1

[(r1)9(r1)(r1)8(r1)6(r1)(r1))

62223224

24

=r+r+2r+3r+2r+r+1

65432

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

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----