一、 容斥原理

$A_1,A_2,\cdots ,A_n$ 是 $n$ 个集合 ; 则 这 $n$ 个集合 并集的元素个数 是 :

$$|\bigcup _{i=1}^n{A}_i|=\sum _{i=1}^n|A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n-1}|A_1\cap A_2\cap \cdots \cap An|$$

解析 :

$n$ 个集合进行并运算后 , 元素个数 , 通常使用 容斥原理 进行计算 ;

${\sum }_{i=1}^n|A_i|$ : 将每个集合中的 元素个数 相加 , 该值大于 总元素数 , 需要进行修正 ; ( 系数值 $(-1{)}^0$ )

${\sum }_{i<j}|A_i\cap A_j|$ : 减去两两相交的元素个数 , 该值又小于 总元素数 , 继续进行修正 ; ( 系数值 $(-1{)}^1$ )

${\sum }_{i<j<k}|A_i\cap A_j\cap A_k|$ : 加上三个集合相交的元素个数 , 该值大于 总元素数 , 继续进行修正 ; ( 系数值 $(-1{)}^2$ )

减去四个集合相交的元素个数 , 该值小于 总元素数 , 继续进行修正 ; ( 系数值 $(-1{)}^3$ )

$⋮$

$(-1{)}^{n-1}|A_1\cap A_2\cap \cdots \cap An|$ : 加上 $(-1{)}^{n-1}$ 乘以 $n-1$ 个集合相交的元素个数 ; ( 系数值 $(-1{)}^{n-1}$ )

上述 奇数个集合 交集元素个数 前系数是 正数 , 偶数个集合 交集元素个数 前系数是 负数 ;

二、 容斥原理 示例

$1$ ~ $10000$ 之间 , 既不是某个整数的平方 , 又不是某个整数的立方 , 的数个数 ?

全集 : $E$ 集合是全集 , 是 $1$ 到 $10000$ 的自然数 , $E$ 集合的个数 $|E|=10000$

平方对应的数集合 $A$ : $A$ 集合是 某个数 的平方 对应的 某个数 集合 , $A=\{x\in E|x=k^2\wedge k\in Z\}$ , $A$ 集合元素个数是 $|100|$ ;

$100^2=10000$ , 因此 $A$ 集合的元素是 $\{0,1,2,\cdots ,100\}$ , 元素个数有 $100$ 个 ; $1^2,2^2,3^3,\cdots ,100^2$ 都在 $1$ 到 $10000$ 之间 , $101^2=10201$ 就超过 $10000$ 了 ;

立方对应的数集合 $B$ : $B$ 集合是 某个数 的立方 对应的 某个数 集合 , $B=\{x\in E|x=k^3\wedge k\in Z\}$ , $A$ 集合元素个数是 $|21|$ ;

$21^3=9261$ , 因此 $B$ 集合的元素是 $\{0,1,2,\cdots ,21\}$ , 元素个数有 $21$ 个 ; $1^3,2^3,3^3,\cdots ,21^3$ 都在 $1$ 到 $10000$ 之间 , $22^2=10648$ 就超过 $10000$ 了 ;

计算 $A\cap B$ 集合的交集 $C$ : 元素个数 , 既是平方 , 又是立方 , 肯定是六次方的数 , $C=\{x\in E|x=k^6\wedge k\in Z\}$ , $C$ 集合的元素个数是 $4$ ;

$4^6=4096$ , 因此 $C$ 集合的元素是 $\{1,2,3,4\}$ , 元素个数有 $4$ 个 ; $1^6,2^6,3^6,4^6$ 都在 $1$ 到 $10000$ 之间 , $5^6=15,625$ 就超过 $10000$ 了 ;

题目可以转化成 : 集合 $Z$ 中 , 既不属于 $A$ 集合 , 有不属于 $B$ 集合 的数字 ;

集合 $A$ 与 集合 $B$ 并集是 $A\cup B$

上述并集 的 绝对补集 $\sim (A\cup B)$ 元素个数 $|\sim (A\cup B)|$ , 就是题目中要求的结果 ;

$|\sim (A\cup B)|=|E|-|A\cup B|$

上述式子中 , $|E|=10000$ , $|A\cup B|$ 值可以使用 容斥原理 进行计算 ;

$|A\cup B|$ 两个集合并集的元素个数 , 可以使用两个集合的元素个数相加 , 然后减去两个集合交集的元素个数 ;

$|A\cup B|=|A|+|B|-|A\cup B|=100+21-4=117$

代入总的公式 : $|\sim (A\cup B)|=|E|-|A\cup B|=10000-117=9883$

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/108876810