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

§32容斥原理 令:M为修数学的学生集合; P为修物理的学生集合; C为修化学的学生集合 M=170f=13(4=120M∩F=45 M∩d=20P∩d=2nP∩(=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容斥原理 MUPU=+1+(M∩M M∩P∩d+M∩P∩d =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 容斥原理

§32容斥原理 同理可推出: ∪ BUCUD=4+|6+d+D-AB A∩q-|BdAD+|ABd +|AB∩D+| BCOD-ABCAD 利用数学归纳法可得一般的定理

同理可推出： 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容斥原理 定理设￠(nk)是[1,n]的所有k 子集的集合,则 A1=(-1)1 证对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容斥原理 心A=心4U4 =心4+4|-∪4n4 i=1 14|+14-(4n4) ∑(-1)∑n4+4-2()∑(4n∩4 (n-1,k) I∈￠(n-1k

§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