清华大学：《组合数学》课程教学资源（PPT课件讲稿）第三章 容斥原理和鸽巢原理

§3,2容斥原理 令:M为修数学的学生集合 P为修物理的学生集合; C为修化学的学生集合; M=170=13.(=-120M∩F=45 Md=20P∩d=22P∩d=3

令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合； 170, 130, 120, 45 20, 22, 3 P C M P M C P C M P C             M §3.2 容斥原理

§32容斥原理 MUPd=M+2+M∩M MnGP∩d+ MnNg =170+130+120-45-20-22+3 =336 即学校学生数为336人

170 130 120 45 20 22 3 336 M P C P C M P M M C P C M P C                        M 即学校学生数为336人。 §3.2 容斥原理

§3,2容斥原理 同理可推出: AUBUCUD=A+B+C+D-An B A∩BdAD+A∩Bd ABD+B CD 利用数学归纳法可得一般的定理

同理可推出： 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 容斥原理

§3.2容斥原理 定理设￠(n,k是[1,n]的所有k 子集的集合,则 A|=已2(-1)-1ca合 证对n用归纳法。n=2时,等式成立。 假设对n-1,等式成立。对于n有

定理 设￠(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容斥原理 UA|=∪4U4 U4+14-04n4 U4+14-(4n4 ∑(-11∑n4+1A-∑()∑∩(4n∩4 I∈￠(n-1.)e I∈￠(n-1)

§3.2 容斥原理 1 i 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A ( ) ( 1) ( 1) ( ) n n i n i i n n i n i n i i n n i n i n i i n n k k i n i n k k i I A A A A A A A A A A A A A A                                             I∈￠(n-1,k) I∈￠(n-1,k) i∈I