容斥原理
定理 设￠(n,k)是［1,n］的所有k子集的集合, 则 n n |∪Ai | = ∑ (－1)k-1 ∑ | ∩ Ai | i=1
k=1
I∈￠(n,k) i∈I
证 对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有
§3.2
容斥原理
n n 1 i 1 n
A
i 1
500 500 A 166, B 100; 3 5 500 A B 33 15
§3.3
例
被3或5除尽的数的个数为
A B A B A B 166 100 33 233
例3 求由a,b,c,d四个字母构成的位
A1 A2 ... An 1 An Ai Ai A j
i 1 n i 1 j i n n
+ Ai A j Ak ...
i=1 j>i k>j n 1
( 1)
A1 A2 ... An
§3.2 容斥原理
又 A N A,
§3.2 容斥原理
A1 A2 ... An A1 A2 ... An 正确
则 A1 A2 ... An An 1 ( A1 ... An ) An 1 ( A1 A2 ... An An 1 A1 A2 ... An An 1 即定理对n+1也是正确的。
- Ai Aj Ak ...
i=1 j>i k>j n
n
(1) A1 A2 ... An (5) 容斥原理指的就是（4）和（5）式。
§3.3
例 §3 例
例1 求a,b,c,d,e,f六个字母的全排列
中不允许出现ace和df图象的排列数。 解：设A为ace作为一个元素出现的 排列集，B为 df作为一个元素出现的 排列集，A B 为同时出现ace、df的 排列数。
符号串中，a,b,c,d至少出现一次的符号 串数目。
§3.3
例
解：令A、B、C分别为n位符号串中 不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a， b，c，d四种符号中的一个，故不允许 n 出现a的n位符号串的个数应是 3 ，即
A B C 3
n n
A B AC C B 2

I∈￠(n,k)
A
iI
此定理也可表示为：
§3.2 容斥原理 定理：设 A1, A2 ,..., An 是有限集合，则
A A2 ... An 1

i 1 n
n
Ai Ai A j
i 1 j i
n
+ Ai A j Ak ...
i=1 j>i k>j n 1
§3.2 容斥原理
§2
定理：
容斥原理
最简单的计数问题是求有限集合A 和B的并的元素数目。显然有
A B A B A B (1)
即具有性质A或B的元素的个数等于具
§3.2 容斥原理
有性质A和B的元素个数。 U A A B
B
§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.3 例
.!3 B A ,!5 B ,!4 A
根据容斥原理，不出现ace和df的排列数 为：
B A
=6!- (5!+4!)+3!=582
§3.3
例
例2 求从1到500的整数中能被3或5
除尽的数的个数。 解： 令A为从1到500的整数中被3除 尽的数的集合，B为被5除尽的数的集合
(A A )
i n iI
I∈￠(n-1,k)
§3.2

容斥原理
n 1 k 1

i 1
n 1
Ai (1)
k 2 n
I∈￠(n-1,k)

A
iI
i
An
( 1) k 1
k 2
I∈￠(n-1,k-1)

A
iI i
i
An

(1)
k 1
n
k 1
§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 |
§3.1 容斥原理引论
第三章 容斥原理和鸽巢原理 §1 容斥原理引论
例 [1，20]中2或3的倍数的个数 [解] 2的倍数是：2，4，6，8，10， 12，14，16，18，20。 10个
§3.2 容斥原理
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} ,有
(a) A B A B
(b) A B A B
§3.2 容斥原理
证：(a)的证明。 设 ,则 x A B x A B 相当于 x A和 x B 同时成立，亦即
i 1 j i
n 1
+ Ai A j Ak ...
i=1 j>i k>j n
n-1
( 1)
A1 A2 ... An 1
n n
A 1 nA ... 2A 1A A ... A A
2 1
A ) 1 nA ... 2A 1A (
§3.2 容斥原理
An2 An1 An ... (1) A1 A2 ... An
n
Ai An Ai Aj An ...
i 1 i 1 j i
n 1
n 1
(1) A1 A2 ... An
n
§3.2 容斥原理
( 1)
A A2 ... An 1
(4)
§3.2 容斥原理 证：用数学归纳法证明。
已知 n=2时有
2
设 n-1时成立，即有：
A 1A 2A 1A 2A 1A
§3.2 容斥原理
A1 A2 ... An 1

i 1
n 1
Ai Ai A j
§3.2 容斥原理
DeMogan定理的推广：设 A1, A2 ,..., An是U的子集
则 (a)A1 A2 ... An A1 A2 ... An
证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定：
n
A ... 2A 1A nA ... 2A 1A)b(
其中N是集合U的元素个数，即不属于 A的元素个数等于集合的全体减去属于 A的元素的个数。一般有：
§3.2 容斥原理
A1 A2 ... An N A1 A2 ... An 1 An N Ai Ai Aj
i 1 i 1 j i n n
例
§3.2 容斥原理
令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；
M 170, P 130, C 120, M P 45 M C 20, P C 22, M P C 3
§3.2 容斥原理
M PC M P C M P M M C P C M P C 170 130 120 45 20 22 3 336
§3.3
例
A B C 1
a，b，c至少出现一次的n位符号串集 合即为 A B C
A B C 4 ( A B C ) ( A B
n
AC C B ) A B C 4 3 3 3 2 1
n n n
§3.3
例
例4。求不超过120的素数个数。 因 ，故不超过120的合数必 然是2、3、5、7的倍数，而且不超过 120的合数的因子不可能都超过11。 设 为不超过120的数 i 的倍数集， i =2，3，5，7。
A A B x A B
B A x
(1)
§3.2 容斥原理
反之，若 x A B, 即x A和x B 故 x A和x B.亦即x A B
x A B x A B (2)
由（1）和（2）得 x A B x A B (b)的证明和（a)类似，从略.
n
A
1 n
n
A ) 1 nA ... 2A 1A (
§3.2 容斥原理
§3.2 容斥原理
但 (A1 A2 ... An 1 ) An ( A1 An ) ( A2 An )... (A n-1 An ),