【集合论】容斥原理 ( 包含排斥原理 | 示例 )

一、 容斥原理

A 1 , A 2 , ⋯   , A n A_1 , A_2 , \cdots , A_n A1​,A2​,⋯,An​ 是 n n n 个集合 ; 则 这 n n n 个集合 并集的元素个数 是 :

∣ ⋃ 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​Ai​∣=i=1∑n​∣Ai​∣−i