赞美长城的句子-恶魔小丑天赋

组合数学试题集
一.简单题目
可以根据需要改成选择题或者填空题 < br>1．在1到9999之间，有多少个每位上数字全不相同而且由
奇数构成的整数？（参见课本21 页）
解：该题相当于从“
1
，
3
，
5
，
7
，
9
”五个数字中分别选出
1
，
2
，
3
，
4
作排列的方案数；


（
1
）选
1
个，即构成
1
位数，共有
P
5
个；


（
2
）选
2
个，即构成两位数，共有
P5
个；


（
3
）选
3
个，即构 成
3
位数，共有
P
5
个；


（4
）选
4
个，即构成
4
位数，共有
P
5
个；

1234

由加法法则可知，所求的整数共有：
P< br>5
P
5
P
5
P
5
205
个 。

1
2
3
4
2．一教室有两排，每排8个座位，今有14 名学生，问按下
列不同的方式入座，各有多少种做法？（参见课本21页）
（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；
（2）要求前排至少坐5人，后排至少坐4人。
解：（
1
）因为就坐是有次序的，所有是排列问题。

5
人 坐前排，其坐法数为
P(8,5)
，
4
人坐后排，其坐法数为
P(8 ,4)
，


剩下的
5
个人在其余座位的就坐方式有
P(7,5)
种，


根据乘法原理，就座方式总共有：

P(8,5)gP(8,4)gP(7,5)28449792000
（种）


（
2
）因前排至少需坐
6
人，最多坐
8人，后排也是如此。

可分成三种情况分别讨论：

①

前排恰好坐
6
人，入座方式有
C(14,6)P(8,6)P(8,8)
；

②

前排恰好坐
7
人，入座方式有
C(14,7 )P(8,7)P(8,7)
；

③

前排恰好坐
8
人，入座方式有
C(14,8)P(8,8)P(8,6)
；

各类入座方式互相不同，由加法法则，总的入座方式总数为：

C(1 4,6)P(8,6)P(8,8)C(14,7)P(8,7)P(8,7)C(14,8)P(8,8) P(8,6)


10
3．一位学者要在一周内安排50个小时的工作时 间，而且每天至少工作5小时，
问共有多少种安排方案？（参见课本21页）
解：用
x
i
表示第
i
天的工作时间，
i1,2,L,7
，则问题 转化为求不定方程

x
1
x
2
x
3
 x
4
x
5
x
6
x
7
50
的整数解的组数，且
x
i
5
，于是又可以转化为求
不定方程
y
1
y
2
y
3
y
4
y
5
y
6
y
7
15
的整数解的组数。

该问题等价于：将
15
个没有区别的球，放入
7
个不同的盒子中，每盒球数 不限，即相
异元素允许重复的组合问题。

故安排方案共有：
RC(,15)C(1571,15)54264

（种）


另解：

因为允许
y
i0
，所以问题转化为长度为
1
的
15
条线段中间有
1 4
个空，再加上前后两
个空，共
16
个空，在这
16
个空中 放入
6
个“＋”号，每个空放置的“＋”号数不限，未放
“＋”号的线段合成一条线段 ，求放法的总数。从而不定方程的整数解共有：

RC(,6)C(1661,6)

即共有
54 264
种安排方案。

212019181716
54264
（组）

654321
4.求下列函数的母函数:

{n(n1)}
；（参见课本51页）

母函数为：

2 x2x2x
2
G(x)

n(n1)x

n(n1 )x2

nx
；
323
(1x)(1x)(1x)
n0n0n0

n

n

n

方法二：


G(x)

n(n1)x00x
n
n0
2


2

n

n1

x
n2
2n2

x



n0

n2
x


n2

n1

xx
n
n0


< br>2

x

x
2


x
n2

x
2

1x

n0



2x
2


1x

3< /p>

5.求下列函数的母函数:
{n(n2)}
；（参见课本51页）

母函数为：

2xx3xx
2
G(x)
< br>n(n2)x

n(n1)x

nx
。 323
(1x)(1x)(1x)
n0n0n0

n

n

n

方法二：

G(x)

n(n2)x


n1

n2

x


n1

x

x
nnnn< br>n0

n0n0n0




x
n2




x
n1

n0n0
2




11

n2


n1




x< br>



x


1x

n0

n0

1x



x

x

1211





32
1x1x1x1x

1x1x
 


3xx
2


1x
3
6．利用递推关系求下列和：
S
n


