容斥原理的证明 公式:∪A=S-S2+s-…+(-)S++(- n-1 口我们证明并集中的元素在右边式子中恰好被计数1次 口设并集中对象a出现在m个集合A中 口则它在在S1中被计数m次,在S中被计数C次 口将上述分析带入计数公式可得a在右式中计数次数 四-C2++(-1)Cm+…+(-1)Cm 该计算式值为1,因为当x=1时下式为0 (1-x)"=1-C1xC2x2+…+(-1)Ckx+…+(-1)“Cmx 口a恰好被计数1次容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合Ai中  则它在在S1中被计数m 次，在Sk中被计数 次  将上述分析带入计数公式可得a在右式中计数次数： ◼ 该计算式值为1，因为当x=1时下式为0：  a恰好被计数1次 n n k k S S S S S -1 -1 1 2 3 n i 1 i A = - + -...+ (−1) +...+ (−1) =  m Ck m m m m k m m k C C C C 1 1 1 2 ... ( 1) ... ( 1) − − − + + − + + − m m m m k m k m m m k (1 x) 1 C x C x ... ( 1) C x ... ( 1) C x 2 − = − 1 + 2 + + − + + −