容斥原理¶

Lead in:

设 $S$ 是对象的有限集合，$P_1$ 和 $P_2$ 是 $S$ 中每个对象有或没有的两个性质，计数 $S$ 中既不具有性质 $P_1$ 也不具有性质 $P_2$ 的对象个数？

Ans: 设 $A_1$ 是 $S$ 中具有性质 $P_1$ 的对象组成的子集，$A_2$ 是 $S$ 中具有性质 $P_2$ 的对象组成的子集。于是，$\overline{A}_1$ 由 $S$ 中不具有性质 $P_1$ 的对象组成，$\overline{A}_2$ 由 $S$ 中不具有性质 $P_2$ 的对象组成，集合 $\overline{A}_1 \cap \overline{A}_2$ 就是目标集合， $$ |\overline{A}_1 \cap \overline{A}_2| = |S| - |A_1| - |A_2| + |A_1 \cap A_2| $$ 定理 集合 $S$ 中不具有性质 $P_1, P_2, \cdots, P_m$ 的对象个数由下面的交错表达式给出: $$ |\overline{A}_1 \cap \overline{A}_2 \cap \cdots \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| $$

总的-多加上的+多减去的-多加上的+...

证明

设 $x \in S$ 不具有任何一条性质，对右边的贡献是 $1 - 0 + 0 - 0 + \cdots + (-1)^m 0 = 1$
设 $y \in S$ 恰含有 $n \geqslant 1$ 条性质，
对 $|S|$ 的贡献是 $1 = \binom{n}{0}$
对 $\sum|A_i|$ 的贡献是 $n = \binom{n}{1}$
对 $\sum|A_i \cap A_j|$ 的贡献是 $\binom{n}{2}$
...
所以，$y$ 对右边的净贡献是 $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^m\binom{n}{m}$，$n \leqslant m$ ，所以表达式等于 $0$

推论 集合 $S$ 中至少具有性质 $P_1, P_2, \cdots, P_m$ 之一的对象个数为 $$ |A_1 \cup A_2 \cup \cdots \cup A_m| = \sum|A_i| - \sum|Ai \cap A_j| + \sum|A_i \cap A_j \cap A_k|\ - \cdots + (-1)^{m+1}|A_1 \cap A_2 \cap \cdots \cap A_m| $$

用集合的运算就可以得到

带重复的组合¶

回顾，有 $k$ 种不同对象且每种对象都有无限重的多重集的 $r$ 组合数为 $\binom{r + k - 1}{r}$ 。那如果不是无限重呢？如果有重数小于 $r$ ？

Q: 确定多重集 $T = \{3 \cdot a, 4 \cdot b, 5 \cdot c\}$ 的 10 组合的数目

把容斥原理应用到 $T^{*} = \{\infty \cdot a, \infty \cdot b, \infty \cdot c\}$ 的所有10组合的集合 $S$ 上

算 $|A_1| \Rightarrow$ $a$ 至少出现4次 $\Rightarrow$ 先确定4个 $a$ ，化为无限重多重集 (6重) 组合问题

错位排列¶

四位厨师各做了一道拿手菜，每人品尝一道菜，但不能尝自己做的那道，有多少种不同的尝法？

错位排列: 设 $X = \{1, 2, \cdots, n\}$ ，它的排列用 $i_1 i_2 \cdots i_n$ 表示，错位排列是使得 $i_1 \neq 1, i_2\neq 2, \cdots, i_n \neq n$ 的排列。用 $D_n$ 表示错位排列的个数 ($D_n$ 是可以直接用的)

求解 $D_n$ :

设 $S$ 是全部排列 $i_1 i_2 \cdots i_n$ 的集合，$A_j$ 是 $i_j = j$ 的排列集合，(注意: $A_j$ 只定义了第 $j$ 个位置)

$$ D_n = n!\space(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}) $$ $D_5 = 44, D_8 = 14833$

考虑 $\mathrm{e}^{-1}$ 的无穷级数展开: $$ \mathrm{e}^{-1} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots $$

