容斥原理的证明 ▣公式：UA=S,-S2+S,-+(-1)S++(-1)Sn i=1 口我们证明并集中的元素在右边式子中恰好被计数1次 口设并集中对象a出现在m个集合A中 则它在在S中被计数m次，在S2中被计数C2”次 口 ■以n=4,m=3为例： S1:1Al+1A21+1A3l+1Al S2: -(IA1∩A2I+|A1∩A3|+|A1∩A4|+|A2∩A3|+|A2∩A4I+|A3∩A4I) S3: +(IA1∩A2∩A3+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4) S4: -|A1∩A2∩A3∩A4容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数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 ：