文章目录
一、 容斥原理
二、 容斥原理 示例
一、 容斥原理
A 1 , A 2 , ⋯ , A n A_1 , A_2 , \cdots , A_nA
1
,A
2
,⋯,A
n
是 n nn 个集合 ; 则 这 n nn 个集合 并集的元素个数 是 :
∣ ⋃ i = 1 n A i ∣ = ∑ i = 1 n ∣ A i ∣ − ∑ i < j ∣ A i ∩ A j ∣ + ∑ i < j < k ∣ A i ∩ A j ∩ A k ∣ − ⋯ + ( − 1 ) n − 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A 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 |
∣
i=1
⋃
n
A
i
∣=
i=1
∑
n
∣A
i
∣−
i<j
∑
∣A
i
∩A
j
∣+
i<j<k
∑
∣A
i
∩A
j
∩A
k
∣−⋯+(−1)
n−1
∣A
1
∩A
2
∩⋯∩An∣
解析 :
n nn 个集合进行并运算后 , 元素个数 , 通常使用 容斥原理 进行计算 ;
∑ i = 1 n ∣ A i ∣ \sum_{i = 1}^n | A_i |∑
i=1
n
∣A
i
∣ : 将每个集合中的 元素个数 相加 , 该值大于 总元素数 , 需要进行修正 ; ( 系数值 ( − 1 ) 0 (-1)^0(−1)
0
)
∑ i < j ∣ A i ∩ A j ∣ \sum_{i < j} | A_i \cap A_j |∑
i<j
∣A
i
∩A
j
∣ : 减去两两相交的元素个数 , 该值又小于 总元素数 , 继续进行修正 ; ( 系数值 ( − 1 ) 1 (-1)^1(−1)
1
)
∑ i < j < k ∣ A i ∩ A j ∩ A k ∣ \sum_{i < j < k} | A_i \cap A_j \cap A_k |∑
i<j<k
∣A
i
∩A
j
∩A
k
∣ : 加上三个集合相交的元素个数 , 该值大于 总元素数 , 继续进行修正 ; ( 系数值 ( − 1 ) 2 (-1)^2(−1)
2
)
减去四个集合相交的元素个数 , 该值小于 总元素数 , 继续进行修正 ; ( 系数值 ( − 1 ) 3 (-1)^3(−1)
3
)
⋮ \vdots⋮
( − 1 ) n − 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A n ∣ ( -1 )^{n - 1} | A_1 \cap A_2 \cap \cdots \cap An |(−1)
n−1
∣A
1
∩A
2
∩⋯∩An∣ : 加上 ( − 1 ) n − 1 ( -1 )^{n - 1}(−1)
n−1
乘以 n − 1 n-1n−1 个集合相交的元素个数 ; ( 系数值 ( − 1 ) n − 1 (-1)^{n-1}(−1)
n−1
)
上述 奇数个集合 交集元素个数 前系数是 正数 , 偶数个集合 交集元素个数 前系数是 负数 ;
二、 容斥原理 示例
1 11 ~ 10000 1000010000 之间 , 既不是某个整数的平方 , 又不是某个整数的立方 , 的数个数 ?
全集 : E EE 集合是全集 , 是 1 11 到 10000 1000010000 的自然数 , E EE 集合的个数 ∣ E ∣ = 10000 |E| = 10000∣E∣=10000
平方对应的数集合 A AA : A AA 集合是 某个数 的平方 对应的 某个数 集合 , A = { x ∈ E ∣ x = k 2 ∧ k ∈ Z } A = \{ x \in E | x = k^2 \land k \in Z \}A={x∈E∣x=k
2
∧k∈Z} , A AA 集合元素个数是 ∣ 100 ∣ |100|∣100∣ ;
10 0 2 = 10000 100^2 = 10000100
2
=10000 , 因此 A AA 集合的元素是 { 0 , 1 , 2 , ⋯ , 100 } \{0, 1, 2 , \cdots , 100 \}{0,1,2,⋯,100} , 元素个数有 100 100100 个 ; 1 2 , 2 2 , 3 3 , ⋯ , 10 0 2 1^2 , 2^2 , 3^3, \cdots ,100^21
2
,2
2
,3
3
,⋯,100
2
都在 1 11 到 10000 1000010000 之间 , 10 1 2 = 10201 101^2 = 10201101
2
=10201 就超过 10000 1000010000 了 ;
立方对应的数集合 B BB : B BB 集合是 某个数 的立方 对应的 某个数 集合 , B = { x ∈ E ∣ x = k 3 ∧ k ∈ Z } B = \{ x \in E | x = k^3 \land k \in Z \}B={x∈E∣x=k
3
∧k∈Z} , A AA 集合元素个数是 ∣ 21 ∣ |21|∣21∣ ;
2 1 3 = 9261 21^3 = 926121
3
=9261 , 因此 B BB 集合的元素是 { 0 , 1 , 2 , ⋯ , 21 } \{0, 1, 2 , \cdots , 21 \}{0,1,2,⋯,21} , 元素个数有 21 2121 个 ; 1 3 , 2 3 , 3 3 , ⋯ , 2 1 3 1^3 , 2^3 , 3^3, \cdots ,21^31
3
,2
3
,3
3
,⋯,21
3
都在 1 11 到 10000 1000010000 之间 , 2 2 2 = 10648 22^2 = 1064822
2
=10648 就超过 10000 1000010000 了 ;
计算 A ∩ B A \cap BA∩B 集合的交集 C CC : 元素个数 , 既是平方 , 又是立方 , 肯定是六次方的数 , C = { x ∈ E ∣ x = k 6 ∧ k ∈ Z } C= \{ x \in E | x = k^6 \land k \in Z \}C={x∈E∣x=k
6
∧k∈Z} , C CC 集合的元素个数是 4 44 ;
4 6 = 4096 4^6 = 40964
6
=4096 , 因此 C CC 集合的元素是 { 1 , 2 , 3 , 4 } \{1, 2 , 3, 4\}{1,2,3,4} , 元素个数有 4 44 个 ; 1 6 , 2 6 , 3 6 , 4 6 1^6 , 2^6 , 3^6, 4^61
6
,2
6
,3
6
,4
6
都在 1 11 到 10000 1000010000 之间 , 5 6 = 15 , 625 5^6 = 15,6255
6
=15,625 就超过 10000 1000010000 了 ;
题目可以转化成 : 集合 Z ZZ 中 , 既不属于 A AA 集合 , 有不属于 B BB 集合 的数字 ;
集合 A AA 与 集合 B BB 并集是 A ∪ B A \cup BA∪B
上述并集 的 绝对补集 ∼ ( A ∪ B ) \sim ( A \cup B )∼(A∪B) 元素个数 ∣ ∼ ( A ∪ B ) ∣ |\sim ( A \cup B ) |∣∼(A∪B)∣ , 就是题目中要求的结果 ;
∣ ∼ ( A ∪ B ) ∣ = ∣ E ∣ − ∣ A ∪ B ∣ |\sim ( A \cup B ) | = |E| - |A \cup B|∣∼(A∪B)∣=∣E∣−∣A∪B∣
上述式子中 , ∣ E ∣ = 10000 |E| = 10000∣E∣=10000 , ∣ A ∪ B ∣ |A \cup B|∣A∪B∣ 值可以使用 容斥原理 进行计算 ;
∣ A ∪ B ∣ |A \cup B|∣A∪B∣ 两个集合并集的元素个数 , 可以使用两个集合的元素个数相加 , 然后减去两个集合交集的元素个数 ;
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∪ B ∣ = 100 + 21 − 4 = 117 |A \cup B| = |A| + |B| - |A \cup B| = 100 + 21 - 4 = 117∣A∪B∣=∣A∣+∣B∣−∣A∪B∣=100+21−4=117
代入总的公式 : ∣ ∼ ( A ∪ B ) ∣ = ∣ E ∣ − ∣ A ∪ B ∣ = 10000 − 117 = 9883 |\sim ( A \cup B ) | = |E| - |A \cup B| = 10000 - 117 = 9883∣∼(A∪B)∣=∣E∣−∣A∪B∣=10000−117=9883
