十一年-reachfor

第五章 Pólya计数理论
1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类.
解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|S
n
|＝5。
(123)(234)(5)(14)(23)

12345

1 2345

12345





23 145




13425




43215




12345
 
12345




34125

< br>

43215



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

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

（5）（12）（34）的置换的型为1< br>1
2
2
而S
n
中属于1
1
2
2型的元素个数为
个其共轭类为
（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的等价类的个数.
1
n
c
1
(a
i
)
，其中c
1
(ai
)表示在置换a
i
作用下保持不变解：根据Burnside引理
l
G
i1
5!
15
2!1!1
1
2
2< br>的元素个数，则有
c
1
(σ
I
)=n;
设在σ的作用下，A的元素在B中的个数为i，则
c
2
(σ)=n－2i；
1
若没有其他置换，则G诱出来的等价类个数为l=
[n(n2i)]ni< br>
2
3. 由0,1,6,8,9组成的n位数,如果把一个数调转过来读得到另一个数 ,则称这两
个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n位 数有
多少个？
解：该题可理解为相当于n位数，0，1，6，8，9这5个数存在一定的置换关系

31

对于置换群G={g
1
,g
2
}
g
1
为不动点置换，型为1
n
；为5
n
；
n

n

g
2
置换：（1n）(2(n-1))(3( n-2))…(


2

2

)

分为2种情况：
（1） n为奇数时
12
，但是只有中 间的数字是0，1，8的时候，才可能调
转过来的时候是相同的，所以这里的剩下的中间数字只能是有3 种。
即：个数为3×
5
n
2
n
2
n1
2

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

该置换群的轮换指标为
1
n
1
22
(55)5
n为偶数时，等价类的个数l =
22
1
n
n为奇数时，等价类的个数l=
(535
2
n1
2
n3n
)

4. 现有8个人计划去访问3个城市 ,其中有3个人是一家,另外有2个人是一家.
如果一家人必须去同一个城市,问有多少种方案？写出它 们的模式.
解：令D={d
1
,d
2
,…,d
8
}，其中，d
1
,d
2
,d
3
为一家，d
4
,d
5
为一家。R={c
1
,c
2
,c
3
},w(c
1
)=
α,w(c
2
)=β,w(c
3
)=γ.f:D→R是一种安排方案。根据题意，做D的一个5
分划 {d
1
,d< br>2
,d
3
},{d
4
,d
5
},{d
6
},{d
7
},d
8
},
要求f在每块中的元素取值 相同。对于{d
1
,d
2
,d
3
}，可以取α
3< br>＋β
3
＋γ
3
模式；
对于{d
4
,d
5
}，可以取α
2
＋β
2
＋γ
2
模式；对于{ d
6
},{d
7
},{d
8
}，可以取α＋β
＋γ 模式.所以，总的模式为
（α
3
＋β
3
＋γ
3
） （α
2
＋β
2
＋γ
2
）（α＋β＋γ）
3

5. 对正立方体6个面用红、蓝、绿3种颜色进行着色,问有多少种不同的方案？
又问3种颜 色各出现2次的着色方案有多少种？
解：正立方体6个面的置换群G有24个元素，它们是：
（1） 不动的置换，型为1
6
，有一个；
（2） 绕相对两面中心轴旋转 90°，270°的置换，型为1
2
4
1
，有6个；旋
转180°的 置换，型为1
2
2
2
，有3个；
（3） 绕相对两顶点连线旋转120°，240°的置换，型为3
2
，有8个；
（4） 绕相对两边中点连线旋转180°的置换，型为2
3
，有6个。
所以，该置换群的轮换指标为
P
G
（x
1
,x
2
,…,x
6
）=
等价类的个数为
1
622223
(x
1
6x
1
x
4
3x
1
x
2
8x
3
6x
2
)

24
32

