§32容斥原理 DeMorgan定理的推广:设 A42,…,4,是的子集 则(a)A1∪A2U.UA1=A1∩A2…A2 (P)UUU=∩∩∩ 证明:只证(a)N=2时定理已证。 设定理对n是正确的,即假定:
DeMogan定理的推广：设 1, 2 ,..., A A A U n 是 的子集 2 1 2 ... ... 则 (a)A1 A A A A A n n = 2 1 2 ... ... (b)A1 A A A A A n n = 证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定： §3.2 容斥原理
§32容斥原理 A1∪A∪…An=A1∩A2…A,正确 A1UA2∪. UAUA=(AU…JA1)UA21 =(A4UA2U…UA1∩A1 =A1∩A21.An∩A1 即定理对n+1也是正确的
2 1 2 ... ... A1 A A A A A n n = 正确 2 1 1 2 1 2 1 1 1 1 ... ( ... ) ( ... ... n n n n n n n n A A A A A A A A A A A A A A + + + + = = = 1 则 A 即定理对n+1也是正确的。 §3.2 容斥原理
§32容斥原理 §2容斥原理 最简单的计数问题是求有限集合A 和B并的元素数目。显然有 定理: A∪B|=4+|B-A∩B(1) 即具有性质A或B的元素的个数等于具
§2 容斥原理 最简单的计数问题是求有限集合A 和B的并的元素数目。显然有 即具有性质A或B的元素的个数等于具 A B A B A B = + − (1) 定理： §3.2 容斥原理
§32容斥原理 有性质A和B的元素个数。 U A 40B B
有性质A和B的元素个数。 U A A B B §3.2 容斥原理
§32容斥原理 证若A∩B=(,则|A∪B|=|A|+|B A|=A∩(B∪B) =(A∩B)∪(AnB) =A∩B+A∩B|(1) 同理|B|=|B∩A|+|B∩A(2) A∪B|=(An(B∪B))∪(B∩(A∪A =(A∩B)∪(AnB)∪(B∩A)∪(B∩A) A∩B|+A∩B|+|B∩A|(3)
§3.2 容斥原理 证 若A∩B=φ，则 | A∪B |= |A| + |B| | A |＝| A ∩( B∪B) | ＝| (A∩B)∪(A∩B)| ＝| A∩B | + | A∩B | ( 1 ) 同理 | B | ＝| B∩A | + | B∩A | ( 2 ) | A∪B |＝|(A∩( B∪B))∪(B∩(A∪A))| ＝|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)| ＝| A∩B| + |A∩B | + | B∩A| ( 3 )