k(k2)
（参见课本第92页）
k0
n
显然，
S
n
 S
n1
n(n2)
，

同理对应的齐次方程的特征根为
1
，特解为
S
n
A(1)
n
A
，

*
n(Bn
2
CnD)Bn
3
Cn
2< br>Dn
，

非齐次方程的特解为：
S
n

所以，非齐次方程的通解为：
S
n
Bn
3
Cn
2
DnA
，


初始条件为：
S
0< br>0,S
1
3,S
2
11,S
3
26
，代入上式，可得


S
0
A0
，
S
1
BCDA3
，
S
2
8B4C2DA 11
，

S
3
27B9C3DA26
，解得：< br>A0
，
B
17
3
，
C
，
D
，

36
2
所以

S
n
n
3
n
2
n

方法二：

1
3
3
2
7
6
n(n1)(2n7)

6
显然，
S
n
S
n1
n(n2)
，类似可得，
S
n1
S
n2
(n1)(n1)
，

两式相减得
S
n
2S
n1
S
n 2
2n1
，

同理可得
S
n12S
n2
S
n3
2(n1)1
，两式再相减得< br>
S
n
3S
n1
3S
n2
Sn3
2
，同理得
S
n1
3S
n2
 3S
n3
S
n4
2
，

两式再相减，可得关于
S
n
的齐次定解问题：


S
n
4S
n1
6S
n2
4S
n3
S
n4
0


S0,S3,S11,S26
123

0

由（
1
）知，方程的通解为：
S
n
ABnCn
2
Dn
3
，代入初始条件得：

S
0
A0
，
S
1
ABCD3
，
S
2
A 2B4C8D11
，

731
S
3
A3B9 C27D26
，解得：
A0,B,C,D
，

623
731n(n1)(2n7)
故

S
n
nn
2
n
3


6236

方法三（快速求系数）

n(n1)n(n1)( n2)
通解为：
S
n
A
0
A
1
n A
2
，
A
3
2!3!
初始条件：
S0
0,S
1
3,S
2
11,S
3
26
，代入得

A
0
0
，
A
0
A
1
3
，
A
0
2A
1
A
2
11
，
A
0
3A
1
3A
2A
3
26
，
解得：
A
0
0，
A
1
3
，
A
2
5
，
A
3
2

所以，
S
n
3n5

S
n


k(k1)(k2)
（参见课本第92页）
7．利用递推关系求下列和：
k0
n
n(n1)n(n1)(n2) n(n1)(2n7)

2
2!3!6
显然，
S
n
S
n1
n(n1)(n2)
，

同理对应的齐次 方程的特征根为
1
，特解为
S
n
A(1)
n
A
，

*
n(Bn
3
Cn
2
DnE )Bn
4
Cn
3
Dn
2
En
，

非齐次方程的特解为：
S
n

所以，非齐次方程的通解为：
S
n
Bn
4
Cn
3
Dn
2
EnA
，


初始条件为：
S
0
0 ,S
1
6,S
2
30,S
3
90,S
4210
，代入上式，可得

S
0< br>A0
，
S
1
BCDEA6
，
S2
16B8C4D2EA30
，

S
3
 81B27C9D3EA90
，
S
4
256B64C16D 4EA210

解得：
A0
，
B
1
4< br>3
2
11
133
，
C
，
D
，< br>E

4
422
n

n1

n 2

n3

11
2
3
nn

424
所以

S
n
n
4
n
3


方法二：


显然，
S
n
S
n 1
n(n1)(n2)
，类似可得，
S
n1
S
n2
n(n1)(n1)
，

两式相减得
S
n2S
n1
S
n2
3n(n1)
，

同理可得
S
n1
2S
n2
S
n3
3 n(n1)
，两式再相减得

S
n
3S
n1
3S
n2
S
n3
6n
，同理得
S
n1
3S
n2
3S
n3
S
n4
6(n 1)
，

两式再相减得
S
n
4S
n1
6S
n2
4S
n3
S
n4
6
，
同理可得
S
n1
4S
n2
6S
n 3
4S
n4
S
n5
6
，

两式再相减，可得关于
S
n
的齐次定解问题：


S
n
5S
n1
10S
n2
1 0S
n3
5S
n4
S
n5
0


S0,S6,S30,S90,S210
1234

0

其特征方程为：
x
5
5x
4
10x
3
10x
2
5x10
，
x1
是五重特征根，< br>
所以方程的通解为：
S
n
ABnCn
2< br>Dn
3
En
4
，代入初始条件得：