l=P
G
(3,3,…,3)=
1
6< br>(363
3
33
2
3
2
83
2
63
3
)
=57
24
下面计算全部着色模式。这里 ，R={c
1
,c
2
,c
3
}，w(c
1
)=r，w(c
2
)=b，w(c
3
)=g，
于是
F的全部模式表
1
[(rbg)
6
6(rbg)
2
(r
4
b
4
g
4
)3(rbg)< br>2
(r
2
b
2
g
2
)
2
24

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

242!2!2!1!1!1!
6. 有一个3×3的正方形棋盘,若用红蓝两色对这9个方格 进行着色,要求两个位
红色,其余为蓝色,问有多少种方案？
解： 其置换群为：
不动置换：型为 1
9
，1个
沿中间格子及其对角线方向做旋转的置换：型为1
3
2
3
，4个
旋转90°和240°时的置换：型为1
1
4
2
， 2个
旋转180°时的置换 型为1
1
2
4
， 1个
1
93 234224
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
9
，（1＋x）
9
中x
2
项系数为C(9,2)= 36；
（2） 对应于1
3
2
3
，4(1＋x)
3
(1+x
2
)
3
中x
2
项系数为：
4[C(3,2)C(3,0)+C(3,0)C(3,1)]=24；
（3） 对应于1
1
4
2
2(1+x)(1+x
4
)
2
中x
2
项系数为0；
（4） 对应于1
1
2
4
(1+x)(1+x
2
)
4
中x
2
项系数为C(4,1)=4；

1
故x的系数为
(36244)8

8
2
7. 对正六角形的6个顶点用5种颜色进行着色.试问有多少种不同的方案,旋转
使之重合作为相同处理.
解：对该正六角形的6的顶点的置换群有12个，它们分别是：
(1) 不动点置换，型为1
6
，有1个；
(2) 旋转60°和300°的置换，型为6
1
，有2个；旋转120°和240°的
置换， 型为3
2
，有2个； 旋转180°的置换型为2
3
有1个；
(3) 绕对角连线旋转180°的置换 ，型为1
2
2
2
，有3个；
(4) 绕对边中点连线旋转180°的置换，型为2
3
，有3个。

33

所以，该置换群的轮换指标为
1
62223
(x2x2 x3xx3x
P
G
（x
1
,x
2
,…,x6
）=
163122
)

12
下面计算全部着色模式。 这里，R={c
1
,c
2
,c
3
,c
4
, c
5
}，不妨设w(c
1
)=r，w(c
2
)=b，
w(c
3
)=g，w(c
4
)=p，w(c
3
)=y，于 是
F的全部模式表
1
[(rbgpy)
6
2(r6
b
6
g
6
p
6
y
6
)2(r
3
b
3
g
3
p
3
y
3
)
2
12
3(r
2
b
2
 g
2
p
2
y
2
)(r
2
b
2
g
2
p
2
y
2
)
2
3 (r
2
b
2
g
2
p
2
y
2
)
3
]

其中，用这5种颜色着色的方案数就是上述展开式中r
2
bgpy, rb
2
gpy,
rbg
2
py,rbgp
2
y, rbgpy
2
项的系数之和，即
16!
(5)150

122!1!1!1!1!
8. 在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可 供选择的方案？
（旋转木马只能转动不能翻转）
解： 设想另一个正7边形与不动的正7边形 完全重合，并且顶点标记相同，那
360

么绕中心旋转
i
（1≤i ≤7）角度，使得能够与不动的正7边形重合。它
7
对应的置换是：7
1
共6个。故其轮换指标为
P
G
(x
1
,x
2
,…x
n
)=
1
7
(x
1
6x
7
)

71
7
777
计算全部着色模式为
[(x
1
x
2
...x
n
)
7
6(x
1
x
2
...x
n
)]

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
的置换是：n
1
共(n－1)个；
（3）把n为奇数、偶数分两种情况分析：
i) n为奇数时：沿一 颗珠子和其他剩余珠子的平分线绕180°，对应的置
换是
12
1
n12
共n个；
34

