在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。
![](https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D592/sign=3ef1ffbf1fd8bc3ec20806c3b08aa6c8/0ff41bd5ad6eddc403aafe7e3fdbb6fd536633e1.jpg)
也可表示为
设S为有限集,
,则
![](https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D192/sign=2ee170943812b31bc36cc920b4193674/3c6d55fbb2fb4316304e96a921a4462308f7d394.jpg)
![](https://gss0.bdstatic.com/94o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D384/sign=79d25d2838dbb6fd215be32e3d25aba6/8b82b9014a90f6035b8575943812b31bb051ed28.jpg)
由于
![](https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D316/sign=5cbe5cdd9b2397ddd2799e056f82b216/ae51f3deb48f8c54ad68a01530292df5e0fe7f54.jpg)
![](https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D316/sign=4d3f58fd9a52982201333fc2e1ca7b3b/faf2b2119313b07ec19c343206d7912397dd8ce2.jpg)
所以
![](https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D359/sign=f42224034136acaf5de090f945d88d03/e1fe9925bc315c600b650cd587b1cb1349547713.jpg)
两个集合的容斥关系公式:A∪B =|A∪B| = |A|+|B| - |A∩B |(∩:重合的部分)
三个集合的容斥关系公式:|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|
个人体会:总结起来就是如果要求s中不具有1-n性质的元素就是等于S-一个元素的所有和+二个元素的所有和-三个元素的所有和(都是交集);
比如看欧拉定理吧,与N互素,就是找出N的素数因子,然后求满足全都不包括这些元素性质的就可以了;打个比方:10,素数因子2,5
则A(1)=5{2,4,6,8,10},A(2)=1{5} 则所求=10-6+0=4。不过后面那个最简式的得来真是推不下去了,脑阔痛
![](https://images2017.cnblogs.com/blog/1147305/201708/1147305-20170802150334771-1547839528.png)