第三章 容斥原理和鸽巢原理
§ 1 容斥原理引论例 [1,20]中 2或 3的倍数的个数
[解 ] 2的倍数是,2,4,6,8,10，
12,14,16,18,20。 10个
§ 3.1 容斥原理引论
3的倍数是,3,6,9,12,15，
18。 6个但答案不是 10+6=16 个，因为 6，
12,18在两类中重复计数，应减去。故答案是,16-3=13
§ 3.2 容斥原理容斥原理 研究有限集合的 交或并的计数 。
[DeMorgan定理 ] 论域 U,补集
A
{ | }A x x U x A且,有
§ 3.2 容斥原理
(a)
A B A B?
(b)
A B A B?
证,(a)的证明。
设,则相当于 和同时成立，亦即
BAx
BAx
BAx Ax?
Bx?
A A B x A B (1)
§ 3.2 容斥原理反之，若 x A B x A x B,即 和故,x A x B x A B和 亦即
xx BA AB (2)
由（ 1）和（ 2）得
x BA ABx
(b)的证明和（ a)类似，从略,
§ 3.2 容斥原理
DeMogan定理的推广：设
1,2,.,,,nA A A U是 的子集
2 1 2.,,,,,nnA A A A A?1则 ( a ) A 2 1 2.,,,,,nnA A A A A?1( b ) A
证明,只证 (a),N=2时定理已证。
设定理对 n是正确的，即假定：
§ 3.2 容斥原理
2 1 2.,,,,,nnA A A A A?1A
正确
21
12
12
11
1
1
..,(,.,)
(,.,
...
nnnn
n
n
n
n
A A A A A A
A A A A
A A A A
1
则
A
即定理对 n+1也是正确的。
§ 3.2 容斥原理
§ 2 容斥原理最简单的计数问题是求有限集合 A
和 B的并的元素数目。显然有即具有性质 A或 B的元素的个数等于具
A B A B A B
(1)
定理,
§ 3.2 容斥原理有性质 A和 B的元素个数。
U
BA AB
§ 3.2 容斥原理
§ 3.2 容斥原理证 若 A∩B=φ,则 | A∪ B |= |A| + |B|
| A |＝ | A ∩( B∪ B) |
＝ | (A∩B)∪ (A∩B)|
＝ | A∩B | + | A∩B | ( 1 )
同理 | B | ＝ | B∩A | + | B∩A | ( 2 )
| A∪ B |＝ |(A∩( B∪ B))∪ (B∩(A∪ A))|
＝ |(A∩B)∪ (A∩B)∪ (B∩A)∪ (B∩A)|
＝ | A∩B| + |A∩B | + | B∩A| ( 3 )
§ 3.2 容斥原理
( 3 ) － ( 1 ) － ( 2 ) 得
| A∪ B |－ | A |－ | B |
＝ | A∩B| + |A∩B | + | B∩A|
－ ( | A∩B | + | A∩B | )
－ ( | B∩A | + | B∩A | )
＝－ | A∩B |
∴ | A∪ B |＝ | A | + | B |－ | A∩B |
定理：
(2)A B C A B C A B
B C A B C
A C-
：
()
()
A B C A B C
A B C A B C
证明
§ 3.2 容斥原理
( ) ( ) ( )
( ) ( )
A B C A C B C
A B C A B C A B
A C B C
A B C A B B C
A B C
根据
C- A
§ 3.2 容斥原理
A B
C
AC BC
AB
A B C
§ 3.2 容斥原理例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有 170,130,120人；同时修数学、物理两门课的学生 45人；同时修数学、化学的 20人；同时修物理化学的 22人。同时修三门的 3人。问这学校共有多少学生？
§ 3.2 容斥原理令,M为修数学的学生集合；
P 为修物理的学生集合；
C 为修化学的学生集合；
1 7 0,1 3 0,1 2 0,4 5
2 0,2 2,3
P C M P
M C P C M P C
M
§ 3.2 容斥原理
1 7 0 1 3 0 1 2 0 4 5 2 0 2 2 3
336
M P C P C M P M
M C P C M P C
M
即学校学生数为 336人。
§ 3.2 容斥原理同理可推出：
A B C D A B C D A B
B C A D A B C
A B D B C D A B C D
A C
利用数学归纳法可得一般的定理：
§ 3.2 容斥原理定理 设 ￠ (n,k)是［ 1,n］ 的所有 k-
子集的集合,则
|∪ Ai | = ∑ (－ 1)k-1 ∑ | ∩ Ai |
证 对 n用归纳法。 n=2时，等式成立。
假设对 n - 1,等式成立。对于 n有
§ 3.2 容斥原理
n
i=1 k=1
n
I∈ ￠ (n,k) i∈ I
§ 3.2 容斥原理
1
i
11
11
11
1
11
11
11
11
A
()
( 1 ) ( 1 ) ( )
nn
in
ii
nn
i n i n
ii
nn
i n i n
ii
nn
kk
i n i n
kk iI
AA
A A A A
A A A A
A A A A
I∈ ￠ (n-1,k) I∈ ￠ (n-1,k)i∈ I
§ 3.2 容斥原理
11
1
12
1
2
1
1
( 1 )
( 1 )
( 1 )
nn
k
i i n
ik iI
n
k
in
k iI
n
k
i
k iI
A A A
AA
A
I∈ ￠ (n,k)
I∈ ￠ (n-1,k-1)
I∈ ￠ (n-1,k)
此定理也可表示为：
定理,设
1,2,..,,nA A A
是有限集合，则
12
11
1
1
2
...
...
( 1 ),..
n
nn
i i j
i i j i
k
n
j
n
A A A
A A A
AA
A A A
n
i
i=1 j>i k>j
+ A
(4)
§ 3.2 容斥原理证,用数学归纳法证明。
已知 n=2时有
1 2 1 2 1 2A A A A A A
设 n-1时成立，即有：
§ 3.2 容斥原理§ 容斥原理
1 2 1
11
11
1 2 1
...
...
( 1 ),..
n
nn
i i j
i i j i
jk
n
n
A A A
A A A
AA
A A A
n-1
i
i=1 j>i k>j
A+
§ 3.2 容斥原理
1 2 1
1 2 1
1 2 1
1 2 1
...
(,.,)
...
(,.,)
nn
nn
nn
nn
A A A A
A A A A
A A A A
A A A A
§ 3.2 容斥原理
1 2 1
12
..,)
( ) ( ),.,
),
nn
nn
n
A A A A
A A A A
A
n-1
但 (
(A
§ 3.2 容斥原理
1 2 1
1 2 1
1 2 1
1 2 1 3
(,,,)
( ) ( ),,,( )
...
...
nn
n n n n
n n n n
nn
A A A A
A A A A A A
A A A A A A
A A A A A A
§ 3.2 容斥原理
2 1 1 2
11
11
12
.,,( 1 ),,,
...
( 1 ),,,
n
n n n n
nn
i n i j n
i i j i
n
n
A A A A A A
A A A A A
A A A
§ 3.2 容斥原理
1 2 1
11
1
1
2
...
...
( 1 ),..
nn
nn
i i j
i i i
n
n
j
jk
A A A A
A A A
AA
A A A
n
i
i=1 j>i k>j
A+
§ 3.2 容斥原理
,NA又 A
其中 N是集合 U的元素个数，即不属于
A的元素个数等于集合的全体减去属于
A的元素的个数。一般有：
§ 3.2 容斥原理
1 2 1 2 1
11
12
...,..
...
( 1 ),..
n n n
nn
i i j
i i j
jk
n
i
n
A A A N A A A A
N A A A
AA
A A A
n
i
i= 1 j> i k> j
A-
(5)
容斥原理指的就是（ 4）和（ 5）式。
§ 3.2 容斥原理
§ 3 例例 1 求 a,b,c,d,e,f六个字母的全排列中不允许出现 ace和 df图象的排列数。
解,设 A为 ace作为一个元素出现的排列集,B为 df作为一个元素出现的排列集,为同时出现 ace,df的排列数。
AB
§ 3.3 例
4 !,5 !,3 !,A B A B
根据容斥原理，不出现 ace和 df的排列数为：
AB
=6!- (5!+4!)+3!=582
§ 3.3 例例 2 求从 1到 500的整数中能被 3或 5
除尽的数的个数。
解,令 A为从 1到 500的整数中被 3除尽的数的集合,B为被 5除尽的数的集合
50 0 50 0
16 6,10 0 ;
35
500
33
15
AB
AB
§ 3.3 例被 3或 5除尽的数的个数为
1 6 6 1 0 0 3 3 2 3 3
A B A B A B
例 3 求由 a,b,c,d四个字母构成的位符号串中,a,b,c,d至少出现一次的符号串数目。
§ 3.3 例解,令 A,B,C分别为 n位符号串中不出现 a,b,c符号的集合。
由于 n位符号串中每一位都可取 a，
b,c,d四种符号中的一个，故不允许出现 a的 n位符号串的个数应是 3 n，即
3
2
n
n
BC
A B A C C B
A
§ 3.3 例
1A B C?
a,b,c至少出现一次的 n位符号串集合即为 A B C
4 ( ) (
33 24 3
)
1
n
nn n
A B C A B
A C C B A B C
A B C
§ 3.3 例例 4。 求不超过 120的素数个数。
因,故不超过 120的合数必然是 2,3,5,7的倍数，而且不超过
120的合数的因子不可能都超过 11。
设 为不超过 120的数 的倍数集，
=2,3,5,7。
211 121?
i A
i
i
§ 3.3 例
23
57
2 3 2 5
2 7 3 5
12 0 12 0
60 40
23
12 0 12 0
24 17,
57
12 0 12 0
20 12,
2 3 10
12 0 12 0
88
14 15
AA
AA
A A A A
A A A A
，，
，
，
，，
§ 3.3 例
3 7 5 7
2 3 5
2 3 7
2 5 7
12 0 12 0
53
21 35
120
4
2 3 5
120
2
2 3 7
120
1
257
A A A A
A A A
A A A
A A A
，，
，
，
，
§ 3.3 例
2 3 5 7 2 3 5
7 2 3 2 5 2 7
3 5 3 7 5 7
2 3 5 2 3 7
2 5 7 3 5 7
2 3 5 7
120A A A A A A A
A A A A A A A
A A A A A A
A A A A A A
A A A A A A
A A A A
§ 3.3 例
12 0 ( 60 40 24 17 ) ( 20 12 8
8 5 3 ) ( 4 2 1 1 )
27.
§ 3.3 例注意,27并非就是不超过 120的素数个数，因为这里排除了 2,3,5,7着四个数，又包含了 1这个非素数。 2，
3,5,7本身是素数。故所求的不超过
120的素数个数为：
27+4-1=30
§ 3.3 例例 5。 用 26个英文字母作不允许重复的全排列，要求排除 dog,god,gum，
depth,thing字样的出现，求满足这些条件的排列数。
解,所有排列中，令：
§ 3.3 例
1
2
3
4
5
A do g
A go d
A gu m
A de pth
A thing
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
§ 3.3 例出现 dog字样的排列，相当于把 dog作为一个单元参加排列，故 2 4 !?
1A
类似有：
2 3 4 52 4 !,2 2 !A A A A
由于 god,dog不可能在一个排列中同时出现，故：
12 0;AA?
类似：
2 3 1 40,0A A A A
§ 3.3 例由于 gum,dog可以在 dogum字样中同时出现，故有：
13 2 2 !AA?类似有 god和 depth可以在 godepth字样中同时出现，故
24 2 0 !AA?
god和 thing可以在 thingod字样中同时出现，从而
25 2 0 !AA?
§ 3.3 例
1 5 4 5
3 4 3 5
1 2 3 1 2 4
1 2 5 1 3 4
1 3 5 1 4 5
0,19 !,
20 !,
0,0
0,0
0,0
A A A A
A A A A
A A A A A A
A A A A A A
A A A A A A
§ 3.3 例
2 3 4 2 3 50,0A A A A A A
由于 god,depth,thing不可以同时出现，故有：
2 4 5 0AAA?
345 1 7 !A A A?
其余多于 3个集合的交集都为空集。
§ 3.3 例故满足要求的排列数为：
2 6 ! 3 2 4 ! 2 2 2 ! 2 2 ! 4 2 0 ! 1 9 ! 1 7 !
2 6 ! 3 2 4 ! 2 2 ! 4 2 0 ! 1 9 ! 1 7 !
§ 3.3 例例 6。 求完全由 n个布尔变量确定的布而函数的个数。
解,设
12(,,.,,,)nif x x x x中 不出现的布尔函数类为：,1,2,...,.in?
iA
由于 n个布尔变量 的不同的真值表数目与 位 2进制数数目相同，故为 个。根据容斥原理，
满足条件的函数数目为：
12,,...,nx x x
2n
22 n
§ 3.3 例
1
2
22
12
22
..,2 (,1 ) 2
(,2 ) 2,.,( 1 ) (,) 2
..,( 1 ) (,) 2
nn
n n k
n
k
n
A A A C n
C n C n k
C n n
2
22
2
2,
2 ( 2,1 ) 2 ( 2,2) 2
16 8 2 10
n
A C C
1
时得
A
§ 3.3 例
§ 3.3 例这 10个布尔函数为：
x1∧ x2,x1∧ x2,x1∧ x2,x1∧ x2，
x1∨ x2,x1∨ x2,x1∨ x2,x1∨ x2，
(x1∨ x2)∧ (x1∨ x2),(x1∨ x2)∧ (x1∨ x2)
例 7。 欧拉函数?(n)是求小于 n且与 n
互素的数的个数。
解,若 n分解为素数的乘积
12
12,..
ka a a
kn p p p?
设 1到 n的 n个数中为 倍数的集合为
i p
,1,2,.,,,.ik?iA
则有
§ 3.3 例
12
12
...
,1,2,...,.
，,1,2,...,.
k
a a a
ki
i
ij
ij
n p p p p
n
A i k
p
n
A A i j k i j
pp
,,,,,
§ 3.3 例
12
1 2 1 2
1 3 1 1 2
12
...
(,.,) (
..,)
1 1 1
( 1 ) ( 1 ) ( 1 )
k
k
nk
k
A A A
n n n n
n
p p p p p
n n n
p p p p p p p
n
p p p
(n)=
§ 3.3 例
2
6 0 2 3 5,
1 1 1
( 6 0 ) 6 0 ( 1 ) ( 1 ) ( 1 ) 1 6
2 3 5
n
例如 则即比 60小且与 60无公因子的数有 16个：
7,11,13,17。 19。 23,29,31，
37,41,43,47,49,53,59，此外尚有一个 1。
§ 3.3 例
§ 4 错排问题
n个元素依次给以标号 1,2,…,n。
N个元素的全排列中，求每个元素 都不在自己原来位置 上的排列数。
设 为数 在第 位上的全体排列，
=1,2,…,n。 因数字 不能动，
因而有：
iA i i
i i
§ 3.3 例
( 1 ) !,1,2,.,,,iA n i n
( 2) !,1,2,...,,
ij
A A n i n i j
同理
§ 3.4 错排问题每个元素都不在原来位置的排列数为
12
11
.,,! (,1 ) ( 1 )
1
! ( 1
!
(,2 ) ( 2 )
)
1 ! 2 ! !
! (,) 1 !
n
A A A n C n n
C n n
n
n
C n n
§ 3.4 错排问题例 1。 数 1,2,…,9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。
解,实际上是 1,3,5,7,9五个数的错排问题，总数为：
5 ! ( 5,1 ) 4 ! ( 5,2 ) 3 ! ( 5,3 ) 2 ! ( 5,4 ) 1 !
1 1 1 1
( 5,5 ) 1 2 0 ( ) 4 4
2 6 2 4 1 2 0
C C C C
C
§ 3.4 错排问题例 2,在 8个字母 A,B,C,D,E,F,G,H的全排列中,求使 A,C,E,G四个字母不在原来上的错排数目。
8个字母的全排列中，令分别表 A,C,E,G在原来位置上的排列，
则错排数为：
1 2 3 4,,,A A A A
§ 3.4 错排问题
1 2 3 4
8 ! ( 4,1 ) 7 ! ( 4,2 ) 6 !
( 4,3 ) 5 ! ( 4,4 ) 4 !
24024
A A A A C C
CC
§ 3.4 错排问题例 3。 求 8个字母 A,B,C,D,E,F,G,H的全排列中只有 4个不在原来位置的排列数。
解,8个字母中只有 4个不在原来位置上，其余 4个字母保持不动，相当于 4个元素的错排，其数目为
§ 3.4 错排问题
1 1 1 1
! ( 1 )
1 ! 2 ! 3! 4 !
1 1 1
24( 1 1 ) 9
2 6 2
4
4
故 8个字母的全排列中有 4个不在原来位置上的排列数应为,C(8,4)·9=630
§ 3.4 错排问题
§ 5 棋盘多项式和有限制排列
1,有限制排列
§ 3.5 棋盘多项式和有限制排列例 4个 x,3个 y,2个 z的全排列中，
求不出现 xxxx,yyy,zz图象的排列。
解 设出现 xxxx的排列的集合记为 A1，
|A1|= =60;
设出现 yyy的排列的集合记为 A2，
| A2|= =105；
6!
1!·3!·2!
4!2!
7!
§ 3.5 棋盘多项式和有限制排列设出现 zz的排列的集合记为 A3，
| A3|= =280；
|A1∩A2|= =12； |A1∩A3|= =20；
|A2∩A3|= =30； |A1∩A2∩A3|=3!=6；
全排列的个数为,=1260；
所以：
|A1∩A2∩A3|=1260－ (60+105+280)
+(12+20+30)－ 6
=871
4!·3!
8!
4!2! 5!
3!6!
4! 9!
2!·3!·4!
§ 3.5 棋盘多项式和有限制排列
2．棋子多项式
n个不同元素的一个全排列可看做 n个相同的棋子在 n× n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子
x
x
x
x
x
如图所示的布局对应于排列 41352。
§ 3.5 棋盘多项式和有限制排列可以把棋盘的形状推广到任意形状：
布子规定称为无对攻规则，棋子相当于象棋中的车。
令 r k（ C） 表示 k个棋子布到棋盘 C上的方案数。如：
§ 3.5 棋盘多项式和有限制排列
r1( )=1,r1( )=2,r1( )=2，
r2( )=0,r2( )=1。
为了形象化起见，（ ）中的图象便是棋盘的形状。
§ 3.5 棋盘多项式和有限制排列定义 设 C为一棋盘，称 R(C)= ∑ rk(C) xk
为 C的棋盘多项式。
规定 r0(C)=1,包括 C=Ф时。
设 Ci是棋盘 C的某一指定格子所在的行与列都去掉后所得的棋盘； Ce是仅去掉该格子后的棋盘。
在上面定义下，显然有
rk(C)=rk－ 1(Ci)＋ rk(Ce)，
k=0
∞
§ 3.5 棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk－ 1(Ci)；
要么不布子，方案数为 rk(Ce)。
设 C有 n个格子，则 r1(C)＝ n．
r1(C)＝ r0(Ci) + r1(Ce),∵ r1(Ce)＝ n－ 1
∴ r0(Ci)＝ 1,故规定 r0(C)＝ 1是合理的．
§ 3.5 棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk－ 1(Ci)；
要么不布子，方案数为 rk(Ce)。
从而
R(C)= ∑ rk(C) xk
＝１＋ ∑[rk－ 1(Ci)+ rk(Ce)]xk
= x ∑ rk(Ci)xk + ∑ rk(Ce)xk
＝ xR(Ci) + R(C e) (3)
∞
k=0
∞
∞∞
k=0
k=0k=0
§ 3.5 棋盘多项式和有限制排列例如：
R( )=1+ x；
R( )= xR( )+ R( )= x+ (1+ x)=1+2x；
R( )= x R( ) + R( )
= x(1 + x )+1 + x
=1+ 2x +x2
§ 3.5 棋盘多项式和有限制排列如果 C由相互分离的 C1,C2组成，即 C1
的任一格子所在的行和列中都没有 C2的格子。则有：
rk(C) = ∑ ri(C1) rk－ i(C2)
i=0
k
故 R(C) = ∑ (∑ ri(C1) rk－ i(C2) ) xk
= (∑ ri(C1) xi) (∑ rj(C2) xj )
j=0
nn
kn
i=0
i=0
k=0
∴ R(C) = R(C1) R(C2) (4)
§ 3.5 棋盘多项式和有限制排列利用（３）和（４），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，
从而得到其棋盘多项式。
例 R ( ) = xR( )+R( )
= x(1+ x)2 +(1+2x)2
=1+ 5x +6x2 + x3
*
R( ) = xR( ) + R( )
= 1+6x +10 x2 +4x3
§ 3.5 棋盘多项式和有限制排列
３．有禁区的排列例 设对于排列 P=P1 P2 P3 P4,规定 P1≠３，
P２ ≠１、４,P３ ≠2、４,P4≠2。
1 2 3 4
P1
P2
P3
P4
1 2 4 3
1
4 3
2
2
3
4 3
1 2
1
4
这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。
§ 3.5 棋盘多项式和有限制排列定理 设 ri 为 I个棋子布入禁区的方案数，
i =1,2,3,··,n。 有禁区的布子方案数（即禁区内不布子的方案数）为
r0 n! － r1(n－ 1)! ＋ r2(n－ 2)!－ ···＋ (－ 1)nrn
＝ ∑(－ 1)k rk ( n－ k)!
k=0
n
证 设 Ai 为第 i个棋子布入禁区，其他棋子任意布的方案集,i =1,2,3,…,n 。
§ 3.5 棋盘多项式和有限制排列则所有棋子都不布入禁区的方案数为
｜ A1∩A2∩···∩An｜
＝ n！＋ ∑(－ 1)k ∑ ｜ ∩Ai｜
I∈ ￠ (n,k)
n
i∈ Ik=0
而 ∑ ｜ ∩Ai｜ 正是 k个棋子布入禁区，其他 n - k个棋子任意布的方案数 。由假设可知等于 rk(n－ k)！ (注意：布入禁区的棋子也要遵守无对攻规则）,所以
｜ A1∩A2∩···∩An｜ =n!+ ∑(－ 1)k rk ( n－ k)!
I∈ ￠ (n,k) i∈ I
k=0
n
§ 3.5 棋盘多项式和有限制排列上例方案数为
4!－ 6(4－ 1)!＋ 11(4－ 2)!－ 7(4－ 3)!
＋ 1(4－４ )!＝ 4
例 １，２，３，４四位工人,A,B，
C,D四项任务。条件如下：
１ 不干 B；２ 不干 B,C；
３ 不干 C,D；４ 不干 D。
问有多少种可行方案？
§ 3.5 棋盘多项式和有限制排列解 由题意，可得如下棋盘：
其中有影线的格子表示禁区。
A B C D
1
2
3
4
R( )=1+6x+10x2+4x3
方案数 =4!－ 6(4－ 1)!+10(4－ 2)!－ 4(4－ 3)!
+0(4－ 4)!=4
§ 3.5 棋盘多项式和有限制排列例 三论错排问题错排问题对应的是 n× n的棋盘的主对角线上的格子是禁区的布子问题。
C = ···
R( C ) = ( 1 + x )n = ∑ ( ) xk 令 rk = ( )nk=0
nk
n
k
故 R(C)中的 xn,n! + ∑(－ 1)k ( ) (n－ k)!
= n!∑ (－ 1)k － =Pnk=1
n
n
k=0 k!
1k
n
§ 3.6 一般公式
§ 3.6 一般公式若将§３,2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少
”“只修两门课的学生有多少？”则相应的答案表示如下：
｜ M∩P∩C｜；
｜ M∩P∩C｜ +｜ M∩P∩C｜ +｜ M∩P∩C｜
｜ M∩P∩C｜ +｜ M∩P∩C｜ +｜ M∩P∩C｜
§ 3.6 一般公式设有与性质１,2,··,n相关的元素 N个，
Ai为有第 i 种性质的元素的集合,i=1,2,…,n
Pk为至少有 k种性质的元素的元次；
qk为恰有 k种性质的元素的个数。
P0 = N,P1 = | A1 | + | A2 | + ··+ | An |，
P2 = | A1∩A2 |+ | A1∩A3 |+ ··+ | An - 1∩An |
Pk = ∑ | ∩Aij |
qk = ∑ | (∩ Ai)∩ ( ∩ Aj)|
I∈ ￠ (n,k) i ∈ I
I∈ ￠ (n,k) i ∈ I j ∈ I
§ 3.6 一般公式定理 qk = ∑ (－ 1)i( )Pk+ik+iii=0n-k
证１ 设某一元素恰有 k种性质，则其对 Pk
的某一项的贡献为１，而对 Pk+1,Pk+2,··,
Pn的贡献都是０。若某一元的性质少于 k种则其对 Pk,Pk+1,···,Pn的贡献都是０。若恰有 k + j种性质，则其对 Pk的贡献是 ( ),
对 Pk+i的贡献是（ ）
k + j
k k + j
k + i
§ 3.6 一般公式而 ∑ (－ 1)i ( ) ( )
= ∑ (－ 1)i ( ) ( )
= ∑ (－ 1)i ( ) ( ) = ( ) ∑ (－ 1)i ( )
= ( ) · 0 = 0
即某恰有 k + j种性质的元素对上式右边的总的贡献为０。
k + j
k + i
k + i
ii = 0
j
i = 0
j k + j
k + i
k + i
k
i = 0
j k + j
i
j
k
k + j
k
j
i
k + j
k
§ 3.6 一般公式前例中只修一门课的学生为：
| M∩P∩C | + | M∩P∩C | + | M∩P∩C |
= q1= ∑ (－ 1)j - 1 ( ) Pj
= P1 － 2P2 + 3P3
j
1j =1
3
在一般公式中，若令
P0 = N,q0 = | A1∩A2∩···∩An |，
就得到原来的容斥原理。
§ 3.6 一般公式证２ 根据定义
qk = ∑ | (∩ Ai)∩ ( ∩ Aj)|
qk由 Pk+j的代数和组成，符号 (－ 1)j,计算
Pk+j的重复度,k + j个集的交的绝对值的项的总个数为 ( ) ( ),共 ( )种。
每一项的重复度为
( ) ( ) ( ) = ( )
从而 Pk+j的重复度也是 ( )
I∈ ￠ (n,k) i ∈ I j ∈ I
n
k k + j
k + j
k + j
k + j
j
n－ k
n－ k
n
nn
k j k
k
§ 3.6 一般公式
∴ qk = ∑(－ 1)j ( )Pk+j
= ∑(－ 1)j － k ( ) Pj
k + j
k
k
j
j =0
n － k
k
n
证３ 对 N做归纳。
N = 1时，设此元有 m种性质,m ＜ n,
不妨设 A1 =A2= ·· =Am={ a1 }。 显然
Pj = ( ),若 j＞ m,则 Pj = 0；
由定义，得 qk=｛
j
m
1 k = m
0 k ≠m
§ 3.6 一般公式右端＝ ∑ (－ 1)i( )Pk+i
＝ ∑ (－ 1)i( ) ( )
＝ ∑ (－ 1)i( ) ( ) = {
k+i
ii=0
n－ k
k+i
k
m
k+ii=0
n－ k
m
k
m - k
i i=0
n－ k 1 k =m
0 k≠m
假设对于 N－ 1,等式成立。
对于 N,设新增元有 m种性质，对于 N个元的 P’j＝ Pj＋ ( ),q’k＝｛
j
m 1 k =m
0 k≠m
§ 3.6 一般公式右端＝ ∑ (－ 1)i ( )P’k+i
＝ ∑ (－ 1)i ( ) [Pk+ i + ( )]
＝ ∑ (－ 1)i ( )Pk+i +∑ (－ 1)i ( )( )
＝ qk + ｛
等式成立．
k + i
ki=0
n－ k
k + i
k k + i
m
k + i
ki=0
n－ k
k + i
ki=0
n－ k
k + i
m
n－ k
i = 0
1 k =m
0 k≠m
§ 3.6 一般公式例 某校有１２个教师，已知教数学的有
８位，教物理的有６位，教化学的５位；
数、理５位，数、化４位，理、化３位；
数理化３位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？
解 令教数学的教师属于 A1,教物理的属于 A2,教化学的属于 A3。 则 P0＝１２，
P1＝ | A1 |+| A2|+| A3 |＝ 8+6+5＝１９ ;
P2＝ | A1∩A2|+ | A1∩A3|+| A2∩A3|＝ 12；
P3＝ | A1∩A2∩A3|＝ 3；
§ 3.6 一般公式故 教其他课的老师数为：
q0＝ P0 － P1 +P2－ P3＝２
恰好一门的教师数：
q1＝ P1－ 2P2 + 3P3＝ 4
恰好教两门的老师数为：
q2＝ P2－ 3P3＝ 3
§ 3.6 一般公式例 n 对夫妻围坐问题设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？
解 不妨设 n 个女人先围成一圈，方案数为 ( n－ 1 )! 。 对任一这样的给定方案，顺时针给每个女人以编号 1,2,··,n。 设第 i
号与第 i + 1号女人之间的位置为第 i 号位置,1≤ i ≤n－ 1。 第 n 号女人与第 1 号之
§ 3.6 一般公式间的位置为第 n 号位置。设第 i 号女人的丈夫的编号也为第 i 号,1≤ i ≤ n。 让 n 个男人坐到上述编号的 n 个位置上。设 ai是坐在第 i 号位置上的男人，则
ai ≠ i,i + 1，１ ≤ i ≤n－ 1； an≠n,1。
这样的限制也即要求在下面 3行 n列的排列中
１ ２ ３ ··· ··· n－１ n
２ ３ ４ ··· ··· n 1
a1 a2 a3 ·· ·· an－ 1 an
§ 3.6 一般公式每列中都无相同元素。满足这样的限制的排列 a1a2 ···an称为 二重错排 。
设二重错排的个数为 Un,原问题所求的方案数就是 Un ( n－ 1)！。
设 Ai为 ai = I 或 I + 1 (1≤ I ≤n－ 1 ),an = n
或 1的排列 a1 a2 ··· an的集合。 则
｜ Ai｜ = 2 (n－ 1)!,关键是计算 ∑ |∩Ai|
I ∈ ￠ ( n,k) i∈ I
§ 3.6 一般公式也就是从 ( 1,2 ) ( 2,3 ) ·· ( n－１,n ) ( n,1)
这 n对数的 k 对中各取一数，且互不相同的取法的计数。这相当于从 1,2,2,3,3,4,··,
n－ 1,n－ 1,n,n,1中取 k 个互不相邻数的组合的计数，但首尾的１不能同时取。回想无重复不相邻组合的计数：
C’( n,r ) = C ( n－ r + 1,r ),这里所求的是
( )－ ( )= ( )2n－ k+1 k 2n－ 4－ ( k－ 2)+1k－ 2 2n－ kk2n2n－ k
§ 3.6 一般公式
∴ Un =∑(－ 1)k ( )(n－ k)!
= ｜ ∩ Ai｜
2n
2n－ k
2n－ k
k
i ∈ [ 1,n ]
§３,11 反演基本想法,{an} 易算,{bn}难算,{an}可用
｛ bn｝ 表示，利用反演，将 {bn}用 {an}表示．
１．二项式反演
1
( 1 ) {
0,
n
mk
km
n k n
k m m n
，m引理
§３,11 反演证
0
( 1 )
( 1 )
1
{
0,
n
km
m
nm
i
n n m
m k m
n n m
mi
mn
mn
左边
，
§３,11 反演定理
00
( 1 ) ( 1 )
nn
kk
n k n k
kk
nn
a b b a
kk
0 0 0
00
00
00
( 1 ) ( 1 ) ( 1 )
( 1 ) ( 1 )
( 1 )
( 1 )
n n n
k k l
kl
k k l
nk
kl
l
kl
nk
kl
l
kl
nn
kl
ln
lk
n n k
ab
k k l
nk
b
kl
nk
b
kl
nk
bb
kl
证
§３,11 反演
00
( 1 )
nn
nk
n k n k
kk
nn
a b b a
kk
推论证 在定理中 bk处用 (－ 1)k bk代入，即可．
例 n! = ∑ ( ) Dn－ k,Dn=bn，
令 n－ k = l,则 n! = ∑ ( ) Dl
Dn = ∑ (－ 1)n-k ( )k!
= n! ∑ (－ 1)n-k
= n ∑
n
k n
kn
k 1
(n－ k)!
k=0
k=0
k=0
n
n
n (－ 1)k
k!
§３,11 反演
２,Mǒbíus反演定义 设 n ∈ Z+
1,若 n = 1;
μ( n ) = 0,若 n = p1α1 p2α2 ··· pkαk 存在 αi>1
(－ 1)k,若 n = p1p2···p k
如 μ( 30) = μ( 2·3·5 ) = (－ 1)3
μ( 12) = 0；
§３,11 反演定理 设 n ∈ Z+
则 ∑ μ( d ) =
1，若 n = 1；
0，若 n > 1；d | n
证 若 n =1,∑ μ( d ) = μ( 1 ) = 1,成立．
若 n>1,设 n = p1α1 p2α2 ··· pkαk,n’ = p1p2···p k
∑μ( d ) = ∑μ( d ) =∑ ∑ μ( ∏pi ) +μ(1)
=1 + ∑( ) (－ 1)j = (1－ 1)k = 0
d | n
d | n d | n’ j=1
k
i∈ II∈ ￠ (k,j)
k
jj=1
k
§３,11 反演推论?(n) = n ∑ μ(d )dd | n
证 n ∑ = n ∑
= n · { 1 + ∑ (－ 1)j ∑ ( ∏ pi )－ 1}
= n ∏ (1－ ) =?(n)
μ(d )
dd | n
μ(d )
dd | n’
1
pi
j =1
i =1
k
k
I ∈ ￠ (k,j ) i ∈ I
§３,11 反演定理 ( Mǒbíus反演定理 )设 f ( n )和 g ( n )
是定义在正整数集合上的两个函数．
f ( n ) = ∑ g (d ) = ∑ g ( ) (M1 )
g( n ) = ∑μ(d) f ( ) = ∑μ( )f (d) (M2) nd nd
d | n d | n
d | nd | n
则 ( M1 ) ( M2 )
n
d
§３,11 反演证,?”设 ( M1 )成立。
∑μ(d) f ( ) = ∑μ(d) ∑ g ( d1 )
= ∑ ∑μ(d) g ( d1 ) = ∑μ(d) g( d1 )
=∑ ∑ μ(d) g ( d1 ) = ∑ g(d1 ) ∑ μ(d)
= ∑μ(d) = = g( n )
d | n d | n
d | n dd1 | n
d1 | n nd
1
d | nd
1
d | d1 | n
n
dd1 |
n
dd1 |
n
d
n
d1d |
1,d1 = n
0,d1 < n
§３,11 反演
,?”：设（ M2） 成立。
∑ g (d ) = ∑ g (d )
= ∑ ∑μ( d ) f ( d1 ) =∑μ( d ) f ( d1 )
= ∑ f ( d1 ) ∑ μ( d )
= ∑μ( d ) = ∑μ( d ) =
= f ( n )
d | n
d | n
d | n
n
dd1 |
n
d1d |
n
d1d |
n
d1d | d1 | n
dd1 | n
1,d1 = n
0,d1 < n
§３,11 反演例 圆排列问题设 a1a2···a n 是一个 圆排列,即 a2a3···a na1,··,
ana1 ···a n－ 1,看作是相同的。为了加以区别，
必要时把原先的排列称为 线排列 。一个圆排列在 n 个位置短开形成的 n 个线排列在元素可重复的情况下，未必都不相同。
例如,d｜ n时，由不重复的 a1a2 ···a d重复 n ／ d次构成的圆排列
§３,11 反演
( a1a2 ···a d ) ·· ( a1a2 ···a d )
n d 组只能形成 d 个不同的线排列。
若一个圆排列可由一个长度为 k 的线排列重复若干次形成，则这样的 k 中最小者成为该圆排列的周期 。一个圆排列中元素的个数（
重复出现的按其重复次数计）称为它的 长度
§３,11 反演设集合｛ 1,2,··,m｝ 中元素形成的长度与周期都是 d 的圆排列的个数为 M(d)。
设 n 是一给定的正整数。
若 d ｜ n,每个长度与周期都是 d的圆排列可在 d 个位置上断开，重复 n / d 次形成 d个长度为 n 的可重排列。因此有
∑ d M( d ) = mn 由 Mǒbíus反演定理
n M(n) = ∑ μ( d ) m
故 M( n ) = ∑ μ( d ) m
d｜ n
d｜ n
d｜ n
n
d
n
d
§３,11 反演设长度为 n 的圆排列的个数为 T( n ),则
T( n ) ＝ ∑ M( d )
d｜ n
例 m = { 1,2 },n = 7 则
M ( 7 ) = ( 27－ 2 ) = 18
T ( 7 ) = ∑ M( d ) = M (1 ) + M ( 7) = 20
d｜ 7
1
7
§３,7 鸽巢原理之一鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即
“若有 n个 鸽子巢,n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”
例１ 367人中至少有２人的生日相同。
例２ 10双手套中任取 11只，其中至少有两只是完整配对的。
例３ 参加一会议的人中至少有２人认识的别的参加者的人数相等。
§３,7 鸽巢原理之一例４ 从 1到 2n的正整数中任取 n+1个，则这 n+1个数中，至少有一对数，其中一个是另一个的倍数。
证 设 n+1个数是 a1,a2,··,an+1。 每个数去掉一切 2的因子，直至剩下一个奇数为止。
组成序列 r1,r2,,··,rn+1。 这 n+1个数仍在［
1,2n]中，且都是奇数。而 [1,2n]中只有 n个奇数,故必有 ri = rj = r,则 ai = 2αi r,aj = 2αj r
若 αi＞ αj,则 ai 是 aj 的倍数。
§３,7 鸽巢原理之一例５ 设 a1,a2,··,am是正整数序列，则至少存在 k和 l,1≤k≤ l≤m,使得和
ak + ak+1 + ·· + al 是 m的倍数。
证 设 Sk = ∑ai,Sh≡ rh mod m 0≤rh≤m-1
h = 1,2,··,m,若存在 l,Sl≡0 mod m 则命题成立．否则,1≤rh≤m-1,但 h = 1,2,
··,m,由鸽巢原理，故存在 rk = rh,即
Sk≡ Sh,不妨设 h ＞ k,则
Sh－ Sk = ak+1 + ak+2 +… + a h ≡0 mod m
i=1
h
§３,7 鸽巢原理之一例６ 设 a1,a2,a3为任意３个整数,b1b2b3
为 a1,a2,a3的任一排列，则 a1－ b1,a2－ b2,
a3－ b3中至少有一个是偶数．
证 由鸽巢原理,a1,a2,a3必有两个同奇偶．设这３个数被２除的余数为 xxy,于是 b1,b2,b3中被２除的余数有２个 x,一个
y,这样 a1－ b1,a2－ b2,a3－ b3被２除的余数必有一个为０．
§３,7 鸽巢原理之一例７ 设 a1,a2,··,a100是由 1和２组成的序列,已知从其任一数开始的顺序 10个数的和不超过 16．即
ai + ai+1 +… + a i+9 ≤16,1≤ i ≤91
则至少存在 h 和 k,k > h,使得
ah + ah+1 +… + a k = 39
证 令 Sj = ∑ai,j =1,2,…,100 显然
S1<S2<…<S 100,且 S100 = (a1 + … +a 10)
+ (a11 + … +a 20)+… + (a 91 + … +a 100)
i =1
j
§３,7 鸽巢原理之一根据假定有 S100≤10× 16 = 160
作序列 S1,S2,…,S 100,S1 +39,…,S 100+39,
共 200项．其中最大项 S100+39≤160+39
由鸽巢原理，必有两项相等．而且必是前段中某项与后段中某项相等．设
Sk = Sh + 39,k>h Sk－ Sh =39 即
ah + ah+1 +… + a k = 39
§３,8 鸽巢原理之二鸽巢原理二 m1,m2,…,m n都是正整数，
并有 m1 + m2 +… +m n－ n + 1个鸽子住进 n个鸽巢，则至少对某个 i 有 第 i 个巢中至少有
mi个鸽子,i = 1,2,…,n,
上一小节的鸽巢原理一是这一原理的特殊情况，即 m1 = m2 = … = m n= 2，
m1 + m2 +… +m n－ n + 1 = n + 1
如若不然，则对任一 i,都有第 i 个巢中的鸽子数 ≤mi－ 1 则
§３,8 鸽巢原理之二鸽子总数 ≤ m1 + m2 +… +m n－ n,
与假设相矛盾．
推论１ m只鸽子进 n个巢,至少有一个巢里有 「 － |只鸽子,nm
推论２ n(m－ 1) + 1只鸽子进 n个巢，至少有一个巢内至少有 m只鸽子．
推论３ 若 m1,m2,…,m n是正整数，且
> r－ 1,则 m1,…,m n至少有一个不小于 r
m1 + … +m n
n
§３,8 鸽巢原理之二例 设 A= a1a2···a 20是 10个 0和 10个 1 组成的
２进制数,B=b1b2···b 20是任意的２进制数．
C = b1b2···b 20 b1b2···b 20 = C1C2···C 40,则存在某个 i,1≤ i ≤20,使得
CiCi+1···C i+19与 a1a2···a 20至少有 10位对应相等．
…..,…...
...,..,..,..
A B
C
第 i 格 第 i +19格
1 2 ······· 19 20 1 2 ······ 19 20
1 2 ······ 19 20 1 ····· 19 20
§３,8 鸽巢原理之二证 在 C = C1C2···C 40中，当 i 遍历 1,2,…,
20时，每一个 bj历遍 a1,a2,…,a 20,因 A中有 10个 0和 10个 1，每一个 bj都有 10位次对应相等．从而当 i历遍 1,…,20 时，共有
10 · 20=200位次对应相等．故对每个 i平均有 200 20 = 10位相等，因而对某个 i 至少有 10位对应相等．
§３,8 鸽巢原理之二定理 若序列 S ={ a1,a2,…,a mn+1}中的各数是不等的,m,n 是正整数，则 S有一长度为 m+1的严格增子序列或长度为 n+1的减子序列，而且 S有一长度为 m+1的减子序列或长度为 n+1的增子序列．
证１ 由 S中的每个 ai 向后选取最长增子序列，设其长度为 li,从而得序列
L = { l1,l2,…,l mn+1 },若存在 lk≥m+1
则结论成立．
§３,8 鸽巢原理之二否则所有的 li ∈ [ 1,m],其中必有
「 | = n+1个相等．
设 li1 = li2 = ·· = lin= lin+1 不妨设 i1<i2< ·· <in+1
应有 ai1 > ai2 > ·· > ain+1,即有一长度为
n+1的减子列．
否则 不妨设 ai1 < ai2,则有
li1 > li2,矛盾．
mn+1
m
§３,8 鸽巢原理之二证２ 从 ai 向后取最长增子列及减子列，设其长度分别为 li,l’i,
若任意 i,都有 li ∈ [ 1,m],l’i∈ ［１,n］,
不超过 mn种对．则存在 j <k,( lj,l’j ) = ( lk,l’k )
若 aj <ak,则 lj >lk，
若 aj >ak,则 l’j >l’k,矛盾．
§３,8 鸽巢原理之二例 将 [ 1,65 ]划分为４个子集，必有一个子集中有一数是同子集中的两数之差．
证 用反证法．设次命题不真．即存在划分 P1∪ P2∪ P3∪ P4＝ [ 1,65 ],Pi
中不存在一个数是 Pi中两数之差,i=1,2,3,4
因 = 17，故有一子集，其中至少有 17
个数，设这 17个数从小到大为 a1,…,a 17,
不妨设 A={a1,…,a 17 } P1。
令 bi－ 1= ai－ a1,i = 2,···,17。
65
4
§３,8 鸽巢原理之二设 B＝｛ b1,··,b16},B [ 1,65 ]。
由反证法假设 B∩P1 = ф。 因而
B ( P2∪ P3∪ P4 )。
因为 ＝ 6，不妨设 {b1,··,b6} P2,
令 Ci－ 1=bi－ b1,I = 2,···,6
设 C＝ { C1,··,C5 },C [ 1,65 ]
由反证法假设 C∩( P1∪ P2 ) =ф,故有
C (P3∪ P4 )
因为 ＝ 3，不妨设 {C1,C2,C3 } P3
16
3
5
2
§３,8 鸽巢原理之二令 di－ 1= Ci－ C1,I = 2,3
设 D＝ { d1,d2 },D [ 1,65]。
由反证法假设 D∩( P1∪ P2∪ P3 )=ф,因而
D P4 。
由反证法假设
d2－ d1∈ P1∪ P2∪ P3 且 d2－ d1∈ P4,
故 d2－ d1 ∈ [ 1,65 ],但显然
d2－ d1 ∈ [ 1,65 ]，
矛盾。
§３,9 Ramsey 问题
１,Ramsey问题
Ramsey问题可以看成是鸽巢原理的推广．下面举例说明 Ramsey问题．
例 6 个人中至少存在３人相互认识或者相互不认识．
证 这个问题与 K6的边２着色存在同色三角形等价．假定用红蓝着色,
§３,9 Ramsey 问题设 K6的顶点集为 {v1,v2,··,v6 },dr(v)表示与 顶点 v 关联的红色边的条数,db(v)表示与 v 关联的蓝色边的条数．在 K6 中，有
dr(v)＋ db(v)＝５,由鸽巢原理可知，至少有３条边同色．
现将证明过程用判断树表示如下：
§３,9 Ramsey 问题
dr(v1)≥3?
db(v1)≥3 设 (v1v2) (v1v3) (v1v4)为红边设 (v1v2) (v1v3) (v1v4)为蓝边
△ v2v3v4是红△?
△ v2v3v4是蓝△?
设 ( v2v3 )是蓝边设 ( v2v3 )是红边
△ v1v2v3是蓝△
△ v1v2v3是红△√
√
YN
N
N
Y
Y
§３,9 Ramsey 问题
２．若干推论
( a ) K6的边用红蓝任意着色，则至少有两个同色的三角形．
证 由前定理知，有同色三角形，不妨设
△ v1v2v3是红色三角形可由如下判断树证明．
§３,9 Ramsey 问题
△ v1v4v5是蓝△
设 (v4v5)为蓝边
△ v4v5v6是红△?
设 (v1v4) (v1v5) (v1v6)为蓝边
db(v1)≥3
dr(v1)≥3? 设 (v
1v4)为红边
(v4v2) (v4v3) 为蓝边?
设 (v4v2)为红边 db(v4)≥3?
△ v1v2v4是红△ dr(v4)≥3
设 (v4v5)为蓝边(v4v5) (v4v6) 为红边
△ v2v3v5是红△?
设 (v2v5)为蓝边
△ v2v4v5是蓝△△ v
4v5v6是红△
△ v1v5v6是蓝△?
设 (v5v6)为红边 √
√
√
y
y
y
yy
y
n
n
n
n n
§３,9 Ramsey 问题
( b ) K9 的边红蓝两色任意着色，则必有红 K4或蓝色三角形 (蓝 K4或红色三角形 )．
证 设９个顶点为 v1,v2,··,v9,对９个顶点的完全图的边的红、蓝２着色图中，
必然存在 vi,使得 dr(vi)≠3,否则，
红边数＝ ∑ dr(vi)＝,这是不可能的．
不妨设 dr(v1)≠3,可得如下判断树证明结论．
1
2
27
2
§３,9 Ramsey 问题
dr(v1)≥4?
db(v1)≥6 设 (v1v2) (v1v3) (v1v4)(v1v5)是 4红边设 (v1v2) ·· (v1v7)是 6条蓝边
K4(v2v3v4v5)是蓝 K4?
K6(v2···v 7)中有红 △?
设 (v2v3)是红边
△ v1v2v3是红△
设△ v2v3v4是红△
K4(v2v3v4v5)是蓝 K4
√
√Y
Y
YN
N
N
§３,9 Ramsey 问题
∴ K9的边红、蓝２着色，必有红色三角形或蓝色 K4．
同理可证 K9的红、蓝２着色，必有蓝色三角形或红色 K4,
(红△ ∨ 蓝 K4) ∧ (蓝 △ ∨ 红 K4)
＝ 存在同色 K4或红△及蓝 △
＝同色 K4 ∨ (红△ ∧ 蓝△ )
§３,9 Ramsey 问题
( c ) K18的边红，蓝２着色，存在红 K4
或蓝 K4,
证 设 18个顶点为 v1,v2,··,v18,从 v1引出的 17条边至少有９条是同色的，不妨先假定为红色．从而可得下面的判断树证明命题．
§３,9 Ramsey 问题
dr(v1)≥9
db(v1)≥9 设 (v1v2) ·· (v1v10)是 红边
K9(v2 ·· v10)中有同色 K4
或红△加蓝△
K10( v1v2 ···v 10)中有同色 K4
设 (v1v2) ·· (v1v10)是 蓝边
K9(v2 ·· v10)中有同色 K4
或红△加蓝△
K10( v1v2 ···v 10)中有同色 K4
YN
§３,10 Ramsey数将上一节的问题一般化：给定一对正整数
a,b,存在一个最小的正整数 r,对 r 个顶点的完全图的边任意红、蓝２着色，存在
a 个顶点的红边完全图或 b 个顶点的 蓝边完全图。 记为 r ( a,b )。 比如：
r ( 3,3 )＝ 6,r ( 3,4 )＝ 9，
r ( 4,4 )＝ 18
１,Ramsey数的简单性质
§３,10 Ramsey数定理 r ( a,b )＝ r ( b,a )； r ( a,2 )＝ a
证 K r(a,b )的边红蓝２着色，有红 Ka或蓝
Kb,将红蓝２色对换，就有红 Kb或蓝 Ka．
设 r ( a,b )＝ r,Kr的边任意红蓝２着色红蓝互换后仍是 Kr的边的２着色，由 r(a,b)
的定义，有红 Ka或蓝 Kb,再红蓝对换恢复原图有红 Kb或蓝 Ka．
§３,10 Ramsey数例 K9的边任意红蓝２着色，有红三角形或蓝 K4,红蓝对换后，仍有红三角形或蓝
K4,再对换一次，回到原来的着色方案，
有蓝三角形或红 K4．
第二个等式容易看出,Ka红蓝２着色若不全红 (红 Ka),则必有一条蓝边．
§３,10 Ramsey数定理 当 a,b ≥２ 时，
r ( a,b )≤ r ( a － 1,b )＋ r ( a,b－ 1 )
证 对 r ( a － 1,b )＋ r ( a,b－ 1 ) 个顶点的完全图红蓝２着色．任取其中一点 v，
有
dr(v) + db(v) = r( a － 1,b ) + r( a,b－ 1 )－ 1
从而可得判断树如下．
§３,10 Ramsey数
dr(v)≥r (a－ 1,b)?
db(v)≥r (a,b － 1 )
与 v 以红边相连的 r(a－ 1,b)个顶点的完全图中有一个红 Ka－ 1?
有蓝 Kb
红 Ka或蓝 Kb
V与 这 a－ 1个点构成红 Ka
N
Y
Y
N
§３,10 Ramsey数推论 r (a,b ) ≤ ( )a + b－ 2a－ 1
证 r ( a,b )≤ r ( a － 1,b )＋ r ( a,b－ 1 )
≤( )＋ ( )
＝ ( ) a + b－ 2a－ 1
a + b－ 3
a－ 2
a + b－ 3
a－ 1
§３,10 Ramsey数定理 若 a ≥３,则 r ( a,a) > 2
a
2
证 Kn有 ( )条边，对边红蓝２着色有
2 种方案．其中同色 Ka的 方案数不超过
n
2n
2( )
a
2( )( ) · 2 · 2
n
2( )－n
2
Ka的个数可红可蓝可任意着色边数同色边数
§３,10 Ramsey数这是一个上界,Kn中含 Ka的方案被重复计数．若取 n足够小，便得
a
2( )( ) · 2
n
a( )－ + 1 n
a < 2
n
2( )
则必有 Kn的一个２着色方案中无同色 Ka，
有 r ( a,a)定义可知,r (a,a)>n
即 ( ) < 2 n= 2 时
( ) < = 2 = 2 · 2
≤2
a
2( )－１n
a
a
2
a
2( )－ 1
n
a
na
2a－ 1
－ a+1a
2
2
a
2( )－ 1 － +2
a
2
§３,10 Ramsey数所以 r (a,a) > 2
a
2
§３,10 Ramsey数
２,Ramsey数的推广若将２着色改为 k 着色，同色 Ka或同色
Kb改为同色 Ka i i = 1,2,…,k,即得 Ramsey
数 r ( a1,a2,…,a k),对于给定的正整数 ai
( ai ≥2),i = 1,2,…,k,存在最小正整数
r,对 Kr的边用 k中颜色 Ci ( i = 1,2,…,k)
任意着色．则存在 i,出现全 Ci色的 Ka i,(
即边都是 Ci色的 ai个顶点的完全图）；
这个最小正整数 r 用 r (a1,…,a k)表示．
§３,10 Ramsey数有 r (a1,a2,…,a k)≤ r ( a1,r ( a2,…,a k) )
证 设 r ( a1,r ( a2,…,a k) ) = p，
r (a2,…,a k) = q；
对 Kp的边２着色，出现第一色 Ka1或第二色 Kq，
用 n－ 1中色对 Kq的边着色，至少出现 i色的 ai点完全图,i = 2,…,n,对 Kp的边 n 着色，将后
n－ 1中色看作同一种色，出现第一色 Ka 1或另一色 (n－ 1种色看作另一色）的 Kq,即出现 第 I 色
Ka i,I = 2,…,n,故 r (a1,a2,…,a k)≤ p
§３,10 Ramsey数例 r ( 3,3,3) = 17
证 设三色为 r,b,g,则对 K17的任一顶点 v
有 dr(v) + db(v) + dg(v) = 16； 因 =6,
故任一顶点与其他顶点的连线中，至少有
６条同色．不妨设 dr(v1)≥6,(v1v2)…(v 1v7)
都是红边．
从而可得如下判断树．
16
3
§３,10 Ramsey数
K6(v2···v 7)中无红边?
K6(v2···v 7)中有红边
K6(v2···v 7)中蓝绿２着色有蓝 K3或绿 K3
设 (v2v3)为红边
△ v1v2v3是红色的原题得证．
YN
§ 1 容斥原理引论例 [1,20]中 2或 3的倍数的个数
[解 ] 2的倍数是,2,4,6,8,10，
12,14,16,18,20。 10个
§ 3.1 容斥原理引论
3的倍数是,3,6,9,12,15，
18。 6个但答案不是 10+6=16 个，因为 6，
12,18在两类中重复计数，应减去。故答案是,16-3=13
§ 3.2 容斥原理容斥原理 研究有限集合的 交或并的计数 。
[DeMorgan定理 ] 论域 U,补集
A
{ | }A x x U x A且,有
§ 3.2 容斥原理
(a)
A B A B?
(b)
A B A B?
证,(a)的证明。
设,则相当于 和同时成立，亦即
BAx
BAx
BAx Ax?
Bx?
A A B x A B (1)
§ 3.2 容斥原理反之，若 x A B x A x B,即 和故,x A x B x A B和 亦即
xx BA AB (2)
由（ 1）和（ 2）得
x BA ABx
(b)的证明和（ a)类似，从略,
§ 3.2 容斥原理
DeMogan定理的推广：设
1,2,.,,,nA A A U是 的子集
2 1 2.,,,,,nnA A A A A?1则 ( a ) A 2 1 2.,,,,,nnA A A A A?1( b ) A
证明,只证 (a),N=2时定理已证。
设定理对 n是正确的，即假定：
§ 3.2 容斥原理
2 1 2.,,,,,nnA A A A A?1A
正确
21
12
12
11
1
1
..,(,.,)
(,.,
...
nnnn
n
n
n
n
A A A A A A
A A A A
A A A A
1
则
A
即定理对 n+1也是正确的。
§ 3.2 容斥原理
§ 2 容斥原理最简单的计数问题是求有限集合 A
和 B的并的元素数目。显然有即具有性质 A或 B的元素的个数等于具
A B A B A B
(1)
定理,
§ 3.2 容斥原理有性质 A和 B的元素个数。
U
BA AB
§ 3.2 容斥原理
§ 3.2 容斥原理证 若 A∩B=φ,则 | A∪ B |= |A| + |B|
| A |＝ | A ∩( B∪ B) |
＝ | (A∩B)∪ (A∩B)|
＝ | A∩B | + | A∩B | ( 1 )
同理 | B | ＝ | B∩A | + | B∩A | ( 2 )
| A∪ B |＝ |(A∩( B∪ B))∪ (B∩(A∪ A))|
＝ |(A∩B)∪ (A∩B)∪ (B∩A)∪ (B∩A)|
＝ | A∩B| + |A∩B | + | B∩A| ( 3 )
§ 3.2 容斥原理
( 3 ) － ( 1 ) － ( 2 ) 得
| A∪ B |－ | A |－ | B |
＝ | A∩B| + |A∩B | + | B∩A|
－ ( | A∩B | + | A∩B | )
－ ( | B∩A | + | B∩A | )
＝－ | A∩B |
∴ | A∪ B |＝ | A | + | B |－ | A∩B |
定理：
(2)A B C A B C A B
B C A B C
A C-
：
()
()
A B C A B C
A B C A B C
证明
§ 3.2 容斥原理
( ) ( ) ( )
( ) ( )
A B C A C B C
A B C A B C A B
A C B C
A B C A B B C
A B C
根据
C- A
§ 3.2 容斥原理
A B
C
AC BC
AB
A B C
§ 3.2 容斥原理例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有 170,130,120人；同时修数学、物理两门课的学生 45人；同时修数学、化学的 20人；同时修物理化学的 22人。同时修三门的 3人。问这学校共有多少学生？
§ 3.2 容斥原理令,M为修数学的学生集合；
P 为修物理的学生集合；
C 为修化学的学生集合；
1 7 0,1 3 0,1 2 0,4 5
2 0,2 2,3
P C M P
M C P C M P C
M
§ 3.2 容斥原理
1 7 0 1 3 0 1 2 0 4 5 2 0 2 2 3
336
M P C P C M P M
M C P C M P C
M
即学校学生数为 336人。
§ 3.2 容斥原理同理可推出：
A B C D A B C D A B
B C A D A B C
A B D B C D A B C D
A C
利用数学归纳法可得一般的定理：
§ 3.2 容斥原理定理 设 ￠ (n,k)是［ 1,n］ 的所有 k-
子集的集合,则
|∪ Ai | = ∑ (－ 1)k-1 ∑ | ∩ Ai |
证 对 n用归纳法。 n=2时，等式成立。
假设对 n - 1,等式成立。对于 n有
§ 3.2 容斥原理
n
i=1 k=1
n
I∈ ￠ (n,k) i∈ I
§ 3.2 容斥原理
1
i
11
11
11
1
11
11
11
11
A
()
( 1 ) ( 1 ) ( )
nn
in
ii
nn
i n i n
ii
nn
i n i n
ii
nn
kk
i n i n
kk iI
AA
A A A A
A A A A
A A A A
I∈ ￠ (n-1,k) I∈ ￠ (n-1,k)i∈ I
§ 3.2 容斥原理
11
1
12
1
2
1
1
( 1 )
( 1 )
( 1 )
nn
k
i i n
ik iI
n
k
in
k iI
n
k
i
k iI
A A A
AA
A
I∈ ￠ (n,k)
I∈ ￠ (n-1,k-1)
I∈ ￠ (n-1,k)
此定理也可表示为：
定理,设
1,2,..,,nA A A
是有限集合，则
12
11
1
1
2
...
...
( 1 ),..
n
nn
i i j
i i j i
k
n
j
n
A A A
A A A
AA
A A A
n
i
i=1 j>i k>j
+ A
(4)
§ 3.2 容斥原理证,用数学归纳法证明。
已知 n=2时有
1 2 1 2 1 2A A A A A A
设 n-1时成立，即有：
§ 3.2 容斥原理§ 容斥原理
1 2 1
11
11
1 2 1
...
...
( 1 ),..
n
nn
i i j
i i j i
jk
n
n
A A A
A A A
AA
A A A
n-1
i
i=1 j>i k>j
A+
§ 3.2 容斥原理
1 2 1
1 2 1
1 2 1
1 2 1
...
(,.,)
...
(,.,)
nn
nn
nn
nn
A A A A
A A A A
A A A A
A A A A
§ 3.2 容斥原理
1 2 1
12
..,)
( ) ( ),.,
),
nn
nn
n
A A A A
A A A A
A
n-1
但 (
(A
§ 3.2 容斥原理
1 2 1
1 2 1
1 2 1
1 2 1 3
(,,,)
( ) ( ),,,( )
...
...
nn
n n n n
n n n n
nn
A A A A
A A A A A A
A A A A A A
A A A A A A
§ 3.2 容斥原理
2 1 1 2
11
11
12
.,,( 1 ),,,
...
( 1 ),,,
n
n n n n
nn
i n i j n
i i j i
n
n
A A A A A A
A A A A A
A A A
§ 3.2 容斥原理
1 2 1
11
1
1
2
...
...
( 1 ),..
nn
nn
i i j
i i i
n
n
j
jk
A A A A
A A A
AA
A A A
n
i
i=1 j>i k>j
A+
§ 3.2 容斥原理
,NA又 A
其中 N是集合 U的元素个数，即不属于
A的元素个数等于集合的全体减去属于
A的元素的个数。一般有：
§ 3.2 容斥原理
1 2 1 2 1
11
12
...,..
...
( 1 ),..
n n n
nn
i i j
i i j
jk
n
i
n
A A A N A A A A
N A A A
AA
A A A
n
i
i= 1 j> i k> j
A-
(5)
容斥原理指的就是（ 4）和（ 5）式。
§ 3.2 容斥原理
§ 3 例例 1 求 a,b,c,d,e,f六个字母的全排列中不允许出现 ace和 df图象的排列数。
解,设 A为 ace作为一个元素出现的排列集,B为 df作为一个元素出现的排列集,为同时出现 ace,df的排列数。
AB
§ 3.3 例
4 !,5 !,3 !,A B A B
根据容斥原理，不出现 ace和 df的排列数为：
AB
=6!- (5!+4!)+3!=582
§ 3.3 例例 2 求从 1到 500的整数中能被 3或 5
除尽的数的个数。
解,令 A为从 1到 500的整数中被 3除尽的数的集合,B为被 5除尽的数的集合
50 0 50 0
16 6,10 0 ;
35
500
33
15
AB
AB
§ 3.3 例被 3或 5除尽的数的个数为
1 6 6 1 0 0 3 3 2 3 3
A B A B A B
例 3 求由 a,b,c,d四个字母构成的位符号串中,a,b,c,d至少出现一次的符号串数目。
§ 3.3 例解,令 A,B,C分别为 n位符号串中不出现 a,b,c符号的集合。
由于 n位符号串中每一位都可取 a，
b,c,d四种符号中的一个，故不允许出现 a的 n位符号串的个数应是 3 n，即
3
2
n
n
BC
A B A C C B
A
§ 3.3 例
1A B C?
a,b,c至少出现一次的 n位符号串集合即为 A B C
4 ( ) (
33 24 3
)
1
n
nn n
A B C A B
A C C B A B C
A B C
§ 3.3 例例 4。 求不超过 120的素数个数。
因,故不超过 120的合数必然是 2,3,5,7的倍数，而且不超过
120的合数的因子不可能都超过 11。
设 为不超过 120的数 的倍数集，
=2,3,5,7。
211 121?
i A
i
i
§ 3.3 例
23
57
2 3 2 5
2 7 3 5
12 0 12 0
60 40
23
12 0 12 0
24 17,
57
12 0 12 0
20 12,
2 3 10
12 0 12 0
88
14 15
AA
AA
A A A A
A A A A
，，
，
，
，，
§ 3.3 例
3 7 5 7
2 3 5
2 3 7
2 5 7
12 0 12 0
53
21 35
120
4
2 3 5
120
2
2 3 7
120
1
257
A A A A
A A A
A A A
A A A
，，
，
，
，
§ 3.3 例
2 3 5 7 2 3 5
7 2 3 2 5 2 7
3 5 3 7 5 7
2 3 5 2 3 7
2 5 7 3 5 7
2 3 5 7
120A A A A A A A
A A A A A A A
A A A A A A
A A A A A A
A A A A A A
A A A A
§ 3.3 例
12 0 ( 60 40 24 17 ) ( 20 12 8
8 5 3 ) ( 4 2 1 1 )
27.
§ 3.3 例注意,27并非就是不超过 120的素数个数，因为这里排除了 2,3,5,7着四个数，又包含了 1这个非素数。 2，
3,5,7本身是素数。故所求的不超过
120的素数个数为：
27+4-1=30
§ 3.3 例例 5。 用 26个英文字母作不允许重复的全排列，要求排除 dog,god,gum，
depth,thing字样的出现，求满足这些条件的排列数。
解,所有排列中，令：
§ 3.3 例
1
2
3
4
5
A do g
A go d
A gu m
A de pth
A thing
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
为出现 的排列的全体；
§ 3.3 例出现 dog字样的排列，相当于把 dog作为一个单元参加排列，故 2 4 !?
1A
类似有：
2 3 4 52 4 !,2 2 !A A A A
由于 god,dog不可能在一个排列中同时出现，故：
12 0;AA?
类似：
2 3 1 40,0A A A A
§ 3.3 例由于 gum,dog可以在 dogum字样中同时出现，故有：
13 2 2 !AA?类似有 god和 depth可以在 godepth字样中同时出现，故
24 2 0 !AA?
god和 thing可以在 thingod字样中同时出现，从而
25 2 0 !AA?
§ 3.3 例
1 5 4 5
3 4 3 5
1 2 3 1 2 4
1 2 5 1 3 4
1 3 5 1 4 5
0,19 !,
20 !,
0,0
0,0
0,0
A A A A
A A A A
A A A A A A
A A A A A A
A A A A A A
§ 3.3 例
2 3 4 2 3 50,0A A A A A A
由于 god,depth,thing不可以同时出现，故有：
2 4 5 0AAA?
345 1 7 !A A A?
其余多于 3个集合的交集都为空集。
§ 3.3 例故满足要求的排列数为：
2 6 ! 3 2 4 ! 2 2 2 ! 2 2 ! 4 2 0 ! 1 9 ! 1 7 !
2 6 ! 3 2 4 ! 2 2 ! 4 2 0 ! 1 9 ! 1 7 !
§ 3.3 例例 6。 求完全由 n个布尔变量确定的布而函数的个数。
解,设
12(,,.,,,)nif x x x x中 不出现的布尔函数类为：,1,2,...,.in?
iA
由于 n个布尔变量 的不同的真值表数目与 位 2进制数数目相同，故为 个。根据容斥原理，
满足条件的函数数目为：
12,,...,nx x x
2n
22 n
§ 3.3 例
1
2
22
12
22
..,2 (,1 ) 2
(,2 ) 2,.,( 1 ) (,) 2
..,( 1 ) (,) 2
nn
n n k
n
k
n
A A A C n
C n C n k
C n n
2
22
2
2,
2 ( 2,1 ) 2 ( 2,2) 2
16 8 2 10
n
A C C
1
时得
A
§ 3.3 例
§ 3.3 例这 10个布尔函数为：
x1∧ x2,x1∧ x2,x1∧ x2,x1∧ x2，
x1∨ x2,x1∨ x2,x1∨ x2,x1∨ x2，
(x1∨ x2)∧ (x1∨ x2),(x1∨ x2)∧ (x1∨ x2)
例 7。 欧拉函数?(n)是求小于 n且与 n
互素的数的个数。
解,若 n分解为素数的乘积
12
12,..
ka a a
kn p p p?
设 1到 n的 n个数中为 倍数的集合为
i p
,1,2,.,,,.ik?iA
则有
§ 3.3 例
12
12
...
,1,2,...,.
，,1,2,...,.
k
a a a
ki
i
ij
ij
n p p p p
n
A i k
p
n
A A i j k i j
pp
,,,,,
§ 3.3 例
12
1 2 1 2
1 3 1 1 2
12
...
(,.,) (
..,)
1 1 1
( 1 ) ( 1 ) ( 1 )
k
k
nk
k
A A A
n n n n
n
p p p p p
n n n
p p p p p p p
n
p p p
(n)=
§ 3.3 例
2
6 0 2 3 5,
1 1 1
( 6 0 ) 6 0 ( 1 ) ( 1 ) ( 1 ) 1 6
2 3 5
n
例如 则即比 60小且与 60无公因子的数有 16个：
7,11,13,17。 19。 23,29,31，
37,41,43,47,49,53,59，此外尚有一个 1。
§ 3.3 例
§ 4 错排问题
n个元素依次给以标号 1,2,…,n。
N个元素的全排列中，求每个元素 都不在自己原来位置 上的排列数。
设 为数 在第 位上的全体排列，
=1,2,…,n。 因数字 不能动，
因而有：
iA i i
i i
§ 3.3 例
( 1 ) !,1,2,.,,,iA n i n
( 2) !,1,2,...,,
ij
A A n i n i j
同理
§ 3.4 错排问题每个元素都不在原来位置的排列数为
12
11
.,,! (,1 ) ( 1 )
1
! ( 1
!
(,2 ) ( 2 )
)
1 ! 2 ! !
! (,) 1 !
n
A A A n C n n
C n n
n
n
C n n
§ 3.4 错排问题例 1。 数 1,2,…,9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。
解,实际上是 1,3,5,7,9五个数的错排问题，总数为：
5 ! ( 5,1 ) 4 ! ( 5,2 ) 3 ! ( 5,3 ) 2 ! ( 5,4 ) 1 !
1 1 1 1
( 5,5 ) 1 2 0 ( ) 4 4
2 6 2 4 1 2 0
C C C C
C
§ 3.4 错排问题例 2,在 8个字母 A,B,C,D,E,F,G,H的全排列中,求使 A,C,E,G四个字母不在原来上的错排数目。
8个字母的全排列中，令分别表 A,C,E,G在原来位置上的排列，
则错排数为：
1 2 3 4,,,A A A A
§ 3.4 错排问题
1 2 3 4
8 ! ( 4,1 ) 7 ! ( 4,2 ) 6 !
( 4,3 ) 5 ! ( 4,4 ) 4 !
24024
A A A A C C
CC
§ 3.4 错排问题例 3。 求 8个字母 A,B,C,D,E,F,G,H的全排列中只有 4个不在原来位置的排列数。
解,8个字母中只有 4个不在原来位置上，其余 4个字母保持不动，相当于 4个元素的错排，其数目为
§ 3.4 错排问题
1 1 1 1
! ( 1 )
1 ! 2 ! 3! 4 !
1 1 1
24( 1 1 ) 9
2 6 2
4
4
故 8个字母的全排列中有 4个不在原来位置上的排列数应为,C(8,4)·9=630
§ 3.4 错排问题
§ 5 棋盘多项式和有限制排列
1,有限制排列
§ 3.5 棋盘多项式和有限制排列例 4个 x,3个 y,2个 z的全排列中，
求不出现 xxxx,yyy,zz图象的排列。
解 设出现 xxxx的排列的集合记为 A1，
|A1|= =60;
设出现 yyy的排列的集合记为 A2，
| A2|= =105；
6!
1!·3!·2!
4!2!
7!
§ 3.5 棋盘多项式和有限制排列设出现 zz的排列的集合记为 A3，
| A3|= =280；
|A1∩A2|= =12； |A1∩A3|= =20；
|A2∩A3|= =30； |A1∩A2∩A3|=3!=6；
全排列的个数为,=1260；
所以：
|A1∩A2∩A3|=1260－ (60+105+280)
+(12+20+30)－ 6
=871
4!·3!
8!
4!2! 5!
3!6!
4! 9!
2!·3!·4!
§ 3.5 棋盘多项式和有限制排列
2．棋子多项式
n个不同元素的一个全排列可看做 n个相同的棋子在 n× n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子
x
x
x
x
x
如图所示的布局对应于排列 41352。
§ 3.5 棋盘多项式和有限制排列可以把棋盘的形状推广到任意形状：
布子规定称为无对攻规则，棋子相当于象棋中的车。
令 r k（ C） 表示 k个棋子布到棋盘 C上的方案数。如：
§ 3.5 棋盘多项式和有限制排列
r1( )=1,r1( )=2,r1( )=2，
r2( )=0,r2( )=1。
为了形象化起见，（ ）中的图象便是棋盘的形状。
§ 3.5 棋盘多项式和有限制排列定义 设 C为一棋盘，称 R(C)= ∑ rk(C) xk
为 C的棋盘多项式。
规定 r0(C)=1,包括 C=Ф时。
设 Ci是棋盘 C的某一指定格子所在的行与列都去掉后所得的棋盘； Ce是仅去掉该格子后的棋盘。
在上面定义下，显然有
rk(C)=rk－ 1(Ci)＋ rk(Ce)，
k=0
∞
§ 3.5 棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk－ 1(Ci)；
要么不布子，方案数为 rk(Ce)。
设 C有 n个格子，则 r1(C)＝ n．
r1(C)＝ r0(Ci) + r1(Ce),∵ r1(Ce)＝ n－ 1
∴ r0(Ci)＝ 1,故规定 r0(C)＝ 1是合理的．
§ 3.5 棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk－ 1(Ci)；
要么不布子，方案数为 rk(Ce)。
从而
R(C)= ∑ rk(C) xk
＝１＋ ∑[rk－ 1(Ci)+ rk(Ce)]xk
= x ∑ rk(Ci)xk + ∑ rk(Ce)xk
＝ xR(Ci) + R(C e) (3)
∞
k=0
∞
∞∞
k=0
k=0k=0
§ 3.5 棋盘多项式和有限制排列例如：
R( )=1+ x；
R( )= xR( )+ R( )= x+ (1+ x)=1+2x；
R( )= x R( ) + R( )
= x(1 + x )+1 + x
=1+ 2x +x2
§ 3.5 棋盘多项式和有限制排列如果 C由相互分离的 C1,C2组成，即 C1
的任一格子所在的行和列中都没有 C2的格子。则有：
rk(C) = ∑ ri(C1) rk－ i(C2)
i=0
k
故 R(C) = ∑ (∑ ri(C1) rk－ i(C2) ) xk
= (∑ ri(C1) xi) (∑ rj(C2) xj )
j=0
nn
kn
i=0
i=0
k=0
∴ R(C) = R(C1) R(C2) (4)
§ 3.5 棋盘多项式和有限制排列利用（３）和（４），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，
从而得到其棋盘多项式。
例 R ( ) = xR( )+R( )
= x(1+ x)2 +(1+2x)2
=1+ 5x +6x2 + x3
*
R( ) = xR( ) + R( )
= 1+6x +10 x2 +4x3
§ 3.5 棋盘多项式和有限制排列
３．有禁区的排列例 设对于排列 P=P1 P2 P3 P4,规定 P1≠３，
P２ ≠１、４,P３ ≠2、４,P4≠2。
1 2 3 4
P1
P2
P3
P4
1 2 4 3
1
4 3
2
2
3
4 3
1 2
1
4
这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。
§ 3.5 棋盘多项式和有限制排列定理 设 ri 为 I个棋子布入禁区的方案数，
i =1,2,3,··,n。 有禁区的布子方案数（即禁区内不布子的方案数）为
r0 n! － r1(n－ 1)! ＋ r2(n－ 2)!－ ···＋ (－ 1)nrn
＝ ∑(－ 1)k rk ( n－ k)!
k=0
n
证 设 Ai 为第 i个棋子布入禁区，其他棋子任意布的方案集,i =1,2,3,…,n 。
§ 3.5 棋盘多项式和有限制排列则所有棋子都不布入禁区的方案数为
｜ A1∩A2∩···∩An｜
＝ n！＋ ∑(－ 1)k ∑ ｜ ∩Ai｜
I∈ ￠ (n,k)
n
i∈ Ik=0
而 ∑ ｜ ∩Ai｜ 正是 k个棋子布入禁区，其他 n - k个棋子任意布的方案数 。由假设可知等于 rk(n－ k)！ (注意：布入禁区的棋子也要遵守无对攻规则）,所以
｜ A1∩A2∩···∩An｜ =n!+ ∑(－ 1)k rk ( n－ k)!
I∈ ￠ (n,k) i∈ I
k=0
n
§ 3.5 棋盘多项式和有限制排列上例方案数为
4!－ 6(4－ 1)!＋ 11(4－ 2)!－ 7(4－ 3)!
＋ 1(4－４ )!＝ 4
例 １，２，３，４四位工人,A,B，
C,D四项任务。条件如下：
１ 不干 B；２ 不干 B,C；
３ 不干 C,D；４ 不干 D。
问有多少种可行方案？
§ 3.5 棋盘多项式和有限制排列解 由题意，可得如下棋盘：
其中有影线的格子表示禁区。
A B C D
1
2
3
4
R( )=1+6x+10x2+4x3
方案数 =4!－ 6(4－ 1)!+10(4－ 2)!－ 4(4－ 3)!
+0(4－ 4)!=4
§ 3.5 棋盘多项式和有限制排列例 三论错排问题错排问题对应的是 n× n的棋盘的主对角线上的格子是禁区的布子问题。
C = ···
R( C ) = ( 1 + x )n = ∑ ( ) xk 令 rk = ( )nk=0
nk
n
k
故 R(C)中的 xn,n! + ∑(－ 1)k ( ) (n－ k)!
= n!∑ (－ 1)k － =Pnk=1
n
n
k=0 k!
1k
n
§ 3.6 一般公式
§ 3.6 一般公式若将§３,2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少
”“只修两门课的学生有多少？”则相应的答案表示如下：
｜ M∩P∩C｜；
｜ M∩P∩C｜ +｜ M∩P∩C｜ +｜ M∩P∩C｜
｜ M∩P∩C｜ +｜ M∩P∩C｜ +｜ M∩P∩C｜
§ 3.6 一般公式设有与性质１,2,··,n相关的元素 N个，
Ai为有第 i 种性质的元素的集合,i=1,2,…,n
Pk为至少有 k种性质的元素的元次；
qk为恰有 k种性质的元素的个数。
P0 = N,P1 = | A1 | + | A2 | + ··+ | An |，
P2 = | A1∩A2 |+ | A1∩A3 |+ ··+ | An - 1∩An |
Pk = ∑ | ∩Aij |
qk = ∑ | (∩ Ai)∩ ( ∩ Aj)|
I∈ ￠ (n,k) i ∈ I
I∈ ￠ (n,k) i ∈ I j ∈ I
§ 3.6 一般公式定理 qk = ∑ (－ 1)i( )Pk+ik+iii=0n-k
证１ 设某一元素恰有 k种性质，则其对 Pk
的某一项的贡献为１，而对 Pk+1,Pk+2,··,
Pn的贡献都是０。若某一元的性质少于 k种则其对 Pk,Pk+1,···,Pn的贡献都是０。若恰有 k + j种性质，则其对 Pk的贡献是 ( ),
对 Pk+i的贡献是（ ）
k + j
k k + j
k + i
§ 3.6 一般公式而 ∑ (－ 1)i ( ) ( )
= ∑ (－ 1)i ( ) ( )
= ∑ (－ 1)i ( ) ( ) = ( ) ∑ (－ 1)i ( )
= ( ) · 0 = 0
即某恰有 k + j种性质的元素对上式右边的总的贡献为０。
k + j
k + i
k + i
ii = 0
j
i = 0
j k + j
k + i
k + i
k
i = 0
j k + j
i
j
k
k + j
k
j
i
k + j
k
§ 3.6 一般公式前例中只修一门课的学生为：
| M∩P∩C | + | M∩P∩C | + | M∩P∩C |
= q1= ∑ (－ 1)j - 1 ( ) Pj
= P1 － 2P2 + 3P3
j
1j =1
3
在一般公式中，若令
P0 = N,q0 = | A1∩A2∩···∩An |，
就得到原来的容斥原理。
§ 3.6 一般公式证２ 根据定义
qk = ∑ | (∩ Ai)∩ ( ∩ Aj)|
qk由 Pk+j的代数和组成，符号 (－ 1)j,计算
Pk+j的重复度,k + j个集的交的绝对值的项的总个数为 ( ) ( ),共 ( )种。
每一项的重复度为
( ) ( ) ( ) = ( )
从而 Pk+j的重复度也是 ( )
I∈ ￠ (n,k) i ∈ I j ∈ I
n
k k + j
k + j
k + j
k + j
j
n－ k
n－ k
n
nn
k j k
k
§ 3.6 一般公式
∴ qk = ∑(－ 1)j ( )Pk+j
= ∑(－ 1)j － k ( ) Pj
k + j
k
k
j
j =0
n － k
k
n
证３ 对 N做归纳。
N = 1时，设此元有 m种性质,m ＜ n,
不妨设 A1 =A2= ·· =Am={ a1 }。 显然
Pj = ( ),若 j＞ m,则 Pj = 0；
由定义，得 qk=｛
j
m
1 k = m
0 k ≠m
§ 3.6 一般公式右端＝ ∑ (－ 1)i( )Pk+i
＝ ∑ (－ 1)i( ) ( )
＝ ∑ (－ 1)i( ) ( ) = {
k+i
ii=0
n－ k
k+i
k
m
k+ii=0
n－ k
m
k
m - k
i i=0
n－ k 1 k =m
0 k≠m
假设对于 N－ 1,等式成立。
对于 N,设新增元有 m种性质，对于 N个元的 P’j＝ Pj＋ ( ),q’k＝｛
j
m 1 k =m
0 k≠m
§ 3.6 一般公式右端＝ ∑ (－ 1)i ( )P’k+i
＝ ∑ (－ 1)i ( ) [Pk+ i + ( )]
＝ ∑ (－ 1)i ( )Pk+i +∑ (－ 1)i ( )( )
＝ qk + ｛
等式成立．
k + i
ki=0
n－ k
k + i
k k + i
m
k + i
ki=0
n－ k
k + i
ki=0
n－ k
k + i
m
n－ k
i = 0
1 k =m
0 k≠m
§ 3.6 一般公式例 某校有１２个教师，已知教数学的有
８位，教物理的有６位，教化学的５位；
数、理５位，数、化４位，理、化３位；
数理化３位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？
解 令教数学的教师属于 A1,教物理的属于 A2,教化学的属于 A3。 则 P0＝１２，
P1＝ | A1 |+| A2|+| A3 |＝ 8+6+5＝１９ ;
P2＝ | A1∩A2|+ | A1∩A3|+| A2∩A3|＝ 12；
P3＝ | A1∩A2∩A3|＝ 3；
§ 3.6 一般公式故 教其他课的老师数为：
q0＝ P0 － P1 +P2－ P3＝２
恰好一门的教师数：
q1＝ P1－ 2P2 + 3P3＝ 4
恰好教两门的老师数为：
q2＝ P2－ 3P3＝ 3
§ 3.6 一般公式例 n 对夫妻围坐问题设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？
解 不妨设 n 个女人先围成一圈，方案数为 ( n－ 1 )! 。 对任一这样的给定方案，顺时针给每个女人以编号 1,2,··,n。 设第 i
号与第 i + 1号女人之间的位置为第 i 号位置,1≤ i ≤n－ 1。 第 n 号女人与第 1 号之
§ 3.6 一般公式间的位置为第 n 号位置。设第 i 号女人的丈夫的编号也为第 i 号,1≤ i ≤ n。 让 n 个男人坐到上述编号的 n 个位置上。设 ai是坐在第 i 号位置上的男人，则
ai ≠ i,i + 1，１ ≤ i ≤n－ 1； an≠n,1。
这样的限制也即要求在下面 3行 n列的排列中
１ ２ ３ ··· ··· n－１ n
２ ３ ４ ··· ··· n 1
a1 a2 a3 ·· ·· an－ 1 an
§ 3.6 一般公式每列中都无相同元素。满足这样的限制的排列 a1a2 ···an称为 二重错排 。
设二重错排的个数为 Un,原问题所求的方案数就是 Un ( n－ 1)！。
设 Ai为 ai = I 或 I + 1 (1≤ I ≤n－ 1 ),an = n
或 1的排列 a1 a2 ··· an的集合。 则
｜ Ai｜ = 2 (n－ 1)!,关键是计算 ∑ |∩Ai|
I ∈ ￠ ( n,k) i∈ I
§ 3.6 一般公式也就是从 ( 1,2 ) ( 2,3 ) ·· ( n－１,n ) ( n,1)
这 n对数的 k 对中各取一数，且互不相同的取法的计数。这相当于从 1,2,2,3,3,4,··,
n－ 1,n－ 1,n,n,1中取 k 个互不相邻数的组合的计数，但首尾的１不能同时取。回想无重复不相邻组合的计数：
C’( n,r ) = C ( n－ r + 1,r ),这里所求的是
( )－ ( )= ( )2n－ k+1 k 2n－ 4－ ( k－ 2)+1k－ 2 2n－ kk2n2n－ k
§ 3.6 一般公式
∴ Un =∑(－ 1)k ( )(n－ k)!
= ｜ ∩ Ai｜
2n
2n－ k
2n－ k
k
i ∈ [ 1,n ]
§３,11 反演基本想法,{an} 易算,{bn}难算,{an}可用
｛ bn｝ 表示，利用反演，将 {bn}用 {an}表示．
１．二项式反演
1
( 1 ) {
0,
n
mk
km
n k n
k m m n
，m引理
§３,11 反演证
0
( 1 )
( 1 )
1
{
0,
n
km
m
nm
i
n n m
m k m
n n m
mi
mn
mn
左边
，
§３,11 反演定理
00
( 1 ) ( 1 )
nn
kk
n k n k
kk
nn
a b b a
kk
0 0 0
00
00
00
( 1 ) ( 1 ) ( 1 )
( 1 ) ( 1 )
( 1 )
( 1 )
n n n
k k l
kl
k k l
nk
kl
l
kl
nk
kl
l
kl
nn
kl
ln
lk
n n k
ab
k k l
nk
b
kl
nk
b
kl
nk
bb
kl
证
§３,11 反演
00
( 1 )
nn
nk
n k n k
kk
nn
a b b a
kk
推论证 在定理中 bk处用 (－ 1)k bk代入，即可．
例 n! = ∑ ( ) Dn－ k,Dn=bn，
令 n－ k = l,则 n! = ∑ ( ) Dl
Dn = ∑ (－ 1)n-k ( )k!
= n! ∑ (－ 1)n-k
= n ∑
n
k n
kn
k 1
(n－ k)!
k=0
k=0
k=0
n
n
n (－ 1)k
k!
§３,11 反演
２,Mǒbíus反演定义 设 n ∈ Z+
1,若 n = 1;
μ( n ) = 0,若 n = p1α1 p2α2 ··· pkαk 存在 αi>1
(－ 1)k,若 n = p1p2···p k
如 μ( 30) = μ( 2·3·5 ) = (－ 1)3
μ( 12) = 0；
§３,11 反演定理 设 n ∈ Z+
则 ∑ μ( d ) =
1，若 n = 1；
0，若 n > 1；d | n
证 若 n =1,∑ μ( d ) = μ( 1 ) = 1,成立．
若 n>1,设 n = p1α1 p2α2 ··· pkαk,n’ = p1p2···p k
∑μ( d ) = ∑μ( d ) =∑ ∑ μ( ∏pi ) +μ(1)
=1 + ∑( ) (－ 1)j = (1－ 1)k = 0
d | n
d | n d | n’ j=1
k
i∈ II∈ ￠ (k,j)
k
jj=1
k
§３,11 反演推论?(n) = n ∑ μ(d )dd | n
证 n ∑ = n ∑
= n · { 1 + ∑ (－ 1)j ∑ ( ∏ pi )－ 1}
= n ∏ (1－ ) =?(n)
μ(d )
dd | n
μ(d )
dd | n’
1
pi
j =1
i =1
k
k
I ∈ ￠ (k,j ) i ∈ I
§３,11 反演定理 ( Mǒbíus反演定理 )设 f ( n )和 g ( n )
是定义在正整数集合上的两个函数．
f ( n ) = ∑ g (d ) = ∑ g ( ) (M1 )
g( n ) = ∑μ(d) f ( ) = ∑μ( )f (d) (M2) nd nd
d | n d | n
d | nd | n
则 ( M1 ) ( M2 )
n
d
§３,11 反演证,?”设 ( M1 )成立。
∑μ(d) f ( ) = ∑μ(d) ∑ g ( d1 )
= ∑ ∑μ(d) g ( d1 ) = ∑μ(d) g( d1 )
=∑ ∑ μ(d) g ( d1 ) = ∑ g(d1 ) ∑ μ(d)
= ∑μ(d) = = g( n )
d | n d | n
d | n dd1 | n
d1 | n nd
1
d | nd
1
d | d1 | n
n
dd1 |
n
dd1 |
n
d
n
d1d |
1,d1 = n
0,d1 < n
§３,11 反演
,?”：设（ M2） 成立。
∑ g (d ) = ∑ g (d )
= ∑ ∑μ( d ) f ( d1 ) =∑μ( d ) f ( d1 )
= ∑ f ( d1 ) ∑ μ( d )
= ∑μ( d ) = ∑μ( d ) =
= f ( n )
d | n
d | n
d | n
n
dd1 |
n
d1d |
n
d1d |
n
d1d | d1 | n
dd1 | n
1,d1 = n
0,d1 < n
§３,11 反演例 圆排列问题设 a1a2···a n 是一个 圆排列,即 a2a3···a na1,··,
ana1 ···a n－ 1,看作是相同的。为了加以区别，
必要时把原先的排列称为 线排列 。一个圆排列在 n 个位置短开形成的 n 个线排列在元素可重复的情况下，未必都不相同。
例如,d｜ n时，由不重复的 a1a2 ···a d重复 n ／ d次构成的圆排列
§３,11 反演
( a1a2 ···a d ) ·· ( a1a2 ···a d )
n d 组只能形成 d 个不同的线排列。
若一个圆排列可由一个长度为 k 的线排列重复若干次形成，则这样的 k 中最小者成为该圆排列的周期 。一个圆排列中元素的个数（
重复出现的按其重复次数计）称为它的 长度
§３,11 反演设集合｛ 1,2,··,m｝ 中元素形成的长度与周期都是 d 的圆排列的个数为 M(d)。
设 n 是一给定的正整数。
若 d ｜ n,每个长度与周期都是 d的圆排列可在 d 个位置上断开，重复 n / d 次形成 d个长度为 n 的可重排列。因此有
∑ d M( d ) = mn 由 Mǒbíus反演定理
n M(n) = ∑ μ( d ) m
故 M( n ) = ∑ μ( d ) m
d｜ n
d｜ n
d｜ n
n
d
n
d
§３,11 反演设长度为 n 的圆排列的个数为 T( n ),则
T( n ) ＝ ∑ M( d )
d｜ n
例 m = { 1,2 },n = 7 则
M ( 7 ) = ( 27－ 2 ) = 18
T ( 7 ) = ∑ M( d ) = M (1 ) + M ( 7) = 20
d｜ 7
1
7
§３,7 鸽巢原理之一鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即
“若有 n个 鸽子巢,n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”
例１ 367人中至少有２人的生日相同。
例２ 10双手套中任取 11只，其中至少有两只是完整配对的。
例３ 参加一会议的人中至少有２人认识的别的参加者的人数相等。
§３,7 鸽巢原理之一例４ 从 1到 2n的正整数中任取 n+1个，则这 n+1个数中，至少有一对数，其中一个是另一个的倍数。
证 设 n+1个数是 a1,a2,··,an+1。 每个数去掉一切 2的因子，直至剩下一个奇数为止。
组成序列 r1,r2,,··,rn+1。 这 n+1个数仍在［
1,2n]中，且都是奇数。而 [1,2n]中只有 n个奇数,故必有 ri = rj = r,则 ai = 2αi r,aj = 2αj r
若 αi＞ αj,则 ai 是 aj 的倍数。
§３,7 鸽巢原理之一例５ 设 a1,a2,··,am是正整数序列，则至少存在 k和 l,1≤k≤ l≤m,使得和
ak + ak+1 + ·· + al 是 m的倍数。
证 设 Sk = ∑ai,Sh≡ rh mod m 0≤rh≤m-1
h = 1,2,··,m,若存在 l,Sl≡0 mod m 则命题成立．否则,1≤rh≤m-1,但 h = 1,2,
··,m,由鸽巢原理，故存在 rk = rh,即
Sk≡ Sh,不妨设 h ＞ k,则
Sh－ Sk = ak+1 + ak+2 +… + a h ≡0 mod m
i=1
h
§３,7 鸽巢原理之一例６ 设 a1,a2,a3为任意３个整数,b1b2b3
为 a1,a2,a3的任一排列，则 a1－ b1,a2－ b2,
a3－ b3中至少有一个是偶数．
证 由鸽巢原理,a1,a2,a3必有两个同奇偶．设这３个数被２除的余数为 xxy,于是 b1,b2,b3中被２除的余数有２个 x,一个
y,这样 a1－ b1,a2－ b2,a3－ b3被２除的余数必有一个为０．
§３,7 鸽巢原理之一例７ 设 a1,a2,··,a100是由 1和２组成的序列,已知从其任一数开始的顺序 10个数的和不超过 16．即
ai + ai+1 +… + a i+9 ≤16,1≤ i ≤91
则至少存在 h 和 k,k > h,使得
ah + ah+1 +… + a k = 39
证 令 Sj = ∑ai,j =1,2,…,100 显然
S1<S2<…<S 100,且 S100 = (a1 + … +a 10)
+ (a11 + … +a 20)+… + (a 91 + … +a 100)
i =1
j
§３,7 鸽巢原理之一根据假定有 S100≤10× 16 = 160
作序列 S1,S2,…,S 100,S1 +39,…,S 100+39,
共 200项．其中最大项 S100+39≤160+39
由鸽巢原理，必有两项相等．而且必是前段中某项与后段中某项相等．设
Sk = Sh + 39,k>h Sk－ Sh =39 即
ah + ah+1 +… + a k = 39
§３,8 鸽巢原理之二鸽巢原理二 m1,m2,…,m n都是正整数，
并有 m1 + m2 +… +m n－ n + 1个鸽子住进 n个鸽巢，则至少对某个 i 有 第 i 个巢中至少有
mi个鸽子,i = 1,2,…,n,
上一小节的鸽巢原理一是这一原理的特殊情况，即 m1 = m2 = … = m n= 2，
m1 + m2 +… +m n－ n + 1 = n + 1
如若不然，则对任一 i,都有第 i 个巢中的鸽子数 ≤mi－ 1 则
§３,8 鸽巢原理之二鸽子总数 ≤ m1 + m2 +… +m n－ n,
与假设相矛盾．
推论１ m只鸽子进 n个巢,至少有一个巢里有 「 － |只鸽子,nm
推论２ n(m－ 1) + 1只鸽子进 n个巢，至少有一个巢内至少有 m只鸽子．
推论３ 若 m1,m2,…,m n是正整数，且
> r－ 1,则 m1,…,m n至少有一个不小于 r
m1 + … +m n
n
§３,8 鸽巢原理之二例 设 A= a1a2···a 20是 10个 0和 10个 1 组成的
２进制数,B=b1b2···b 20是任意的２进制数．
C = b1b2···b 20 b1b2···b 20 = C1C2···C 40,则存在某个 i,1≤ i ≤20,使得
CiCi+1···C i+19与 a1a2···a 20至少有 10位对应相等．
…..,…...
...,..,..,..
A B
C
第 i 格 第 i +19格
1 2 ······· 19 20 1 2 ······ 19 20
1 2 ······ 19 20 1 ····· 19 20
§３,8 鸽巢原理之二证 在 C = C1C2···C 40中，当 i 遍历 1,2,…,
20时，每一个 bj历遍 a1,a2,…,a 20,因 A中有 10个 0和 10个 1，每一个 bj都有 10位次对应相等．从而当 i历遍 1,…,20 时，共有
10 · 20=200位次对应相等．故对每个 i平均有 200 20 = 10位相等，因而对某个 i 至少有 10位对应相等．
§３,8 鸽巢原理之二定理 若序列 S ={ a1,a2,…,a mn+1}中的各数是不等的,m,n 是正整数，则 S有一长度为 m+1的严格增子序列或长度为 n+1的减子序列，而且 S有一长度为 m+1的减子序列或长度为 n+1的增子序列．
证１ 由 S中的每个 ai 向后选取最长增子序列，设其长度为 li,从而得序列
L = { l1,l2,…,l mn+1 },若存在 lk≥m+1
则结论成立．
§３,8 鸽巢原理之二否则所有的 li ∈ [ 1,m],其中必有
「 | = n+1个相等．
设 li1 = li2 = ·· = lin= lin+1 不妨设 i1<i2< ·· <in+1
应有 ai1 > ai2 > ·· > ain+1,即有一长度为
n+1的减子列．
否则 不妨设 ai1 < ai2,则有
li1 > li2,矛盾．
mn+1
m
§３,8 鸽巢原理之二证２ 从 ai 向后取最长增子列及减子列，设其长度分别为 li,l’i,
若任意 i,都有 li ∈ [ 1,m],l’i∈ ［１,n］,
不超过 mn种对．则存在 j <k,( lj,l’j ) = ( lk,l’k )
若 aj <ak,则 lj >lk，
若 aj >ak,则 l’j >l’k,矛盾．
§３,8 鸽巢原理之二例 将 [ 1,65 ]划分为４个子集，必有一个子集中有一数是同子集中的两数之差．
证 用反证法．设次命题不真．即存在划分 P1∪ P2∪ P3∪ P4＝ [ 1,65 ],Pi
中不存在一个数是 Pi中两数之差,i=1,2,3,4
因 = 17，故有一子集，其中至少有 17
个数，设这 17个数从小到大为 a1,…,a 17,
不妨设 A={a1,…,a 17 } P1。
令 bi－ 1= ai－ a1,i = 2,···,17。
65
4
§３,8 鸽巢原理之二设 B＝｛ b1,··,b16},B [ 1,65 ]。
由反证法假设 B∩P1 = ф。 因而
B ( P2∪ P3∪ P4 )。
因为 ＝ 6，不妨设 {b1,··,b6} P2,
令 Ci－ 1=bi－ b1,I = 2,···,6
设 C＝ { C1,··,C5 },C [ 1,65 ]
由反证法假设 C∩( P1∪ P2 ) =ф,故有
C (P3∪ P4 )
因为 ＝ 3，不妨设 {C1,C2,C3 } P3
16
3
5
2
§３,8 鸽巢原理之二令 di－ 1= Ci－ C1,I = 2,3
设 D＝ { d1,d2 },D [ 1,65]。
由反证法假设 D∩( P1∪ P2∪ P3 )=ф,因而
D P4 。
由反证法假设
d2－ d1∈ P1∪ P2∪ P3 且 d2－ d1∈ P4,
故 d2－ d1 ∈ [ 1,65 ],但显然
d2－ d1 ∈ [ 1,65 ]，
矛盾。
§３,9 Ramsey 问题
１,Ramsey问题
Ramsey问题可以看成是鸽巢原理的推广．下面举例说明 Ramsey问题．
例 6 个人中至少存在３人相互认识或者相互不认识．
证 这个问题与 K6的边２着色存在同色三角形等价．假定用红蓝着色,
§３,9 Ramsey 问题设 K6的顶点集为 {v1,v2,··,v6 },dr(v)表示与 顶点 v 关联的红色边的条数,db(v)表示与 v 关联的蓝色边的条数．在 K6 中，有
dr(v)＋ db(v)＝５,由鸽巢原理可知，至少有３条边同色．
现将证明过程用判断树表示如下：
§３,9 Ramsey 问题
dr(v1)≥3?
db(v1)≥3 设 (v1v2) (v1v3) (v1v4)为红边设 (v1v2) (v1v3) (v1v4)为蓝边
△ v2v3v4是红△?
△ v2v3v4是蓝△?
设 ( v2v3 )是蓝边设 ( v2v3 )是红边
△ v1v2v3是蓝△
△ v1v2v3是红△√
√
YN
N
N
Y
Y
§３,9 Ramsey 问题
２．若干推论
( a ) K6的边用红蓝任意着色，则至少有两个同色的三角形．
证 由前定理知，有同色三角形，不妨设
△ v1v2v3是红色三角形可由如下判断树证明．
§３,9 Ramsey 问题
△ v1v4v5是蓝△
设 (v4v5)为蓝边
△ v4v5v6是红△?
设 (v1v4) (v1v5) (v1v6)为蓝边
db(v1)≥3
dr(v1)≥3? 设 (v
1v4)为红边
(v4v2) (v4v3) 为蓝边?
设 (v4v2)为红边 db(v4)≥3?
△ v1v2v4是红△ dr(v4)≥3
设 (v4v5)为蓝边(v4v5) (v4v6) 为红边
△ v2v3v5是红△?
设 (v2v5)为蓝边
△ v2v4v5是蓝△△ v
4v5v6是红△
△ v1v5v6是蓝△?
设 (v5v6)为红边 √
√
√
y
y
y
yy
y
n
n
n
n n
§３,9 Ramsey 问题
( b ) K9 的边红蓝两色任意着色，则必有红 K4或蓝色三角形 (蓝 K4或红色三角形 )．
证 设９个顶点为 v1,v2,··,v9,对９个顶点的完全图的边的红、蓝２着色图中，
必然存在 vi,使得 dr(vi)≠3,否则，
红边数＝ ∑ dr(vi)＝,这是不可能的．
不妨设 dr(v1)≠3,可得如下判断树证明结论．
1
2
27
2
§３,9 Ramsey 问题
dr(v1)≥4?
db(v1)≥6 设 (v1v2) (v1v3) (v1v4)(v1v5)是 4红边设 (v1v2) ·· (v1v7)是 6条蓝边
K4(v2v3v4v5)是蓝 K4?
K6(v2···v 7)中有红 △?
设 (v2v3)是红边
△ v1v2v3是红△
设△ v2v3v4是红△
K4(v2v3v4v5)是蓝 K4
√
√Y
Y
YN
N
N
§３,9 Ramsey 问题
∴ K9的边红、蓝２着色，必有红色三角形或蓝色 K4．
同理可证 K9的红、蓝２着色，必有蓝色三角形或红色 K4,
(红△ ∨ 蓝 K4) ∧ (蓝 △ ∨ 红 K4)
＝ 存在同色 K4或红△及蓝 △
＝同色 K4 ∨ (红△ ∧ 蓝△ )
§３,9 Ramsey 问题
( c ) K18的边红，蓝２着色，存在红 K4
或蓝 K4,
证 设 18个顶点为 v1,v2,··,v18,从 v1引出的 17条边至少有９条是同色的，不妨先假定为红色．从而可得下面的判断树证明命题．
§３,9 Ramsey 问题
dr(v1)≥9
db(v1)≥9 设 (v1v2) ·· (v1v10)是 红边
K9(v2 ·· v10)中有同色 K4
或红△加蓝△
K10( v1v2 ···v 10)中有同色 K4
设 (v1v2) ·· (v1v10)是 蓝边
K9(v2 ·· v10)中有同色 K4
或红△加蓝△
K10( v1v2 ···v 10)中有同色 K4
YN
§３,10 Ramsey数将上一节的问题一般化：给定一对正整数
a,b,存在一个最小的正整数 r,对 r 个顶点的完全图的边任意红、蓝２着色，存在
a 个顶点的红边完全图或 b 个顶点的 蓝边完全图。 记为 r ( a,b )。 比如：
r ( 3,3 )＝ 6,r ( 3,4 )＝ 9，
r ( 4,4 )＝ 18
１,Ramsey数的简单性质
§３,10 Ramsey数定理 r ( a,b )＝ r ( b,a )； r ( a,2 )＝ a
证 K r(a,b )的边红蓝２着色，有红 Ka或蓝
Kb,将红蓝２色对换，就有红 Kb或蓝 Ka．
设 r ( a,b )＝ r,Kr的边任意红蓝２着色红蓝互换后仍是 Kr的边的２着色，由 r(a,b)
的定义，有红 Ka或蓝 Kb,再红蓝对换恢复原图有红 Kb或蓝 Ka．
§３,10 Ramsey数例 K9的边任意红蓝２着色，有红三角形或蓝 K4,红蓝对换后，仍有红三角形或蓝
K4,再对换一次，回到原来的着色方案，
有蓝三角形或红 K4．
第二个等式容易看出,Ka红蓝２着色若不全红 (红 Ka),则必有一条蓝边．
§３,10 Ramsey数定理 当 a,b ≥２ 时，
r ( a,b )≤ r ( a － 1,b )＋ r ( a,b－ 1 )
证 对 r ( a － 1,b )＋ r ( a,b－ 1 ) 个顶点的完全图红蓝２着色．任取其中一点 v，
有
dr(v) + db(v) = r( a － 1,b ) + r( a,b－ 1 )－ 1
从而可得判断树如下．
§３,10 Ramsey数
dr(v)≥r (a－ 1,b)?
db(v)≥r (a,b － 1 )
与 v 以红边相连的 r(a－ 1,b)个顶点的完全图中有一个红 Ka－ 1?
有蓝 Kb
红 Ka或蓝 Kb
V与 这 a－ 1个点构成红 Ka
N
Y
Y
N
§３,10 Ramsey数推论 r (a,b ) ≤ ( )a + b－ 2a－ 1
证 r ( a,b )≤ r ( a － 1,b )＋ r ( a,b－ 1 )
≤( )＋ ( )
＝ ( ) a + b－ 2a－ 1
a + b－ 3
a－ 2
a + b－ 3
a－ 1
§３,10 Ramsey数定理 若 a ≥３,则 r ( a,a) > 2
a
2
证 Kn有 ( )条边，对边红蓝２着色有
2 种方案．其中同色 Ka的 方案数不超过
n
2n
2( )
a
2( )( ) · 2 · 2
n
2( )－n
2
Ka的个数可红可蓝可任意着色边数同色边数
§３,10 Ramsey数这是一个上界,Kn中含 Ka的方案被重复计数．若取 n足够小，便得
a
2( )( ) · 2
n
a( )－ + 1 n
a < 2
n
2( )
则必有 Kn的一个２着色方案中无同色 Ka，
有 r ( a,a)定义可知,r (a,a)>n
即 ( ) < 2 n= 2 时
( ) < = 2 = 2 · 2
≤2
a
2( )－１n
a
a
2
a
2( )－ 1
n
a
na
2a－ 1
－ a+1a
2
2
a
2( )－ 1 － +2
a
2
§３,10 Ramsey数所以 r (a,a) > 2
a
2
§３,10 Ramsey数
２,Ramsey数的推广若将２着色改为 k 着色，同色 Ka或同色
Kb改为同色 Ka i i = 1,2,…,k,即得 Ramsey
数 r ( a1,a2,…,a k),对于给定的正整数 ai
( ai ≥2),i = 1,2,…,k,存在最小正整数
r,对 Kr的边用 k中颜色 Ci ( i = 1,2,…,k)
任意着色．则存在 i,出现全 Ci色的 Ka i,(
即边都是 Ci色的 ai个顶点的完全图）；
这个最小正整数 r 用 r (a1,…,a k)表示．
§３,10 Ramsey数有 r (a1,a2,…,a k)≤ r ( a1,r ( a2,…,a k) )
证 设 r ( a1,r ( a2,…,a k) ) = p，
r (a2,…,a k) = q；
对 Kp的边２着色，出现第一色 Ka1或第二色 Kq，
用 n－ 1中色对 Kq的边着色，至少出现 i色的 ai点完全图,i = 2,…,n,对 Kp的边 n 着色，将后
n－ 1中色看作同一种色，出现第一色 Ka 1或另一色 (n－ 1种色看作另一色）的 Kq,即出现 第 I 色
Ka i,I = 2,…,n,故 r (a1,a2,…,a k)≤ p
§３,10 Ramsey数例 r ( 3,3,3) = 17
证 设三色为 r,b,g,则对 K17的任一顶点 v
有 dr(v) + db(v) + dg(v) = 16； 因 =6,
故任一顶点与其他顶点的连线中，至少有
６条同色．不妨设 dr(v1)≥6,(v1v2)…(v 1v7)
都是红边．
从而可得如下判断树．
16
3
§３,10 Ramsey数
K6(v2···v 7)中无红边?
K6(v2···v 7)中有红边
K6(v2···v 7)中蓝绿２着色有蓝 K3或绿 K3
设 (v2v3)为红边
△ v1v2v3是红色的原题得证．
YN
