首页 > 正在进行安全检测...

正在进行安全检测...

发布时间：2024-03-17 08:06:55 来源：文档文库

小中大

字号：

手机查看

多个集合并集中元素计算公式
(容斥定理的应用组合数学的内容
card(A∪B=card（A）+card（B）-card（A∩B）
card（A∪B∪C）=card（A）+card（B）+card（C）-card（A∩B）-card（A∩C）-card（B∩C）+card（A∩B∩C）
card（A∪B∪C∪D）=card（A）+card（B）+card（C）+card（D）-card（A∩B）-card（A∩C）-card（B∩C）-card（A∩D）+card（A∩B∩C）+card（A∩B∩D）+card（B∩C∩D）-card（A∩B∩C∩D）
更一般的容斥定理：
n(A1∪A2∪...∪Am=∑n(Ai1≤i≤m－∑n(Ai∩Aj1≤i≤j≤m＋∑n(Ai∩Aj∩Ak－…＋(-1m-1n(A1∩A2…∩Am1≤I,j,k≤m
注：m-1是-1的指数。就是说求几个集合的并集可以先把他们统统加起来
但是这样做有些地方就多加了，那么就要减掉一些（由公式来判断什么需要减去），但是这样做有些地方就多减了，那么就要加上一些（由公式来判断什么需要加上）。
......

举个例子吧
集合 a1 , a2 , a3
a1={ 1 , 2 , 3 ，4 }
a2={ 2 , 3 , 4 ，5 }
a3={ 3 , 4 , 5 ，1 }
求三个集合的并集
按照这个公式
∑n(Ai1≤i≤m = a1 + a2 + a3 = { 1 , 2 , 3 ，4 , 2 , 3 , 4 ，5 , 3 , 4 , 5 ，1 }
∑n(Ai∩Aj1≤i≤j≤m = (a1∩a2 + a2∩a3 + a3∩a1 = { 2 , 3 , 4 } +{ 3 , 4 , 5 } + { 3 ，4 , 1}
∑n(Ai∩Aj∩Ak1≤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 }

本文来源：https://www.2haoxitong.net/k/doc/3fff9c70a8114431b80dd858.html