PDF《应用组合数学》

第9讲 容斥原理 张坤龙 zhangkl@tju.

edu.cn 应用组合数学 目录 集合N, n个属性 ? 容斥原理 C 求具有n个属性之一(并集)的元素的个数 C 求不具有n个属性中任何一个(交集)的元素的个数 ? 广义容斥原理 C 求恰好具有m个属性的元素的个数 容斥原理 ? 并集的计数 ? 交集的计数 ? 容斥原理的应用 C 有禁区的排列 两个集合的并集 [定理1] |A∪B|=|A|+|B|-|A∩B| ? ?

3 /

20 U B A A B I [例1] 求不超过20的正整数中2或3的倍数的个数 解:令A为2的倍数集合,B为3的倍数集合 |A|= =10 |B|= =6 |A∪B|=|A|+|B|-|A∩B|=13 |A∩B|= =3 ? ?

2 /

20 ? ?

6 /

20 } [例2] 一个学校只有三门课程:数学、物理、化学.已知修 这三门课的学生分别有

170、

130、120人;

同时修数学 物理两门课的学生45人;

同时修数学化学的20人;

同时 修物理化学的22人.同时修三门课程的3人.问这学校共 有多少学生,假设每个学生至少修一门课? 解:|M∪P ∪C |=170+130+120-45-20-22+3=336 三个集合的并集 [定理2] |A∪B ∪C |=|A|+|B|+|C| -|A∩B|-|A∩C|-|B∩C| +|A∩B∩C| U B A A B I C IC A IC B I IC B A 多个集合的并集 证明:数学归纳法 I I I I I I U U U L L L L | | )

1 ( | | | | | | | | , , , 3] [

2 1

1 1

1 1

2 1

2 1 n n n i i j j k k j i n i i j j i n i i n n A A A A A A A A A A A A A A A ? = >

>

= >

= ? + ? + ? = ∑∑∑ ∑∑ ∑ 是有限集合,则设定理 De Morgan定理 [定理4] 若A,B是U的子集,则UIIUBABABABA==[定理5] 若A1,A2,…An是U的子集,则UUUIIIIIIUUULLLLnnnnAAAAAAAAAAAA21212121==Sylvester公式 I I I I I I I I I L L L L | | )

1 ( | | | | | | | | | | , , , 6] [

2 1

1 1

1 2

1 2

1 n n n i i j j k k j i n i i j j i n i i n n A A A A A A A A A N A A A A A A i N ? + + ? + ? = ∑∑∑ ∑∑ ∑ = >

>

= >

= ,则 的集合 和具有性质 给定集合 定理 有限制的排列 [例3] 求a,b,c,d,e,f六个字母的全排列中不允许出现 ace和df图象的排列数. 解:设A为ace作为一个元素出现的排列集,B为df 作为一个元素出现的排列集,则|N|=6! |A|=4! |B|=5! |A∩B|=3!

582 !

3 ) !

4 !

5 ( !

6 | | = + + ? = ? ? ? ? ? IB A [例4] 4个x、3个y、2个z的全排列中,求不出现xxxx、 yyy、zz图象的排列数. 解:所有出现xxxx图象的排列集合记为A1,出现yyy图 象的排列集合记为A2,出现zz图象的排列集合记为 A3,则871

6 - 30)

20 (12 280)

105 (60 -

1260 )

1 ,

1 ,

1 ;

3 ( - ] )

1 ,

1 ,

4 ;

6 ( )

1 ,

3 ,

1 ;

5 ( )

2 ,

1 ,

1 ;

4 ( [ )]

1 ,

3 ,

4 ;

8 ( )

2 ,

1 ,

4 ;

7 ( )

2 ,

3 ,

1 ;

6 ( [ )

2 ,

3 ,

4 ;

9 ( | | |) | | | | (| |) | | | | (| | | | |

3 2

1 3

2 3

1 2

1 3

2 1

3 2

1 = + + + + + = + + + + + ? = ? + + + + + ? = P P P P P P P P A A A A A A A A A A A A N A A A I I I I I I I Eratosthenes筛法 [例5] 求不超过120的素数的个数. 解:不超过120的合数必然是

2、

3、

5、7的倍数, 且不超过120的合数的因子不可能都超过11.设Ai 为不超过120的数i的倍数集,i=2,3,5,7. I I I I I I I I I I I I I I I I I I I I | | |) | | | | | | (| |) | | | | | | | | | | (| |) | | | | | | (| | | | |

7 5

3 2

7 5

3 7

5 2

7 3

2 5

3 2

7 5

7 3

5 3

7 2

5 2

3 2

7 5

3 2

7 5

3 2 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 N A A A A + + + + ? + + + + + + + + + ? =