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

§3.2容斥原理 A1|+∑(-1) A:+A 1k=21∈￠(1l)e k-1 A,∩A I∈￠(n-1,k-1)le k-1 A k=1 ￠(nk) 此定理也可表示为:

§3.2 容斥原理 1 1 1 1 2 1 2 1 1 ( 1) ( 1) ( 1) n n k i i n i k i I n k i n k i I n k i k i I A A A A A A                                I∈￠(n,k) I∈￠(n-1,k-1) I∈￠(n-1,k) 此定理也可表示为：

§32容斥原理 定理:设AA2…,A1是有限集合,则 A1∪A2∪.∪A ∑|4,∑∑|4,∩ ∑|A:nA,∩Ak 1 j>i k>j +(-1)|410A20…∩An|(4)

定理：设 1, 2 ,..., A A An 是有限集合，则 1 2 1 1 1 1 2 . . . . . . ( 1 ) . . . n n n i i j i i j i k n j n A A A A A A A A A A A                         n i i = 1 j > i k > j + A (4) §3.2 容斥原理

§32容斥原理 证:用数学归纳法证明 已知n=2时有 N∩平|=+平|下∪平 设n-1时成立,即有:

证：用数学归纳法证明。 已知 n=2时有 A1  A2  A1  A2  A1  A2 设 n-1时成立，即有： §§33..22 容容斥斥原原理理

§32容斥原理 A1UA2∪….∪An A,∩A ∑|A1∩A,∩AA +(-1)|A1∩A20…An=1

1 2 1 1 1 1 1 1 2 1 ... ... ( 1) ... n n n i i j i i j i j k n n A A A A A A A A A A A                            n - 1 i i = 1 j > i k > j + A §3.2 容斥原理

§32容斥原理 (∩平∩∩) N∩平∩“∩w+ =(N∩平∩∩2)∩N 于∩甲∩¨∩∩

1 2 1 1 2 1 1 2 1 1 2 1 ... ( ... ) ... ( ... ) n n n n n n n n A A A A A A A A A A A A A A A A                         §3.2 容斥原理