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

§32容斥原理 但(A1∪A2∪.JUA2)A =(4A1)∪(A2∩A (An1∩An)

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

§32容斥原理 (4UAU.∪A2)A =(4∩4)儿(42∩A).U(4210A A4∩41+|42∩4|+…+1421∩41 A∩A2∩A|-1443∩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容斥原理 A42A141+…+(-1441…·4 ∑44∑∑444+ ●●● +(yA4^…A

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 容斥原理

§32容斥原理 A1∪A2∪…∪An-1∪An A4|-∑∑|A,∩A +2∑∑A1∩A,nA 1=1 j>i k>j +(-1)|A41∩A20…∩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 容斥原理

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

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