ii) n为偶数时：沿珠子平分线绕180°，对应的置换是
2
，共个。
故其轮换指标为
n1
1
n
(x
1
(n1)x
n
n x
1
x
2
2
)
（n为奇数时）P
G
(x< br>1
,x
2
,…x
n
)= ；
2n
n
2
n
2
2n
n
n
(x(n1)xx
22
)
（n为偶数时）P
G
(x
1
,x
2
,…x
n
)= ；
1n
3n2
10. 骰子的6个面上分别标有1,2,…,6,问有多少种不同的骰子？
解：下面有3种方法求解：
方法1 6个面分别标上不同的点数，相当于用6种不同的颜色对它着色，
并且每种颜色出现 且只出现一次，共有6！种方案。但这种方案经过正立方
体的旋转可能会发生重合，全部方案上的置换群 G显然有24个元素。由于
每个面的着色全不相同，只有恒等置换σ
I
保持6！种方 案不变，即c
1
(σ
I
)=6!，
c
1
(p)=0 （p≠σ
I
）。由Burnside引理知

l
1
1

c
1
(

)
=
(6!00) 30

G

G
24
方法2 在习题5中已求出关于正立 方体6个面的置换群轮换指标，如果用
m种颜色进行着色，则不同的着色方案数为
l
m

1
(m
6
3m
4
12m
3< br>8m
2
)

24
严格的说，l
m
是至多 用m种颜色着色的方案数。我们可以计算出
l
1
=1,l
2
=10, l
3
=57,l
4
=240,l
5
=800,l
6
=2226。现令n
i
表示恰好用i种颜色着色的方
案数，则由容斥原理知
n
1
=l
1
=1

2

n< br>2
l
2



1


n
1
8



3

3

n
3
l
3


n

2

2


1


n
1
 30



4

4

4


n
4
l
4


nn
3

3

2

2

1


n
1
68



5

5

5

5

 
n
5
l
5


nnn
4

4

3

3

2
2


1


n
1
75



35


6

6

6

6

6

 
n
6
l
6


nnnn
< br>5

5

4

4

3
< br>3

2

2


1

< br>n
1
30


方法3 令R={c1
,c
2
,…,c
6
}，w(c
i
)=wi
(1≤i≤6)。正立方体6个面上的置换
群G的轮换指标为
1
62 2223
(x
1
6x
1
x
4
3x
1< br>x
2
8x
3
6x
2
)
P
G
(x
1
,x
2
,…,x
6
) =
24
于是F的全部模式表为
P
G
(

w(r) ,

w
2
(r),,

w
6
(r))< br>rRrRrR

1
4422
[(w
1


w
6
)
6
6(w
1


w
6
)(w
1


w
6
)3(w< br>1


w
6
)
2
(w
1


w
6
)
2
24

33
2< br>22
3
8(w
1


w
6
) 6(w
1


w
6
)]

其中，w1
w
2
w
3
w
4
w
5
w6
项的系数就是用6种颜色对6个面着色的方案数，
等于
16!
30

241!1!

1!
11. 将 两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不
同的方法？列出全部方案.又问 每盒中有两个球的方法有多少种？
解： 令D={w
1
,w
2
,b
1
,b
2
},R={盒1，盒2}，四个球往两个盒子里放的放法是F：D< br>→R。由于w
1
,w
2
是两个相同的白球，b
1
,b
2
是两个相同的黑球，由此确定出
D上的置换群为
G={σ
I,(w
1
w
2
),(b
1
b
2
),( w
1
w
2
)(b
1
b
2
)}
其轮换指标为
P
G
(x
1
,x
2
,x< br>3
,x
4
) =
1
422
(x
1
 2x
1
x
2
x
2
)

4
于是F上的等价类个数为
1
4
(222
2
22
2
)9

