组合数学期末重点
第一章：7 11 14 25 26
7. n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又
有多少种不同的方案？
[解].(1)若第1个位置是男，有nn(n-1)(n-1)332211=(n!)
2
种排法；
若第1个位置是女，也有(n!)种排法；
2
故n个男n个女排成一男女相间的队伍，有2(n!)种不同的排法。
2
因为若不记座位的差别，只记人与人之间的相对位置的变化，则每一种坐法可产生2n
2(n!)
2
个男女相间的排列，从而坐法为种，
n!(n1)!n[(n1)!]
2
2n
2(n!)11
2
若不记顺、逆时针则有坐法种。
n!(n1)!n[(n1)!]
2
22n22
(2)若第1个座位坐男，有n个可能，则第2个坐女为n个可能，……，根据乘法原理，
故有nn(n-1)(n-1)332211=(n!)种方案。同理，第1个座位坐女，也有(n!)种方案。
22
故有2(n!)种方案。
2
11.凸10边形的任意三条对角线不共点。试求这凸10边形的对角线交于多少个点？又把所
有的对角线分割成多少段？
[解].(参见柯召《组合数学》上册。P 例1.6.1)
34
(1)从一个顶点可引出7条线和第一条（从右到左）交的有17，和第二条交的有26条
故和一个顶点引出的7条线相交的点为：
17+26+35+44+53+62+71=84
故和从10点引出的对角线交的点有个
8410=840，但每个点重复了四次（因为每个点在两
条线上，而每条线有两个端点）。故凸10 边形（这样
840
的）对角线交于个点。
210
4
第11题图1
4
故也可为
C
10
210
10987
4321
第11题图2
(2)从上。一个点引出的7条线中第一条线上有7个点，故将该线段分成8段；第二条
线上有12个点，故将该线段分成13段，故从一个点出发的7条线上的段数为
8+13+16+17+16+13+8=91
故有10个点。故总的段数可为9110=910。但有重复，重复数为2（因为每条线有两个端
点）。故总的段数为。
910
455
2
14.从26个英文字母中取出6个字母组成一字,若其中有2或3个母音.问分别可构成多少个
字(不允许重复)?
[解].英语中有6个元音字母a,e.i,(y),o,u,其余20个是辅音。
(1)若取出6个字母组成一字,其中有2个元音,可构成
206
2019181765
6!654321
=52 326 000
42
432121
(2)若有三个元音,可构成
206
201918654
6!654321
=16 416 000；
33
321321
另一种解法认为有5个元音，其余21个是辅音
(1)若取出6个字母组成一字,其中有2个元音,可构成
215
2120191854
6!654321
=43 092 000
42
432121
(2)若有三个元音,可构成
215
21201954
6!654321
=9 576 000。
33
32121
25.5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种使用方案？
[解].先从m个学生中选取k个使用第1台机器，再从剩下的m-k个学生中选取k个使用第
2台机器，其余m-2k个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C(m,k)
m
C(m-k,k)3
(-2)
mk
。这里k=0,1,2,,q ()，于是，按加法原理，共有
q
2
C(m,k)C(mk,k)3
k0
q
(m2k)
种使用方案。
26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字
符串有多少？
(n,n+1)
[解].转化为格路问题（弱领先条件—参见P36例4
(n+1,n+1)
(n,n)
该例是强领先条件）。即从(0,0)到(n,n)，只能从对角
线上方走，但可以碰到对角线。它可看作是从(0,1)
到(n,n+1)的强领先条件（只能从对角线上方走，但
不可以碰到对角线）的格路问题。更进一步的，它
可看作是从(0,0)到(n,n+1)的强领先条件的格路问题
(0,1)
(0,0) (1,0)
第26题图1
(因为此种格路第一步必到(0,1)格点)。故这样的字符串有
n0(n1)1n1(n1)0
-
=C(2n,n)-C(2n,n-1)个。
nn1
第二章：2.42 2.43 2.44 4 5 6
2.42. 设{a}满足a a a = 0，{b}满足b 2b b = 0，c = a+ b，n =0, 1, 2, 3,
nnn1n2nnn1n2nn n
，
试证序列{c
n
}满足一个四阶线性常系数齐次递推关系。
[解]方法一：(特征系数法)
由于序列{a
nnn1n2
}满足递推关系：a a a = 0
故显然也满足递推关系：
(a a a) + A(a a a) + A(a a a) = 0
nn1n21n1n2n32n2n3n4
这里A
12
，A为任意常数
整理为：a
n1n121n212n32n4
+ (A 1)a+ (A A 1)a (A + A)a Aa = 0
由于序列{b
nnn1n2
}满足递推关系：b 2b b = 0
故显然也满足递推关系：
(b 2b b) + B(b 2b b) + B(b 2b b) = 0
nn1n21n1n2n32n2n3n4
这里B
11
，B为任意常数
整理为：b
n1n121n212n32n4
+ (B 2)b+ (B 2B 1)b (B + 2B)b Bb = 0
A1B2
11
令：
AA1B2B1
2121
AAB2B
1212
AB
22
解之得：，
A2B1
11
A1B1
22
将此解代入和，有：a
nn1n3n4
3a + 3a + a = 0
b 3b + 3b + b = 0
nn1n3n4
将+，并注意到c
nn n
= a+ b，我们有：
c 3c + 3c + c = 0
nn1n3n4
这就是序列{c
n
}所满足的四阶线性常系数齐次递推关系。
方法二：(特征根法)
序列{a
nnn1n2
}的递推关系：a a a = 0
特征方程：
2
1 = 0
特征根：，
15
12
= =
2
15
2
故其通解为：b
15
n
= A()+ B()
2
nn
15
2
序列{b
nnn1n2
}的递推关系：b 2b b = 0
特征方程：
2
2 1 = 0
特征根：
12
=， =
1212
故其通解为：b
n
= C()+ D()
1212
nn
于是有：c
nn n
= a+ b= A()+ B()+ C()+ D()
15
n nnn
15
1212
2
2
因此序列{c
n
}所满足的线性常系数齐次递推关系的特征多项式为：
( )( )[ ()][ ()] = 0
15
15
1212
2
2
整理为：(
22
1)( 2 1) = 0
再整理为：
43
3 + 3 + 1 = 0
因此，对应的四阶线性常系数齐次递推关系为：c
nn1n3n4
3c + 3c + c = 0 。
2.43.在习题2.42中，若c = ab，试讨论之。
nnn
[解](特征根法)
序列{a
nnn1n2
}的递推关系：a a a = 0
特征方程：
2
1 = 0
特征根：，
12
= =
15
15
2
2
15
nn
15
)+ B() = A(
故其通解为：b
2
2
n
序列{b
nnn1n2
}的递推关系：b 2b b = 0
特征方程：
2
2 1 = 0
特征根：
12
=， =
1212
故其通解为：b
n
= C()+ D()
1212
nn
于是有：c
nnn
= ab= [A()+ B()][C()+ D()]
15
n nnn
15
1212
2
2
= AC()() + AD()()
1515
nnnn
1212
22
+ BC()() + BD()()
1515
nnnn
1212
22
因此序列{c
n
}所满足的线性常系数齐次递推关系的特征多项式为：
[ ()][ ()]
1515
1212
22
[ ()][ ()] = 0
1515
1212
22
15
2222
15
)][ () ()] = 0 () (
1515
2
2
整理为：[
再整理为：
432
2 7 2 + 1 = 0
因此，对应的四阶线性常系数齐次递推关系为：c
nn1n2n3n4
2c 7c 2c + c = 0 。
2.44. 设{a}和{b}均满足递推关系x + bx+ bx = 0，试证：
nnn1n12n2
(a) {ab}满足一个三阶齐次线性常系数递推关系；
nn
(b) a, a, a, 满足一个二阶线性常系数齐次递推关系。
024
[证](a)(特征根法)
二阶齐次线性常系数递推关系x
n1n12n2
+ bx+ bx = 0的特征方程为：
x + bx + b = 0
2
12
设其特征根为
12
，
(1)如果 ，则有：a = A = C
1 2 nn
1212
nnnn
+ B ，b+ D
于是：c+ B)(C+ D)
nnn
= ab= (A
1212
nnnn
= AC( + (AD + BC)() + BD(
12
22
))
nnn
12
这说明{c
n
}满足一个三阶齐次线性常系数递推关系。
其特征方程为：(x )(x ) = 0
12
22
12
)(x
3
22232
整理为：x+ )x+ +)x (
323
( + + () = 0
121212
1212
12
由于+ = b
121122122
+ = b， = b，故 +
121
222
b
因此有：x b b= 0
32
()x + b()x
bbb
112
223
222
故此{c
n
}满足如下的三阶齐次线性常系数递推关系：
c ()c + b()c = 0 。
n2n122n2n3
bbb
112
223
b bc
(2)如果 = = ，是一个二重根，则有：a = (A + Bn) ，b = (C + Dn)
1 2 nn
nn
于是：c
nnn
= ab= (A + Bn) (C + Dn) = [AC + (AD + BC)n + BDn]( )
nnn
22
这说明{c
n
}满足一个三阶齐次线性常系数递推关系。
其特征方程为：(x
323
) = 0
整理为：x
32246
3 x + 3 x = 0
由于2 = b
12
， = b
2
因此有：xx = 0
32
3bx + 3
2
bb
22
23
故此{c
n
}满足如下的三阶齐次线性常系数递推关系：
c 3bc + 3 = 0 。
n2n1n2n3
bb
22
23
cc
(b) (特征根法)
二阶齐次线性常系数递推关系x
n1n12n2
+bx+bx= 0的特征方程为
x+ bx+b= 0
2
12
设其特征根为
12
，
(1)如果 ，则有：a = A
1 2 n
12
+B
nn
2n2n
)()(
于是 a+B
2n
= A
12
因此，这说明{a
2n
}满足一个二阶齐次线性常系数递推关系
其特征方程为 (x)(x) = 0
12
22
整理为： x(+)x+= 0
2
1212
2222
由于 += 2b
12 112 2 2
+= b，= b，故有
12
22
b
1
2
于是 x( 2b= 0
2
bb
12
2
)x+
22
故此序列{a
2n
}满足一个二阶齐次线性常系数递推关系为：
c ()c += 0 。
n2n1n2
bb
12
2bc
22
(2)如果 = = ，是一个二重根，则有：a = (A+Bn)
1 2 n
n
于是 a
2n
= (A+Bn)( )
2
n
因此，这说明{a
2n
}满足一个二阶齐次线性常系数递推关系
其特征方程为 (x
22
) = 0
整理为： x2
224
x+ = 0
由于 2 = b
12
， = b，
2
于是 x2b= 0
2
2
x+
b
2
2
故此序列{a
2n
}满足一个二阶齐次线性常系数递推关系为：
c 2bc += 0 。
n2n1n2
b
2
c
2
4. 求由 A, B, C, D 组成的允许重复的排列中 AB 至少出现一次的排列数目.
5. 求 n 位四进制数中2和3必须出现偶数次的数目.
6. 试求由 a, b, c 三个文字组成的 n 位符号串中不出现 aa 图象的符号串的数目.
第三章：3.22 3.23 3.24 3.65 3.66 3.67
3.22.求满足条件：x+x+x=20
123
7 x17 3 x9，0 x8，
123
的整数解的数目。
[解].方法一：利用容斥原理二
不定方程与如下的不定方程等价：
x+x+x=10
123
0 x6，0 x8，0 x10
123
11
x3
(这可通过作变换
22
x
来实现)。
33
x7
对应于不定方程的不受限的不定方程为：
x+x+x=10
123
x0，x0，x0
123
设：X={x|x=(x
123
,x,x)是不定方程的解};
A={ x|x=(x,x,x) 是不定方程的解且x
11231
6+1=7};
A={ x|x=(x,x,x) 是不定方程的解且x
21232
8+1=9};
A={ x|x=(x,x,x) 是不定方程的解且x
31233
10+1=11};
因此,根据定理3.6.4.可知，不定方程的解的数目：
p=|X|=====66
10131212
0
10102
1211
21
A
1
对应的不定方程是：
x+x+x=10
123
x7，x0，x0
123
11
x7
令：0, 0, 0)。利用我们得到：
22
x
(
123
33
x
123
++ =( x-7)+ x+ x=( x+x+x)-7=10-7=3
123123
所以不定方程的解与下列不定方程：
123
++ =3
0, 0, 0
123
的解一一对应。故根据定理3.6.4.可知，不定方程的解的数目为：
|A|=====10
33155
54
1
332
21
同理可得：
|A|===3
3(109)1
2
109
3
1
A
3
对应的不定方程是：
x+x+x=10
123
x0，x0，x11
123
由于解若满足条件x
123
0，x0，x11，则有
x+x+x0+0+11=11>10
123
故不定方程没有解，即
|A|=0
2
因此p
1123
=|A|+|A|+|A|=10+3+0=13
A
12
A对应的不定方程是：
x+x+x=10
123
x7，x9，x0
123
由于解若满足条件x
123
7，x9，x0，则有
x+x+x7+9+0=16>10
123
故不定方程没有解，即
|A|=0
12
A
同理可得：|AAA
1323
|=0，|A|=0
因此pAAA
2121323
=|A|+|A|+|A|=0+0+0=0
A
123
AA对应的不定方程是：
x7，x9，x11
123
x+x+x=10
123
由于解若满足条件x
123
7，x9，x11，则有
x+x+x7+9+11=27>10
123
故不定方程没有解，即
p=| A|=0
3123
AA
所以，不定方程、也即不定方程的解的数目为：
q=|+p=66-13+0-0=53 。
00123
AAA
123
|= p-p- p
方法二：利用母函数方法
不定方程对应的母函数是：
(1+x+x+x+x+x+x)(1+x+x+x+x+x+x+x+x)(1+x+x+x+x+x+x+x+x+x+x
234562345678234567891
0
)
=(1+2x+3x+4x+5x+6x+7x+7x+7x+6x+5x+4x+3x+2x+x)
234567891011121314
(1+x+x+x+x+x+x+x+x+x+x)
2345678910
不定方程的解的数目为上述母函数中x的系数：
10
11+21+31+41+51+61+71+71+71+61+51
=1+2+3+4+5+6+7+7+7+6+5
=53 。
3.23.求满足下列条件：
6 x15，5 x20，10 x25
123
x+x+x=40
123
的整数解的数目。
[解].(仿3.22题)方法一.利用容斥原理二，不定方程与如下的不定方程等价：
x+x+x=19
123
0 x9，0 x15，0 x15
1 2 3
11
x6
(这可通过作变换
22
x5
来实现)。
33
x10
对应于不定方程的不受限的不定方程为：
x+x+x=19
123
x0，x0，x0
123
设：X={x|x=(x
123
,x,x)是不定方程的解};
A={ x|x=(x,x,x) 是不定方程的解且x
11231
9+1=10};
A={ x|x=(x,x,x) 是不定方程的解且x
21232
15+1=16};
A={ x|x=(x,x,x) 是不定方程的解且x
31233
15+1=16};
因此,根据定理3.6.4.可知，不定方程的解的数目：
p==|X|====210
31912121
0
2120
19219
21
A
1
对应的不定方程是：
x+x+x=19
123
x10，x0，x0
123
11
x10
令：0, 0, 0)。利用我们得到：
22
x
(
123
33
x
123
++ =( x-10)+ x+ x=( x+x+x)-10=19-10=9
123123
所以不定方程的解与下列不定方程：
123
++ =9
0, 0, 0
123
的解一一对应。故根据定理3.6.4.可知，不定方程的解的数目为：
|A|=====55
1
391
1111
1110
9
92
21
3(1916)1
55
54
====10 |A|=
32
21
1916
3(1916)1
55
54
====10因此p=|A|+|A|+|A|=55+10+10=75 |A|=
11233
1916
32
21
同理可得：
2
A
12
A对应的不定方程是：
x10，x16，x0
123
x+x+x=19
123
由于解若满足条件x
123
10，x16，x0，则有
x+x+x10+16+0=26>19
123
故不定方程没有解，即
|A|=0
12
A
同理可得：|AAA
1323
|=0，|A|=0
因此pAAA
2121323
=|A|+|A|+|A|=0+0+0=0
A
123
AA对应的不定方程是：
x10，x16，x16
123
x+x+x=19
123
由于解若满足条件x
123
10，x16，x16，则有
x+x+x10+16+16=42>19
123
故不定方程没有解，即
p=| A|=0
3123
AA
所以，不定方程、也即不定方程的解的数目为：
q=|+p=210-75+0-0=135 。
00123
AAA
123
|= p-p- p
方法二：利用母函数方法
不定方程对应的母函数是：
(1+x+x+x+x+x+x+x+x+x) (1+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x)
23456789234567891011121314152
(1x)(12xx)
101632
1x1x
1610
3
(1x)
1x1x
2
=(1-x+2x+x)
1016263242
-2x-x
234n2
2n
xxx
2222
(参见第三版习题2.16(P)或第二版第二章习题7(P))
199131
不定方程的解的数目为上述母函数中x的系数：
19
1
21
2
-1-2
115
22
=
2120111054
212121
--2
=210-55-20
=135 。
3.24.求满足下列条件的整数解的数目：
x+x+x+x=20
1234
1 x5，0 x7，4 x8，2 x6。
1234
[解].(仿题3.22)方法一：利用容斥原理二，不定方程与如下的不定方程等价：
x+x+x+x=13
1234
0 x4，0 x7，0 x4，0 x4
1234
11
x1
(这可通过作变换
22
x
x4
来实现)。
33
44
x2
对应于不定方程的不受限的不定方程为：
x+x+x+x=13
1234
x0，x0，x0，x0
1234
设：X={x|x=(x
1234
,x,x,x)是不定方程的解};
A={ x| x=(x,x,x,x)是不定方程的解且x
112341
4+1=5};
A={ x| x=(x,x,x,x)是不定方程的解且x
212342
7+1=8};
A={ x| x=(x,x,x,x)是不定方程的解且x
312343
4+1=5};
A={ x| x=(x,x,x,x)是不定方程的解且x
412344
4+1=5};
因此,根据定理3.6.4.可知，不定方程的解的数目：
p==|X|====560
41311616
0
161514
13133
321
A
1
对应的不定方程是：
x+x+x+x=13
1234
x5，x0，x0，x0
1234
11
x5
令：0, 0, 0, 0)。利用我们得到：
22
x
(
1234
33
x
44
x
1234
++ +=( x-5)+ x+ x+x=( x+x+x+x)-5=13-5=8
12341234
所以不定方程的解与下列不定方程：
1234
+++=8
1234
0, 0, 0, 0
的解一一对应。故根据定理3.6.4.可知，不定方程的解的数目为：
|A=|====165
481
1111
11109
1
8
83
321
同理可得：
|A|=====56
4(138)1
2
138
88
53
876
321
|A|=====165
4(135)1
135
1111
11109
3
83
321
|A|=====165
4(135)1
4
1111
11109
135
83
321
因此 p
11234
=|A|+|A|+|A|+|A|=165+56+165+165=551
A∩A对应的不定方程是：
12
x+x+x+x=13
1234
x5，x8，x0，x0
1234
x5
11
令：0, 0, 0, 0)。利用我们得到：
22
x8
(
1234
33
x
44
x
1234
+++=(x-5)+(x-8)+ x+x=( x+x+x+x)-(5+8)=13-13=0
12341234
所以不定方程的解与下列不定方程：
1234
+++=0
0, 0, 0, 0
1234
的解一一对应。故根据定理3.6.4.可知，不定方程的解的数目为：
|A∩A| ===1
401
12
0
3
0
同理可得：|A
(1355)14
13
∩A| ====20
1355
6
3
654
321
|A∩A| ====20
4(1355)1
14
6
654
1355
3
321
|A∩A| ===1
4(1385)1
3
23
1385
0
|A∩A| ===1
85)14(13
3
24
1385
0
|A=∩A| ===20因此
4(1355)1
34
1355
6
654
3
321
p=|A∩A|+|A∩A|+|A∩A|+|A∩A|+|A∩A|+|A∩A|
2
121314232434
=1+20+20+1+1+20=63A∩A∩A对应的不定方程是：
123
x+x+x+x=13
1234
x5，x8，x5，x0
1234
由于解若满足条件x
1234
5，x8，x5，x0，则有
x+x+x+x5+8+5+0=18>13
1234
故不定方程没有解，即 |A
123
∩A∩A| = 0
同理可得：|A
124134234
∩A∩A| = 0，|A∩A∩A| = 0，|A∩A∩A| = 0
p=|A∩A∩A|+|A∩A∩A|+|A∩A∩A|+|A∩A∩A| = 0+0+0+0 = 0
3
123124134234
A∩A∩A∩A对应的不定方程是：
1234
x+x+x+x=13
1234
x5，x8，x5，x5
1234
由于解若满足条件x
1234
5，x8，x5，x0，则有
x+x+x+x5+8+5+5=23>13
1234
故不定方程没有解，即
p=| A∩A∩A∩A|=0
4
1234
所以，不定方程、也即不定方程的解的数目为：
q=|+p+p=560－551+63－0+0=72。
001234
AAA
124
∩∩∩| = p－p－p
A
3
方法二.利用母函数方法,不定方程对应的母函数是：
(1+x+x+x+x+x+x+x)(1+x+x+x+x)
2345672343
1x1x
85
3
(1x)(13x3xx)
851015
1x1x
(1x)
4
2n
=(1-3x+3x+3x+x)
581013151823
-x-x-3x
xxx
3333
345n3
(参见第三版习题2.16(P)或第二版第二章习题7(P))
199131
不定方程的解的数目为上述母函数中x的系数：
13
1+3+3
=+3+31
16
11863
-3-1
3333
3
16151411109876654
-3-
321321321321
=560-495-56+60+3
=72 。
3.65.设X={0,1,2,3,4,5,6,7,8,9,10}，从X中任取7个元素，则其中必有两个元素之和等于10。
[证].X={0,1,2,3,4,5,6,7,8,9,10}中这11个元素：0,1,2,3,4,5,6,7,8,9,10，可分为6个子集：{0,10}，
{1,9},{2,8},{3,7},{4,6},{5}。因此，从X中任取7个元素，则其中必有两个元素落入同
一个子集中，但不可能是子集{5}，因为此子集中只有一个元素。而这两个元素落入其
余四个子集的任何一个之中, 其和显然都是10。
3.66.每边长为3的等边三角形内径取10个点，试证至少有一对点距离小于1。
[证].将边长为3的等边三角形按右图剖分成9个相同的边长为1的小等边三角形，因此在大
三角形内径取10个点，必至少有一对点落入某个小三角形中，因此，这一对点的距离
不会超过1。
另外，若这一对点的距离刚好是1，则
这一对点必是该小三角形的三个顶点中
的某两个。而小三角形的三个顶点中至
少有两个在大三角形的边界上，因此，
这一对点中必至少有一个是在大三角形
的边界上，而这与题设这10个点都在大
三角形内矛盾。
第3.66题 图
所以，这一对点的距离小于1。
3.67.任取7个不同的正整数，其中至少存在两个整数a和b使得a-b或a+b被10除尽。
[证].设7个正整数为a, a, a, a, a, a, a，被10除的余数分别是r, r, r, r, r, r, r。另外，
12345671234567
可能的余数共10个：0,1,2,3,4,5,6,7,8,9，可分为6类：{0},{1,9},{2,8},{3,7},{4,6},{5}。
因此r
1234567ijiji
, r, r, r, r, r, r中至少有两个属于同一类,例如r, r。于是或者r= r, 或者r+
r=10。这就是说, 或者a- a可被10除尽, 或者a+ a可被10除尽。
jijij
第四章：4.11 4.13 4.15 4.17 4.18
4.11. 有一个33的正方形棋盘，若用红、蓝色对这9个格进行染色，要求两个格着红色，
其余染蓝色，问有多少种着色方案？
[解]. 一个33的正方形棋盘，只能旋转，不能翻转，其详细的置换群为:
1
2
3
不动0： P
1
=(1)(2)(3)(4)(5)(6)(7)(8)(9)
逆时针旋转90: P
2
=(5)(1793)(2486)
4 5 6
7 8 9
第4.11题 图
顺时针旋转90: P
3
=(5)(1397)(26 84)
旋转180: P
4
=(5)(19)(28)(37)(46)
转动群 格式 置换 循环节
不动 0 (1) 1个 9个
中心 ±90 (1)(4) 2个 3个
中心 180 (1)(2) 1个 5个
9
12
14
第4.11题 表
将2个格着以r色，7个格着以b色，相当于用b，r二种颜色对33的正方形棋盘进
行染色。
于是根据母函数形式的Pólya定理，方案枚举：
P(b,r)=[(b+r)+2(b+r)(b+r)+(b+r)(b+r)]
1
9442224
4
其中b的系数即为所求染色方案数：
72
r
[20]
=
[
1
94
4
21
19!4!
]
42!7!1!3!
=[36+4]/4
=10(种) 。
4.13. 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转使之重
合作为相同处理。
[解]. 见第4.13题图使之重合的刚体运动群，它含有关于正六角形中心轴旋转±60，±120，
，
180的置换，绕过2个对角的轴翻转180
o
的置换，以及
绕过2个对凹的轴翻转180的置换：
o
1
y
z
不动0：(1)(2)(3)(4)(5)(6)
6
2
旋转 ±60：(1 2 3 4 5 6)，(6 5 4 3 2 1)
旋转 ±120：(1 3 5)(2 4 6)，(5 3 1)(6 4 2)
x
x
o
旋转180：(1 4)(2 5)(3 6)
翻转(角-角) 180：(1)(2 6)(3 5)(4)，(2)(1 3)(4 6)(5)，
(3)(1 5)(2 4)(6)
翻转(凹-凹) 180：(1 4)(2 3)(5 6)，(1 2)(3 6)(4 5)，
(1 6)(2 5)(3 4)。
转动群 格式 置换 循环节 所求方案数
不动 0 (1) 1个 6个 5
旋转 ±60 (6) 2个 1个 2·5
旋转 ±120 (3) 2个 2个 2·5
旋转 180 (2) 1个 3个 5
翻转(角-角) 180 (1)(2) 3个 4个 3·5
66
11
22
33
224
3
z
4
第4.13题 图
y
5
翻转(凹-凹) 180 (2) 3个 3个 3·5
33
第4.13题 表
于是根据Pólya定理，可得不同的染色方案数为：
l=
1
612343
[5252553535]
12
1
=
(1562510501251875375)
12
1
=
18060
12
=1505(种) 。
本文发布于:2023-05-21 21:43:52，感谢您对本站的认可！
本文链接：https://www.wtabcd.cn/zhishi/a/168467663347535.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文word下载地址：西安交通大学组合数学期末重点.doc
本文 PDF 下载地址：西安交通大学组合数学期末重点.pdf
| 留言与评论（共有 0 条评论） |