S
0
A0
，
S
1
ABCDE6
，
S
2
A2B4C8D16E30
，

S
3
A3B9C27D81E90
，
S
4
A4B16C6 4D256E210
，

解得：
A0,B,C
故

S
n
n
3
2
3
2
1131
, D,E
，

424
11
2
3
3
14
n

n1

n2

n3

nnn

4244

方法三（快速求系数）
< br>通解为：
S
n
A
0
A
1
nA
2
n(n1)n(n1)(n2)n(n1)(n2)(n3)
A
3< br>A
4
，
2!3!4!
初始条件：
S
00,S
1
6,S
2
30,S
3
90,S
4
210
，代入得

A
0
0< br>，
A
0
A
1
6
，
A
0
2A
1
A
2
30
，
A
0
3A1
3A
2
A
3
90
，
A
0< br>4A
1
6A
2
4A
3
A
4
210

解得：
A
0
0
，
A
1
6
，
A
2
18
，
A
3
18
，
A
4
6

S
n
6n18
n(n1)n(n1)(n2)n(n1)(n2)(n3)
186
2!3! 4!

n

n1

n2

n3


4
所以，

8. 求从1到500的整数中能被3和5整除但不能被7整除的
数的个数。（参见课本123）
解 ：设
A
i
为1到500的整数中能被i整除的数的集合，
i3,5,7，

500

500

500

166A100
A71
， 则
A
3


，，
5
7



3

5


7


500

500

500

33AA14
，
AA23

A
3
A
5


，，
57
37

3557
37



500

4
，
A
3
A
5
A
7



357

满足条件的 整数个数为：
A
3
A
5
A
7
，根据容斥原理有：

A
3
A
5
A
7
A
3< br>A
5
A
3
A
5
A
7
334 29

9．某人参加一种会议，会上有6位朋友，他和其中每一人在会上各
相遇12次 ，每二人各相遇6次，每三人各相遇4次，每四人各相遇
3次，每五人各相遇2次，与六人都相遇1次， 一人也没遇见的有5
次。问该人共参加几次会议？（参见课本123）
解：设S为该人参加的所有会议组成的集合，
设
A
i
表示该人与第 i个朋友相遇的所有会议构成的子集，
i1,2,L,6
，则

R
1
A
i
12
，
i1,2,L,6


R
2
A
i
A
j
6
，
R
3
A
i
A
j
A
k
4
，
R
4
A
i
A
j
A
k
Al
3
，
R
5
A
i
A
j
A
k
A
l
A
m
2
，

R
6
A
1
A
2
A
3
A
4
A
5
A
6
1
，
A
1
A
2< br>A
3
A
4
A
5
A
6
123 456
CRCRCRCRCRCR
6

61626364656
则，
612156204153621
28
则该人共参加会议次数为：
S28533
（次）。
10．n位的四进制数中 ，数字1，2，3各自至少出现一次的
数有多少个？
（参见课本123）

解：设S表示所有n位四进制数构成的集合，
A
i
为不出现i的数的集合，
i1,2,3
，
则
A
1
A
2
A
3
3
n
，< br>A
1
A
2
A
1
A
3
A
2
A
3
2
n
，
A
1
A
2
A
3
1
，
则由逐步淘汰原理，可得


11．一次考试采用百分制，所有考生的总分为10101，证明如果考生人数不少于
202，则必有 三人得分相同。(参见课本145)
A
1
g
A
2
g
A
3
S(A
1
A
2
A
3
)( A
1
A
2
A
1
A
3
A
2A
3
)A
1
A
2
A
3
43nn1
321
n

证明：采用百分制，则所有可能的分数为0~100
，共
101
个分数，现人数不少
于
202
， 则平均每个分数有两个人得分相同。分情况讨论：

（
1
）若有某些分数没有 考生得该分数，则
202
名考生，可能的考生成绩最
多
100
种，根 据抽屉原理，必有三个的得分相同。

（
2
）若有
1
个考生 的分数与其他人都不同，则其余
201
名考试可能的分数

只有
100
种，则必有三人的得分相同。


（
3
）若每个分数线都有两个人，则所有考生的总分为：

2(12L100)10100
，与题目矛盾。所以这种情况不可能存在。

综上所述，必有三人得分相同。证毕。


方法二：反证法。
< br>假设没有三个考生考试成绩相同，因为分数的分布为
0
～
100
分，共
101
种分

数，若考生人数大于
202
人，则根据抽 屉原理必然有三人考试成绩相同，矛盾；

