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

§3,2容斥原理 但(A4∪A2∪.J2)∩A =(AA1)(A2∩A) (Aa1∩A1)

1 2 1 1 2 ... ) ( ) ( )... ), n n n n n A A A A A A A A A           n-1 但 ( (A §3.2 容斥原理

§3,2容斥原理 (4∪4U.UJA)A =4∩A)U(424.U(A2104) =|404+|A24+…14104 4∩404-A43∩A

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

§32容斥原理 A4204;4++(y4∩4…4 ∑44∑>444+ i=1 i>i +(-y|4041…4

2 1 1 2 1 1 1 1 1 2 ... ( 1) ... ... ( 1) ... n n n n n n n i n i j n i i j i n n A A A A A A A A A A A A A A                              §3.2 容斥原理

§3,2容斥原理 A1∪A2U…UAn1∪A ∑∑|A1nA A∩A∩A i=1 j>i k>j +(-1)2-|4A2n…An

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

§3,2容斥原理 又A=N 其中N是集合U的元素个数,即不属于 A的元素个数等于集合的仝体减去属于 A的元素的个数。一般有

又 A  N  A , 其中N是集合U的元素个数，即不属于 A的元素个数等于集合的全体减去属于 A的元素的个数。一般有： §3.2 容斥原理