容斥原理在计数时容斥,为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 核心:(1)两个集合的容斥关系公式: A+B=A∪B+A∩B(2)三个集合的容斥关系公式: A+B+C=A∪B∪C+A∩B+B∩C+C∩A-A∩B∩C
A交B)的补==(A的补)并(B的补)(A并B)的补==(A的补)交(B的补)补==取补集并==取并集交==取交集括号表示顺序n(A1∪A2∪。。。∪Am)=∑n(Ai)1≤i≤m-∑n(Ai∩Aj)1≤i≤j≤m+∑n(Ai∩Aj∩Ak)-…+(-1)m-1n(A1∩A2…∩Am)1≤I,j,k≤m注:m-1是-1的指数这种公式的形式是很复杂的重在理解理解了就很好用了甚至不用背就可以自己写出公式来解题的时候就得心应手不过这个公式已经超出了高中的范畴了高中最多也就讨论m=3的情形用语言表达似乎很困难就是说求几个集合的并集可以先把他们统统加起来但是这样做有些地方就多加了那么就要减掉一些(由公式来判断什么需要减去)但是这样做有些地方就多减了那么就要加上一些(由公式来判断什么需要加上)。
如此重复继续下去最后得到的结果就是这几个集合的并集举个例子吧集合a1,a2,a3a1={1,2,3,4}a2={2,3,4,5}a3={3,4,5,1}求三个集合的并集按照这个公式∑n(Ai)1≤i≤m=a1+a2+a3={1,2,3,4,2,3,4,5,3,4,5,1}∑n(Ai∩Aj)1≤i≤j≤m=(a1∩a2+a2∩a3+a3∩a1)={2,3,4}+{3,4,5}+{3,4,1}∑n(Ai∩Aj∩Ak)1≤i≤j≤m=(a1∩a2∩a3)={3,4}代入公式三个集合的并集=a1+a2+a3-(a1∩a2+a2∩a3+a3∩a1)+(a1∩a2∩a3)={1,2,3,4,2,3,4,5,3,4,5,1}-({2,3,4}+{3,4,5}+{3,4,1})+({3,4})={1,2,3,4,5}以上就是这个公式的具体应用我的表达不是很规范但是这个公式的方法就是这样的重在理解。