「BUAA Discrete Mathematics Chapter6」容斥原理及应用

Part 0

Part 1

容斥原理

定理6.1.1

集合 $ S $ 中不具有性质 $ P_1 , P_2, \cdots , P_m $ 的对象个数由下面的交错表达式给出：

$$|\overline{A_1} \cap \overline{A_2} \cap \cdots\cap\overline{A_m}| = |S| - \sum|A_i| + \sum{|A_i \cap A_j|} - \sum|A_i \cap A_j \cap A_k| \\ + \cdots + (-1)^m|A_1 \cap A_2 \cap \cdots \cap A_m|$$

带重复的组合

错位排列

定理6.3.1

用 $ D_n $ 表示 $ {1,2, \cdots ,n} $ 的错位排列的数目。对于 $ n \ge 1 $ 有：

$$D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!})$$

---

• ← Previous Post
• Next Post →

---