§3.2容斥原理 14|+(-∑.n4 k=2 I∈￠(n-1,k)e +∑(-1)-1 ∩4∩A I∈￠(n-1k-1)∈ ∑(-1)41∑∩4 k=1 I∈￠(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…,A是有限集合,则 A1∪A2∪.∪A A 14∩A A1∩A,∩Ak i=1 j>i k>j +(-1)”41∩A2∩…∩A,(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(+||-NU下 设n-1时成立,即有:
证：用数学归纳法证明。 已知 n=2时有 A A A A A A 1 2 1 2 1 2 = + − 设 n-1时成立，即有： §3.2 容斥原理
§32容斥原理 A∪A2∪.∪An1 ∑|4S∑A∩4 ∑|A1∩A,∩A i=1 j>i k>j +(-1)|A1∩A2….∩An1
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∩平∩∩N+下 =(∩∩“∩x)∩ 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 容斥原理