若考生人数恰好
202
个，要求没 有三个考生考试成绩相同，则所有考生必然
恰好两两得分相同。

而此时所有考生的总 分为：
2(012L100)10100
，矛盾。

故结论成立。


12. 一张卡片分成
42
个方格，每 格用红蓝两色涂染，可有多
少种方法？（参见课本176）
参考修改意见：把红蓝色改成其他颜色
解：如图所示将卡片的八个格进行编号，则对应集合< br>S{1,2,L,8}
，用红蓝两色
涂染，卡片只能旋转，不能翻转，则可得
S
上的置换群
Q{p
1
,p
2
}
，
< br>其中，
p
1
(1)(2)(3)(4)(5)(6)(7)(8)
，
p
2
(18)(27)(36)(45)
，


现在用两种颜色进行涂染，则不同的涂染方案有：

1

L(2
8
2
4
)136
（种）

2

若卡片还能翻转，但同一个格子对应的正反面要求同色，
1
3
5
7
2
4
6
8
则除了上述两个置换外，还有沿着横、竖两个对称轴翻转的置换
p
3

17

28

35

46

，
p
4


12

34
< br>56

78


从而可知不同的染色方案有：
L
2

1
8
22
4
3

76
（种）


4

若同一个格子对应的正反面不要求同色，且卡片既能旋转，又能翻转，
则相应的置换为： < br>q
1


1

2

L

8

A

B

L

H

，
q
2
(18)(27)(36)(45)(AH)(BG)(CF) (DE)

q
3


1G

2H

3E

4F

5C

6D
 
7A

8B

，
q
4


1B

2A

3D

4C
5F

6E

7H

8G


其中
A,B,L,H
是卡片的背面分别依序与
1,2,L,8
对应的 格子。
那么，此时的染色方案有
L
3

1
168

223

16576
（种）

4

13．一根木棍等分成n段，用m种颜色涂染，问有多少种染
法？（参见课本176）
参考修改原则：
当
nm2
和
nm3
时各有多少种方法？

解：如图给木棍的每段依次编号为
1,2,L,n
，

则对应集合< br>S{1,2,L,n}
，用
m
中颜色进行涂
染，当
n
为偶数时，可得
S
上的置换群
Q
1
{p
1
,p
2
}
，其中

p
1
(1)(2)L(n)
，
p
2
(1n)(2n1)L(
1 2
……

n1

n

nn
（木棍只能翻转
180
o
）

1)
，
22
n
1
n
用
m
种颜色进行涂染，则不同的染色 方案有：
L
1
(mm
2
)
；

2当
n
为奇数时，可得
S
上的置换群
Q
2
{p
1
,p
3
}
，其中

p
3
(1 n)(2n1)L(
n1n1n1
2)()
，

222< br>n1
1
n
则不同的染色方案有：
L
2
(mm< br>2
)
。

2

n


1
综上所述，不同的染色方案有：
L(m
n
m

2

)
。

2
1
2
1
当
nm 3
时，不同的染色方案有：
L
2
(3
3
3
2< br>)18

2
当
nm2
时，不同的染色方案有：
L
1
(2
2
2
1
)3

14. 一个圆分成6个相同的扇形，分别涂以三色之一，可有
多少种涂法？（参见课本176）
解： 如图所示，用三个颜色对圆的六个扇形进行涂染，圆可以绕其圆心逆时针旋
转
0
o,60
o
,120
o
,180
o
,240
o< br>,300
o
，于是可以得到置换群
Q
所包含的置换如下：
< br>p
1
(1)(2)(3)(4)(5)(6)
，
p
2
(123456)
，

p
3
(135)(246)
，
p
4
(14)(25)(36)
，

p
5
(153)(264)
，
p
6
(654321)
，

6
5
4
3
1
2
根据
Polya
定 理，则不同的染色方案有：

1
L(3
6
23
1
23
2
3
3
)130
（种）

6


三 应用题
1．比5400小并具有每位的数字全不同的正整数有多少个？
（参见课本21页）
解：（
1
）比
5400
小且每位数字全不同的正整数；


按正整数的位数可分为以下几种情况：


①

一位数，可从
1
～
9
中任取一个，共有
9
个；

②

两位数。十位上的数可从
1
～
9
中选取，个位数上的数可从其余
9
个数字中选取，
根据乘法法则，共有
9981
个；


③