4
这9个不同方案分别为
l=P
G
(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上的全部模式表为
P
G
(x+ y,x
2
+y
2
,x
3
+y
3
,x
4
+y
4
) =
((xy)
4
2(xy)
2
(x
2
y
2
)(x
2
y
2
)
2
)

=x
4
+2x
3
y+3x2
y
2
+2xy
3
+y
4

盒1与盒 2中各放两个球的方案数是x
2
y
2
项的系数，即为3。具体方案为
(ww,bb), (wb,wb), (bb,ww)
36

1
4

12. 将2个红球和2个蓝球放在正六面体的顶点上,问有多少种不同的方案？
解： 正立方体8个点的置换群G有24个元素，它们是：
（1） 不动的置换，型为1
8
，有1个；
（2） 绕相对两面中心轴旋转90°，270° 的置换，型为4
2
，有6个；旋转
180°的置换，型为2
4
，有3 个；
（3） 绕相对两顶点连线旋转120°，240°的置换，型为1
2
3
2
，有8个；
（4） 绕相对两边中点连线旋转180°的置换，型为2
4
，有6个。
所以，该置换群的轮换指标为
1
82224
P
G
（x1
,x
2
,…,x
6
）=
(x
1
6 x
4
8x
1
x
3
9x
2
)

24
下面计算全部着色模式。这里，假设除了红色和蓝色外我们放绿球，则
R={c< br>1
,c
2
,c
3
}，w(c
1
)=r，w( c
2
)=b，w(c
3
)=g，于是
F的全部模式表
1
[(rbg)
8
6(r
4
b
4
g
4
)
2
8(rbg)
2
(r
3
b
3
g
3
)
2
9(r
2
b
2
g
2
)
4
]

24
其中，红色、蓝色各出现2 次的方案数就是上述展开式中r
2
b
2
g
4
项的系数，即
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＝
1
n
(44
2

n1



2

)

14. 用两种颜色对正六面体的6个面、 8个顶点进行着色,问有多少种不同方案？
转动使之一致作为一类处理.
解：对正六面体的6个面的置换群设为G，G的循环指数多项式为：
622232
P(G)=
S
1
6S
1
S
4
3S
1< br>S
2
6S
2
8S
3

设正六面体8个顶点的置换群为H，H的循环指数多项式为
82422
P(H)=< br>S
1
6S
4
9S
2
8S
1
S
3

P(G

H)=P(G)P(H)=

1
2324
{ S
1
6
6S
1
2
S
4
3S
1
2
S
2
6S
2
8S
3
2
}{S
1
8
6S
4
9S
2
8S
1
2
S
3
2
}

2
(24)
37


1
02
{ S
1
6S
1
6
S
4
9S
1
6< br>S
2
8S
1
8
S
3
6S
1 36S
1
2
S
4
54S
1
2
S
2
S
4
48S
1
4
S
2
S4
3S
1
S
2
2
(24)
22622332 732222
18S
1
2
S
2
S
4
2 7S
1
2
S
2
24S
1
4
S
2
S
3
6S
1
8
S
2
36S
2
S
4
54S
2
48S
1
2
S
2
S
3
8S
1
8
S
3
48S
3
S
4
444
72S
2
S
3
64S< br>1
2
S
3
}
所求的不同等价类数为
1
{ 2
6
62
3
32
4
62
3
 82
2
}{2
8
62
2
92
4
82
4
}

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

576
1
240552230

576

15. 一个正八面体,用红、蓝两色对6个顶点进行着色；用黄、绿两种颜 色对8
个面进行着色,试求其中4个顶点为红,两个顶点为蓝,黄和绿的面各4面的方
案数.
注：正八面体可以看作是正方体的对偶，每一面用中心代表一个顶点，相交于一
个顶点的3个面 对应过3个中心的三角形，由此构成的6个顶点，8个面的
几何图形。即可得到我们需要的正八面体的形 状。
解：通过刚才我们的提示可以得到如下结论：可以把问题转换成对于正六面体的
顶点和面 的着色问题，转换成为要求给这个正六面体着色：用红、蓝两色对
6个面进行着色；用黄、绿两种颜色对 8个顶点进行着色,试求其中4个面为
红,2个面为蓝；黄和绿的顶点各4个的方案数.
对正六面体的6个面的置换群设为G，G的循环指数多项式为：

622232
P(G)=
S
1
6S
1
S
4
3S
1
S
2
6S
2
8S
3
设正六面体8个顶点的置换群为H，H的循环指数多项式为
82422
P(H )=
S
1
6S
4
9S
2
8S
1S
3

P(G

H)=P(G)P(H)=
1
2324
{ S1
6
6S
1
2
S
4
3S
1
2
S
2
6S
2
8S
3
2
}{S< br>1
8
6S
4
9S
2
8S
1
2
S
3
2
}

2
(24)
所求的不同等价类数为
1
[(rb)
66(rb)
2
(r
4
b
4
)3(rb)2
(r
2
b
2
)
2
6(r
2b
2
)
3
8(r
3
b
3
)2
]

24

1
[(yg)
8
6 (y
4
g
4
)
2
8(yg)
2
(y
3
g
3
)
2
9(y
2
g
2
)
4
]

24
所得的r
4
b
2< br>y
4
g
4
的系数即为所求：
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{a
1
,a
2
,,a
n
}
的r圆排列数.
解：可转化为有r颗珠子的项链可以着n种颜色的方法数。
（1）不动点置换有1个； 360

i
（1≤i≤r）角度，使得能够与不动的环重合。它对（2）绕中心旋 转
r
应的置换是：r
1
共(r－1)个；
i)
（3）把r为奇数、偶数分两种情况分析：
r为奇数时：沿一颗珠子和其他剩余珠子的平分线 绕180°，对应的置换
是
12
1
r1
2
共r个；
r
2
ii) r为偶数时：沿珠子平分线绕180°，对应的置换是
2
，共个。
故其轮换指标为
r1
1
r
(x
1
(r1)x
r
r x
1
x
2
2
)
（r为奇数时）P
G
(x< br>1
,x
2
,…x
n
)= ；
2r
r
2
1
r
=
(n(r1)nrnn
2r
r1
2
)

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

