容斥原理

oyangningtao

有三个集合A、B、C。记这三个集合中元素的个数分别为|A|、|B|、|C|。记A与B的交集为A∩B，它的元素的个数为|A∩B|；同理，B与C的交集为B∩C，它的元素的个数为|B∩C|；C与A的交集为C∩A，它的元素的个数为|C∩A|。再记A、B、C三个集合的交集为A∩B∩C，它的元素的个数为|A∩B∩C|。那么，A、B、C的并集A∪B∪C中元素的个数|A∪B∪C|为

|A∪B∪C|

= |A| + |B| + |C|

- |A∩B| - |B∩C| - |C∩A|

+ |A∩B∩C|

证明：

我们利用文氏图进行证明。

即

下面是一道典型的三集合容斥原理的应用题。

问题：1到1000这1000个正整数中，能够被3整除，或能够被5整除，或能够被7整除的数有多少个？

解答：

设1到1000这1000个正整数组成的集合为A。A中能被3整除的数有333个（3，6，9，…，999），它可这样求得：1000=333*3+1，其中的1为余数，它小于3。记这个能被3整除的数的集合为A3，它的元素的个数|A|=333。能被5整除的数有200个（5，10，15，…，995，1000），它可这样求得：1000=200*5。记这个能被5整除的数的集合为A5，它的元素的个数为|A|=200。能被7整除的数有142个（7，14，21，…，994），它可这样求得：1000=142*7+6。记这个能被7整除的数的集合为A7，它的元素的个数为|A|=142。

既能被3整除又能被5整除的数一定是能够被15整除的数，这是集合A3和A5的交集。记这个集合为A3∩A5，它的元素的个数可以这样求得：1000=66*15+10。所以

|A3∩A5|=66。

同理可得

|A3∩A7|=47（1000=47*21+13）；

|A5∩A7|=28（1000=28*35+20）。

既能被3整除，又能被5整除，还能被7整除的数的集合为集合A3、集合A5和集全A7的交集A3∩A5∩A7，它的元素的个数为

|A3∩A5∩A7|=9（（1000=9*105+55）

根据容斥原理，有

|A3∪A5∪A7|

= |A3|+|A5|+|A7|

- |A3∩A5| - |A3∩A7| - |A5∩A7|

+ |A3∩A5∩A7|

= 333+200+142-66-47-28+9

= 543

所以，1到1000这1000个正整数中，能够被3整除，或能够被5整除，或能够被7整除的数有543个。

转自：https://www.sohu.com/a/204271684_614593