三位数。百位上的数可从
1
～
9
中选取，剩下的两位数可从其余
9
个数中选
2
个进
行排列，根据乘法法则，共有
9P
9
2
648< br>个；


④

四位数。又可分三种情况：


千位上的数从
1
～
4
中选取，剩下的三位数从剩下的< br>9
个数字中选
3
个进行
排列，根据乘法法则，共有
4P9
3
2016
个；


千位上的数取
5< br>，百位上的数从
1
～
3
中选取，剩下的两位数从剩下的
8个
数字中选
2
个进行排列，共有
3P
8
2
 168
个；


千位上的数取
5
，百位上的数取
0
，剩下的两位数从剩下的
8
个数字中选
2
个进行排列，共有
P
8
2
56
个；


根据加法法则，满足条 件的正整数共有：
9816482016168562978
个；
2．比5400小并具有每位数字不同且不出现数字2与7的正
整数有多少个？（参见课本21页）
按正整数的位数可分为以下几种情况：设
A{0,1,3,4,5,6,8,9}


①

一位数，可从
A{0}
中任取一个，共有
7
个；


②

两位数。十位上的数可从
A{0}
中选取，个 位数上的数可从
A
中其余
7
个数字中
选取，根据乘法法则，共有7749
个；


③

三位数。百位上的数可 从
A{0}
中选取，剩下的两位数可从
A
其余
7
个数中选
2

个进行排列，根据乘法法则，共有
7P
7
2294
个；


④

四位数。又可分三种情况：


千位上的数从
1
，
3
，
4
中选取，剩下的三位数从
A
中剩下的
7
个 数字中选
3
个进行排列，根据乘法法则，共有
3P
7
3
 630
个；


千位上的数取
5
，百位上的数从
0
，
1
，
3
中选取，剩下的两位数从
A
中剩下的
6
个数字中选
2
个进行排列，共有
3P
6
2
90
个；


根据加法法则，满足条件的正整数共有：
749294630901070
个；


3. 投掷两个骰子 ，点数之和为r
(2r12)
，其组合数是多少？
（参见课本51页）
解：用
x
i
表示骰子的点数为
i
，

（
1
）若两个骰子不同，则问题等价于
r
的特殊有序
2-
分拆


rr
1
r
2


1r6,i1,2
i

故相应的母函数为

G(x)(xx
2
x
3
x
4
x
5x
6
)
2
x2x3x4x5x6x5x4x3x 2xx
则点数之和为
r
的方案总数就是
x
r
的系数
(2r12)
。

（
2
）若两个骰子相同，则问题等价于r
的特殊无序
2-
分拆

23456789101112


rr
1
r
2



6r
1
r
2
1
而此问题又可转化为求
r
的最大分项 等于
2
，且项数不超过
6
的分拆数，

即求方程


1x
1
2x
2
r
的非负整数解的个数。


x
1
0,x
2
1,x
1
x
2
6
2
相应的母函数为

G(x)
1xx
2

L
x
5

x
2

1xx
2
x
3
x
4

x
2

34


1xx
2
 x
3

x
2



1xx
2

x
2



1x

< br>x
2



x
2


56
x
2
x
3
2x
4
2x
5
3x
6
3x
7
3x
8
2
9
3x
10
x
11
x
12
其中点数之和为
r
的方案数就是
x
r
的系数。

4．证明Fibona cci数列的性质，当
n1
时，（参见课本第92
页）
（1）
F
n
2
1
F
n
F
n2
(1)n

用数学归纳法：


n1
时，
F
2
2
F
1
F
3
1
2
1 21
，命题成立；


n2
时，
F
3
2
F
2
F
4
2
2
131，命题成立；


假设当
nk
时，命题成立，即F
k
2
1
F
k
F
k2


1

，


当
nk1
时，

k
F
k
2
 2
F
k1
F
k3
F
k2
(F
k
F
k1
)F
k1
(F
k1
F
k2
)
F
k
F
k2
F


由归纳原理知，命题成立。

2
k1
(1)(1)
kk1


所以，
nk1
时，命题也成立；


方法二：

F
n
2
1
F
n
F
n2
n1n1


11515







5


2

2



2
nnn2n2


1151511515


< br>g







 
5


2

2


5


2

2



1


15





5< br>

2


2n2

15

2


2



n1
< br>15

g


2



n1

15




2



2n2




2n2nn2nn 22n2


1151515151515







2


g


2





2


g


2





2



5


2



22


1n1
n
15
n
15



2

1

(1)

(1)


5


2

2


 
22


11515

