什么是容斥原理

花叶万年青2023-04-27  23

这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。

如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。

扩展资料

两个集合的容斥关系公式:A∪B =|A∪B| = |A|+|B| - |A∩B |(∩:重合的部分)

三个集合的容斥关系公式:|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|

简单来说要计算几个集合并集的大小,要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。

参考资料来源:百度百科-容斥原理

"∪"是并集的意思,念"并"(如A并B),就是一个元素可以属于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 ,a3

a1={ 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 }

以上就是这个公式的具体应用

我的表达不是很规范

但是这个公式的方法就是这样的

重在理解

我举的例题的答案其实可以一眼看穿

但是这个公式揭示了普遍原理,是用来解决复杂的问题的

U代表全集,也就是所有的元素包含在一起,当然也包含AB。你说的口朝下的代表“交”,也就是他左右两边两个集合的公共元素。

如果写成口朝上代表并集,就是AB中所有不重复的元素的集合。

不知道你问的U是“由”还是并集。

A∪B∪C∪D=|A|+|B|+|C|+|D| - |A∩B| - |B∩C| - |C∩A|- |A∩D| - |B∩D| - |C∩D|

+|A∩B∩C|+|A∩B∩D| +|A∩C∩D| +|B∩C∩D| -|A∩B∩C∩D|

推导过程我们可以先看三个,比如你过程中出现的|B∪C∪D|

|B∪C∪D|=|B|+|C∪D|-|B∩(C∪D)|=|B|+|C|+|D|-|C∩D|-|[(B∩C)∪(B∩D)]|

=|B|+|C|+|D|-|C∩D|-|B∩C|-|B∩D|+|B∩C∩D|

以上就是关于什么是容斥原理全部的内容,包括:什么是容斥原理、容斥原理中∪∩符号 怎么念各自代表的意思是、n个集合的并集(容斥原理公式)等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!

转载请注明原文地址:https://juke.outofmemory.cn/read/3691018.html

最新回复(0)