般感 容斥原理的证明 。公式：UA,=S,-S2+S-+(-1)1S4++(-1)Sn 。我们证明在上述公式中： 。并集中的元素在右边式子中恰好被计数次 ●设并集中对象a出现在m个集合中 。则它在在S1中被计数m次，在S2中被计数C次 。以n=4,m=3为例： IS+IS2+IS3l+IS4l -(ISOS2l+ISOS3l+ISOS4l+IS20S3l+IS20S4l+IS3OS4l) +(IS1∩S2nS3+lS1∩S2nS4+lS1∩S3nS4+S2nS3∩S4) -IS]0S20S30S4l 容斥原理的证明  公式：  我们证明在上述公式中:  并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合中  则它在在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 |S1 |+ |S2 |+ |S3 |+ |S4 | - (|S1S2 |+|S1S3 |+|S1S4 |+|S2S3 |+|S2S4 |+|S3S4 |) + (|S1S2S3 |+|S1S2S4 |+|S1S3S4 |+|S2S3S4 |) - |S1S2S3S4 |