n

(1)
n
(1)

2




2


52






5．证明Fibonacci数列的性质，当
n1
时，
n F
1
(n1)F
2
L2F
n1
F
n< br>F
n4
(n3)
（参见课本第92页）
证明：采用数学归纳法。


n1
时，
F
1
15

13

F
5

< br>13

，命题成立；


n2
时，2F
1
F
2
38

23

F
6


23

，命题成立；


假设
nk
时，命题成立，即
kF
1
(k1)F
2
L2F
k1
F
k
F
k4
(k 3)
，


当
nk1
时，

(k1)F
1
kF
2
(k1)F
3

L< br>2F
k
F
k1


kF
1
 (k1)F
2

L
2F
k1
F
k



F
1
F
2

L
Fk
F
k1



F
k4
(k 3)



F
k3
1

F
k5
(k4)

即
nk1
时，命题也成立，


根据归纳法，命题成立。


6．求从1到500的整数中能被3和5整除但 不能被7整除
的数的个数。（参见课本第123）
解：设
A
i
为1 到500的整数中能被i整除的数的集合，
i3,5,7
，

500
500

500

166A100
A 71
， 则
A
3


，，
5
7< br>


3

5


7

500

500

500

33AA14
，
AA23

A
3
A
5


，，
57
37


3557
37



500

4
，
A
3
A
5
A
7



357

满足条件的整数个数为：
A
3
A
5
A
7
，根据容斥原理有：

A3
A
5
A
7
A
3
A
5
A
3
A
5
A
7
33429

7．某学生准备恰好用11个星期时间做完数学复习题，每天
至少做一题，一个星期最 多做12题，试证必有连续几天内
该学生共做了21道题。（参见课本第145）
证明：11
个星期总共有
77
天，每天做的题数设为
a
i
(i 1,2,L,77)
，


则
a
i
 1
，
a
k1
a
k2
La
k7
12,k0,1,L,70
，


构造序列
s
i


a
j
，则
1s
1
s
2
Ls
77
132
，

j1
i

若存在某个
s
k
21
，则问题得证。


否则，所有的
s
i
21
，令集合
A{s
1,s
2
,L,s
77
,s
1
21,s
221,L,s
77
21}
，


则有< br>22s
1
21s
2
21Ls
77
21 153
，


集合
A
中共有
154< br>个数，每个数的取值在
1
～
153
之间，

s
i
s
j
，由抽屉原理知，必有两个数相等。又
ij
时，从而< br>s
i
21s
j
21
，

所以，相等的 两个数必为
s
k
s
i
21
，显然
ki
，

故

21s
k
s
i

ji1

a
k
j
。证毕。

8．证明任意给定 的52个整数中，总存在两个数它们的和或
差能被100整除。（参见课本第145）
证明： 设52个整数为
a
1
,a
2
,L,a
52
，
令
r
i
a
i
mod100(i1,2,L ,52)
，则
r
i
的可能取值为0，1，2，……，99。
现将
r
i
分为51类：{0},{1,99},{2,98},……，{49,51} ,{50}（看为51个抽屉），
则根据抽屉原理，至少有2个
r
i
属于同一类，
假设
r
i
,r
j
属于同一类，则或者
r
i
r
j
或 者
r
i
r
j
100
，
若
r
i
r
j
，则
a
i
a
j
能被100整除 ，
若
r
i
r
j
100
，则
a
i
a
j
能被100整除。
证毕。

9．正五角星的五个顶点各镶嵌一个宝石，若有m种颜色的
宝石可供选择，问可以有多少种方案？（参见 课本第176）
解：该问题即：用
m
种颜色给正五边形的五个
d
顶 点染色，有多少种方案。

1
4'
3'
如图所示的正五边形，可绕其 中心
O
旋转
0
o
,72
o
,144
o,216
o
,288
o
，以及过
11'
，
2 2'
，…，
55'
等
5
条轴翻转，从而得到置换群
Q< br>所含的
2
O
5'
3
1'
2'
5
置换 如下：

p
1
(1)(2)(3)(4)(5)
，
p2
(54321)
，

p
3
(14253)
，
p
4
(13524)
，

p
5
( 12345)
，
p
6
(1)(25)(34)
，

p
7
(2)(13)(45)
，
p
8
(3)(15) (24)
，

p
9
(4)(35)(12)
，
p
10
(5)(14)(23)
，

4
根据
Polya
定理，不同的染色方案有：

L
1
5
(m4m5m
3
)

10