可以发现，$\frac{D_n}{n!}$ 是非常接近 $\mathrm{e}^{-1}$ 的

错位排列的递推关系¶

1. $$ D_n = (n-1)(D_{n-2} + D_{n-1}), \space n = 3, 4, \cdots $$ 初始值 $D_2 = 1, D_1 = 0$

组合推理证明: 第1个位置放 $x$ ( $x = 2, 3, \cdots$) ，$1$ 的位置分为恰好在 $x$ 位和其他随机位置

2. $$ D_n = n D_{n-1} + (-1)^n $$ $D_n$ 是偶数当且仅当 $n$ 是奇数

此式通过上一个关系推得，它又可以推出 $D_n$

带有禁止位置的排列¶

是错位排列的扩展。令 $X_1, X_2, \cdots, X_n$ 是 $\{1, 2, \cdots, n\}$ 的子集 (可以是空集)，$P(X_1, X_2, \cdots, X_n)$ 表示 $\{1, 2, \cdots, n\}$ 的排列 $i_1 i_2 \cdots i_n$ 的集合，使得 $$ i_1 不在 X_1 内, i_2不在X_2内,\cdots, i_n不在X_n内 $$

非攻击型车¶

$n$ 行 $n$ 列棋盘非攻击型车的位置与 $\{1,2,\cdots,n\}$ 的排列 $i_1i_2 \cdots i_n$ 相对应，$(1,i_1)$ 为第1个位置，以此类推。

设 $S$ 为 $n$ 个非攻击型车在 $n$ 行 $n$ 列棋盘上所有放置方法的集合。如果第 $j$ 行放置的车属于 $X_j$ ，那么说这种放置满足性质 $P_j$ 。$A_j$ 为满足性质 $P_j$ 的集合

$\begin{aligned}|P(X_1,X_2, \cdots, X_n)|&=|\bar{A}_1\cap\bar{A}_2\cap\cdots\cap\bar{A}_n|\\ &=n!- \sum|A_i| + \sum|Ai \cap A_j| - \sum|A_i \cap A_j \cap A_k|+\cdots + (-1)^{n}|A_1 \cap A_2 \cap \cdots \cap A_n|\end{aligned}$

我们现在需要求解这些和式，考虑 $\sum|A_i|$ ，设 $r_1 = |X_1|+|X_2|+\cdots+|X_n|$ （也即 $r_1$ 是把一个车放到禁止位置的方法数），得到 $\sum|A_i| = r_1(n-1)!$

同理可以定义 $r_k$ 为把 $k$ 个非攻击型车放到棋盘上，每个车都在一个禁止位置上的方法数，于是 $$ \sum|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| = r_k(n-k)! $$ 问题转化为求解 $r_k$ ，一个解法是划分区域:

相对禁止位置¶

$Q_n$ : $\{1, 2, \cdots, n\}$ 的排列中没有 $12, 23, \cdots, (n-1)n$ 这些模式的排列的个数

证明 设 $S$ 为 $\{1, 2, \cdots,n\}$ 的全部 $n!$ 个排列的集合。设 $P_j$ 是在一个排列中出现模式 $j(j+1)$ 的性质。设 $A_j$ 是具有性质 $P_j$ 的集合。

计数 $|A_1|$ : 我们把 12 看作一个整体，于是乎 $|A_1| = (n-1)!$ ，依此类推

例题: 旋转木马*¶

$|A_1| = 8 \times 6!$

$|A_1 \cap A_2| = 8 \times 6 \times 4!$

$|A_1 \cap A_2 \cap A_3| = 8 \times 6 \times 4 \times 2!$

$|A_1 \cap A_2 \cap A_3 \cap A_4| = 8 \times 6 \times 4 \times 2$

如果座位都相同呢? 循环排列，$|A_1| = 6!$

固定 (1, 5)，再排剩余的6人
或者全部除以 $8$

莫比乌斯反演*¶

这一节所涉及的数学比前面各节所涉及的都更加巧妙。——《组合数学》

TODO