2 r
r
r
(x
1
(r1)x
r
x
2< br>2
)
（r为偶数时）P
G
(x
1
,x
2,…x
n
)= ；
3r2
2
r
r
=
(n(r1)nn
2
)

3r2
r
17. 求n个顶点的简单图有多少个？
解：简单图指的是过两个顶点没有多于一条的边，而且不存在圈的图形 。问题相
当于对n个无标志顶点的完全图的
(n1)
条边，用两种颜色进行着色，求 不
同方案数的问题。比如两种颜色x,y，令着上色y的边从图中消去，得到一
n个顶点的简单 图。
例如3个顶点的无向图，有
G={(v
1
)(v
2
)(v
3
)，(v
1
v
2
v
3
)，(v< br>3
v
2
v
1
)，(v
1
)(v
2< br>v
3
)，(v
2
)(v
1
v
3
)， (v
3
)(v
1
v
2
)}
P(x,y)=
[(xy)
3
3(xy)(x
2
y
2
)2(x
3
y
3
)]

=x
3
+y
3
+xy
2
+x
2
y v
1




39
n
2
1
6

v
2
v
3

从P(x,y)可知，对上图的三角形的边着色，其中3条边都用x着色的有1；
同样
用x着色两条的、着色一条的、无一条着色的方案各为1（多项式各项的系
数）。把用y着色的边消除 得到以下的图形。



再看n=4的情况.令e
1
=( v
1
v
2
)，e
2
=(v
2
v
3
)，e
3
=(v
3
v
4
)，e
4
=(v
4
v
1
)，e
5
=(v
1
v
3
)，
e
6
=(v
2
v
4
)，则{v< br>1
,v
2
,v
3
,v
4
}上的每个置换确定 了{e
1
,e
2
,e
3
,e
4
,e
5
,e
6
}上的置换，后
者构成边集合上的置换群G. G中有1
6
型的置换1个，1
2
2
2
型的置换9个，
3
2< br>型的置换8个，2
1
4
1
型的置换6个.G的轮换指标为：
P
G
(x
1
,x
2
,…,x
6
)=
1
6222
(x
1
9x
1
x
2
8x
3
6x
2
x
4
)

24
令R={x, y}，w(x)=r, w(y)=1则
P
G
(r+1,r
2
+1,…, r
6
+1)=< br>1
[(r1)
6
9(r1)
2
(r
2
1)
2
8(r
3
1)
2
6(r
2
1)(r
4
1))

24
= r
6
+r
5
+2r
4
+3r
3
+2r2
+r+1
故4个结点的简单图共有11个，如图所示：






40