##### 容斥原理 - 容斥原理 - **容斥原理**用于计算多个[[集合]]的[[并集]]的[[集合基数|基数]], 其核心思想是通过交替加减不同层次的交集来修正重复计算, 确保每个元素仅被统计一次, 避免重复计数 - 设两个集合 $A,B$, 则并集基数等于 $A$ 的基数加上 $B$ 的基数, 再减去它们的交集部分, 因为交集部分被重复计算了 - $|A \cup B| = |A| + |B| - |A \cap B|$ - 设三个集合 $A,B,C$, 则并集基数需要先将三个集合的基数加起来, 然后依次减去每对集合的交集, 再加回三者交集的部分, 因为它在前两次减法中被减去了两次 - $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ - 设 $n$ 个集合 $A_1, A_2, \dots, A_n$, 则并集基数需要将所有单集合的基数加起来, 然后依次减去所有二集合交集的基数, 加回所有三集合交集的基数, 依此类推, 直到最后加回所有 $n$ 个集合的交集大小 - $\begin{aligned} \left| \bigcup^n_{i=1}A_i \right| &= \sum_{i=1}^{n} |A_i| \\ &\quad - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ &\quad + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| \\ &\quad - \dots \\ &\quad + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n| \end{aligned}$ >[!example]- 容斥原理 >- 求 $5$ 个元素的排列中, 有多少种排列不使得第 $1$ 位为 $1$, 或第 $2$ 位为 $2$ ？ > - 总共排列数 $n!$, 则有 > - $A_1$, 第 $1$ 位为 $1$ 的排列数: $(n-1)!$ > - $A_2$, 第 $2$ 位为 $2$ 的排列数: $(n-1)!$ > - $A_1 \cap A_2$, 第 $1$ 位为 $1$ 且第 $2$ 位为 $2$ 的排列数: $(n-2)!$ > - 不合法排列数 > - $|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2| = (n-1)! + (n-1)! - (n-2)!$ > - 合法排列数 > - $n! - \left[2(n-1)! - (n-2)! \right]$