容斥原理的证明 公式:∪A +S3-…+(-1Sk+…+(-1) 口我们证明并集中的元素在右边式子中恰好被计数1次 口设并集中对象a出现在m个集合A中 口则它在在S1中被计数m次,在S2中被计数C次 ■以n=4,m=3为例 S1:|A1+1A2+A3+A4 S2:-(A1^A2+4A3+A1∩A4|+A2A3+A2A4+A9A4D) +(|A1A2A3|+|A1A2A4|+A1A3A4|+|AA3A4|) A,nA2nA3nA4l容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合Ai中  则它在在S1中被计数m 次，在S2中被计数 次 ◼ 以n=4，m=3为例： n n k k S S S S S -1 -1 1 2 3 n i 1 i A = - + -...+ (−1) +...+ (−1) =  m C2 |A1|+ |A2|+ |A3|+ |A4| - (|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|) + (|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|) - |A1A2A3A4| S1 ： S2 ： S3 ： S4 ：