小蓝书 16.1

一、计数原理

1. 加法原理

设完成某件事有 \(m\) 类不同的方法，

第 \(i(1\le i \le m)\) 类方法中有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 + n_2 + \cdots + n_m \] 种方法。

在严格化的数学中，加法原理是有关集合大小的事实。¹

断言任意有限多个两两互斥的集合大小之和，等于其并集的大小

以符号表示为，若集合 \(S_1,S_2,\cdots,S_n\) 两两互斥，则有 \[ |S_1|+|S_2| + \cdots + |S_n| = |S_1 \cup S_2 \cup \cdots S_n| \] 容斥原理可以视为加法原理的推广。

2. 乘法原理

设完成某件事需要 \(m\) 个步骤，

做第 \(i\) 步有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 \times n_2 \times \cdots \times n_m \]

在集合论中，乘法原理可以设为基数乘积的定义。²

对于集合 \(S_1,S_2,\cdots,S_n\) ，以 \(|S_i|\) 表示 \(S_i\) 的元素个数（基数），则有 \[ |S_1| \times |S_2| \times \cdots \times |S_n| = |S_1 \times S_2 \times \cdots \times S_n| \] 其中 \(S_i \times S_j\) 表示笛卡尔积。 \(S_i\) 可以是无穷集。参见基数和选择公理。

二、排列组合

下面两个指的是无重复的排列与组合

1. 排列数

从 \(n\) 个不同元素中取 \(k(k\le n)\) 个不同元素，并按一定顺序排成一列的方案数 \[ \mathrm{A}_{n}^{k} = \frac{n!}{(n-k)!} \] 也可写作 \(\mathrm{P}_{n}^{k}\) 或直接用组合数写法 \(k! \times \binom{n}{k}\)

2. 组合数

从 \(n\) 个不同元素中取 \(k(k \le n)\) 个不同元素的方案数 \[ \binom{n}{k} = \dfrac{n!}{k!(n-k)!} \] 高中一般记作 \(\mathrm{C}_n^{k}\) ，不是很推荐使用。

特别地，规定当 \(k > n\) 时， \(\mathrm{A}_n^{k} = \mathrm{C}_n^{k}=0\)

三、插板法

插板法是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。

1. 正整数和的数目

\(n\) 个相同的元素，要求将其分成 \(k\) 组，不能有组为空。

考虑将 \(k - 1\) 块板子插入到 \(n\) 个元素两两形成的 \(n-1\) 个空隙里面

因为元素是完全相同的，所以答案就是 \[ \binom{n - 1}{k - 1} \] 根据其本质，我们可以用同样的方法计算 \(x_1+x_2+\cdots+x_k=n~(x_i > 0)\) 的解的组数。

2. 非负整数和的数目

\(n\) 个相同的元素，要求将其分成 \(k\) 组，每组允许为空。

此时我们无法直接插板了，因为一个空里可能塞了多个板子。

考虑以下问题：

计算 \(x_1+x_2+\cdots+x_k=n~(x_i \ge 0)\) 的解的组数。

考虑记 \(y_i = x_i + 1\) ，则原式变为了 \(y_1 + y_2 + \cdots +y_k = n + k\) ，这就变成了刚才的问题

因此该问题的方案数为 \[ \binom{n+k-1}{n-1} = \binom{n+k-1}{k} \] 前面和后面的写法是一样的，不过前者更方便记忆。

3. 不同下界整数和的数目

\(n\) 个相同的元素，要求将其分成 \(k\) 组，每组要求至少有 \(a_i\) 个元素 \((\sum a_i \le n)\)

还是一样的方案，其本质就是在求 \(x_1+x_2+\cdots+x_k=n\) 的解的组数，其中 \(x_i \ge a_i\) 。

显然，我们这次记 \(y_i = x_i - a_i + 1\) ，原式变为了 \(y_1 + y_2 + \cdots +y_k = n + k - \sum a_i\) ，则 \[ \binom{n-\sum a_i+k-1}{n-\sum a_i} \]

4. 不相邻的排列

\(1\sim n\) 这 \(n\) 个自然数中选 \(k\) 个，这 \(k\) 个数任何两个都不相邻的方案数 \[ \dbinom{n-k+1}{k} \]

证明：

感谢 AprilGrimoire 老师的耐心解释 ~~我太蠢了~~

因为选出来的 \(k\) 个数按照一定顺序排列（组合嘛）

不妨假设这个顺序满足 \[ a_1 < a_2 < \cdots < a_k \] \(a_i\) 表示选的第 \(i\) 个数

设合法的答案序列为 \(a_1,a_2,\cdots,a_k\) ，并让原序列按 \(1\sim n\) 排好

我们将「前 \(k-1\) 个被选中的数」在原序列中分别与其右侧相邻的数合并

因为 \(a_i\) 和 \(a_{i+1}\) 一定不相邻，因此合并不会改变选出 \(k\) 个的事实

我们不需要知道这 \(k-1\) 个数具体是什么

因为对于每一个合法的答案序列，都存在唯一的合并方法

这样就形成了 \(n-k+1\) 个新的块，并且这些块不再受到“相邻”的限制

然后就在这 \(n-k+1\) 个块中选 \(k\) 个即可。

答案就是 \(\dbinom{n-k+1}{k}\)

四、多重集与多重集的排列组合

在此章节，请注意区分可重组合数、多组组合、多重组合数与多重集的组合数。

可重组合数 \(H_n^{m}\) 是单独的一类，用于计算 \(n\) 个不同元素取 \(k\) 个且可以取相同的元素的方案数

多组组合 也是单独的一类，只是最终的式子与多重组合数的式子相同，但含义不全相同。

多重组合数和多重集的组合数在下面会讲解：

多重组合数只是一个别称，实际上指的是多重集的排列数。
与多重集的排列数相对，多重集的组合数正如其字面含义。

1. 可重复的排列

从 \(n\) 个不同元素中取 \(k(k\le n)\) 个元素（同一元素允许重复取出），并按一定顺序排成一列的方案数为 \[ n^k \]

2. 可重复的组合（可重组合数 \(H_n^{m}\)）

从 \(n\) 个不同元素中取 \(m\) 个元素（同一元素允许重复取出）的方案数为 \[ \binom{n+m-1}{m} \]

简单证明：

把每次选的看作 \[ \{x_1,x_2,\cdots,x_m\} \quad(1\le x_1 \le x_2 \le \dots \le x_m \le n) \] 然后令 \(y_i = x_i + i-1\)

得到 \[ \{y_1,y_2,\cdots,y_m\} \quad (1 \le y_1 < y_2 < \cdots \le n+m-1) \] 不难发现这就是 \(\binom{n+m-1}{m}\)。证毕。

3. 多组组合

把 \(n\) 个相异元素分为 \(k (k \le n)\) 个按照一定顺序排列成的组，其中第 \(i\) 组有 \(n_i\) 个元素（ \(\sum n_i = n\) ），则不同的分组方法的种数为 \[ \dbinom{n}{n_1,n_2,\cdots,n_k} = \dfrac{n!}{n_1!n_2!\cdots n_k!} \]

简单证明：

根据组合数的性质，不难推出方案数为 \[ \binom{n}{n_1} \times \binom{n-n_1}{n_2}\times \binom{n-n_1-n_2}{n_3}\times \cdots \times \binom{n_k-\sum_{1\le i <k}n_i}{n_k} \] 通过展开上面的式子，可以得到 \[ \dfrac{n!}{n_1!n_2!\cdots n_k!} \] 证毕。

另外，小蓝书上写的是分隔符是空格而不是逗号，其实不影响。

4. 多重集的排列数（多重组合数）

多重集是指包含重复元素的广义集合。³

设 \(S=\{n_1 \cdot a_1,~n_2 \cdot a_2,\cdots,n_k\cdot a_k\}\) 表示由 \(n_1\) 个 \(a_1\) ，\(n_2\) 个 \(a_2\) ，\(\cdots\) ，\(n_k\) 个 \(a_k\) 组成的多重集， \(S\) 的全排列个数为 \[ \dbinom{n}{n_1,n_2,\cdots,n_k} = \dfrac{n!}{n_1!n_2!\cdots n_k!} \] 相当于把相同元素的排列数除掉了。

具体地，如果 \(n\) 个元素中，分别有 \(n_1,n_2,\cdots,n_k\) 个元素相同，且 \(n_1 + n_2 + \cdots + n_k = n\) ，则这 \(n\) 个元素的全排列称为多重集的排列数，或称作多重组合数。

小蓝书上写的「不全相异元素的全排列」就是多重组合数（多重集的排列数）

其不同的排列个数记为 \(\binom{n}{n_1,n_2,\cdots,n_k}\)，则 \[ \dbinom{n}{n_1,n_2,\cdots,n_k} = \dfrac{n!}{n_1!n_2!\cdots n_k!} \] 不难发现， \(\dbinom{n}{m} = \dbinom{n}{m,n-m}\) ，只不过后者比较繁琐，一般不写。

5. 多重集的组合数

设 \(S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}\) 表示由 \(n_1\) 个 \(a_1\) ，\(n_2\) 个 \(a_2\) ，\(\cdots\) ，\(n_k\) 个 \(a_k\) 组成的多重集

对于正整数 \(r(r < n_i)\) ，从 \(S\) 中选择 \(r\) 个元素组成一个多重集的方案数就是多重集的组合数

这个问题等价于 \(x_1+x_2+\cdots+x_k=r\) 的非负整数解的数目，可以用插板法解决，答案为 \[ \left(\begin{array}{c} r+k-1 \\ k-1 \end{array}\right) \] 我们考虑一个拓展的问题。

对于正整数 \(r\) ，从 \(S\) 中选择 \(r\) 个元素组成一个多重集的方案数。

这个问题和上个问题的不同之处在于 \(r\) 的范围不受复杂的限制了。

换句话说，这反倒限制了每种元素的取的个数。

同样的，我们可以把这个问题转化为带限制的线性方程求解 \[ \forall i \in[1, k],~x_i \leq n_i \land \sum_{i=1}^k x_i=r \] 根据容斥原理（后面我们会讲） \[ \begin{aligned} \left|\bigcup_{i=1}^n S_i\right|&= \sum_{1\le i\le n}\left|S_i\right|-\sum_{1\le i < j \le n}\left|S_i \cap S_j\right|+\sum_{1\le i < j < k \le n}\left|S_i \cap S_j \cap S_k\right|-\cdots +(-1)^{n-1}\left|\bigcap_{i=1}^n S_i\right| \\[6pt] &= \sum_{1\le i\le n}\left(\begin{array}{c} k+r-n_i-2 \\ k-1 \end{array}\right)-\sum_{1\le i < j\le n}\left(\begin{array}{c} k+r-n_i-n_j-3 \\ k-1 \end{array}\right) \\[6pt]&+\sum_{1\le i < j < l\le n}\left(\begin{array}{c} k+r-n_i-n_j-n_l-4 \\ k-1 \end{array}\right) - \cdots + (-1)^{k-1}\left(\begin{array}{c} k+r-\sum_{i=1}^k n_i-k-1 \\ k-1 \end{array}\right) \end{aligned} \] 拿全集 \(|U| = \binom{k + r - 1}{k - 1}\) 减去上式，得到多重集的组合数 \[ \mathrm{Ans} = \sum_{p=0}^k(-1)^p \sum_A\binom{k+r-1-\sum_A n_{A_i}-p}{k-1} \] 其中集合 \(A\) 是充当枚举子集的作用，满足 \(|A|=p, A_i<A_{i+1}\) 。

五、相异元素的圆排列和项链数

1. 圆排列

将 \(n\) 个不同元素不分首尾排成一圈，称为 \(n\) 个相异元素的圆排列，方案数为 \[ (n-1)! \] 证明：因为 \(n\) 个不同的直线排列 \(A_1A_2\cdots A_{n-1}A_n\) ，\(A_2A_3\cdots A_nA_1\) ，\(A_3A_4\cdots A_1A_2\) 等

分别将其首尾相连排成一圈，得到的是同一种圆排列，而 \(n\) 个相异元素的全排列有 \(n!\) 个，故方案数 \[ \frac{n!}{n} = (n - 1)! \]

2. 项链数

将 \(n\) 个不同的珠子串成一副项链，则得到的不同的项链数

当 \(n=1\) 或 \(n = 2\) 时，为 \(1\) ，这点显然
当 \(n \ge 3\) 时为 \(\frac{1}{2}(n-1)!\)

后者的证明很简单，圆排列有顺时针和逆时针的区别，而项链数没有，因此只有一半。

六、容斥原理

容斥原理(principle of inclusion-exclusion)：令 \(X\) 为一个有限集合，\(P_1, P_2,\dots , P_m\) 是一些性质的集合，对于任意 \(S \subseteq [m]\) ，即 \(S\subseteq \{1,2,\cdots,m\}\) ，定义 \(N(S) = \{x \in X \mid \forall i \in S : x \text{ has } P_i\}\) 。那么 \(X\) 中满足性质 \(P_{1\sim m}\) 的元素个数为 \[ \sum_{S \subseteq [m]} (-1)^{|S|+1} \left|N(S)\right| \] 如果是不满足任何一个性质的话，把指数中的 \(|S|+1\) 改成 \(|S|\) 即可。

特别地，对于任意的 \(S \subseteq [m]\) ，如果 \(N(S)\) 只和 \(S\) 的大小（即 \(|S|\) ）有关，那么式子可以化简为 \[ \sum_{i=0}^{m} (-1)^{i+1} \binom{m}{i} N(i) \] 其中 \(N(i)\) 表示对于任意满足 \(S \subseteq [m],|S|=i\) 的 \(N(S)\) 值。

如果是不满足任何一个性质的话，把指数中的 \(i+1\) 改成 \(i\) 即可。

容斥原理的常用技巧：

定义一些“坏性质” \(P_1,\dots,P_m\)
找到对于每个 \(S\subseteq [m]\) 计算 \(N(S)\) 的方法
套用容斥原理计算不满足任何一个“坏性质”的元素个数
注意这里求的是不满足任何坏性质，因此用以下公式 \[ \sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right| \]

话说我好像在好多文章里都写过容斥原理的介绍了。

1. 筛法公式

上面的文字看不懂？没关系，我们来个一般形式。 \[ \left|\bigcup_{i=1}^n S_i\right|= \sum_{1\le i\le n}\left|S_i\right|-\sum_{1\le i < j \le n}\left|S_i \cap S_j\right|+\sum_{1\le i < j < k \le n}\left|S_i \cap S_j \cap S_k\right|-\cdots +(-1)^{n-1}\left|\bigcap_{i=1}^n S_i\right| \] 另外，逐步淘汰原理（筛法公式）也可以写为以下形式 \[ \left|\bigcap_{i=1}^k \overline{S_i}\right|= |U| - \left( \sum_{1\le i\le n}\left|S_i\right|-\sum_{1\le i < j \le n}\left|S_i \cap S_j\right|+\sum_{1\le i < j < k \le n}\left|S_i \cap S_j \cap S_k\right|-\cdots +(-1)^{n-1}\left|\bigcap_{i=1}^n S_i\right|\right) \] 以上统称容斥原理。

2. 错排公式

将 \(n\) 个不同元素重新排列，使得每个元素都不在原来的位置上

考虑使用筛法公式 \[ \begin{aligned} \left|\bigcap_{i=1}^k \overline{S_i}\right| &= |U| - \left( \sum_{1\le i\le n}\left|S_i\right|-\sum_{1\le i < j \le n}\left|S_i \cap S_j\right|+\sum_{1\le i < j < k \le n}\left|S_i \cap S_j \cap S_k\right|-\cdots +(-1)^{n-1}\left|\bigcap_{i=1}^n S_i\right|\right) \\[6pt] &= n! - (n-1)!\times\binom{n}{1} + (n-2)!\times\binom{n}{2} - \cdots + (-1)^n \times 0! \times \binom{n}{n}\ \\[6pt] &= n! - \frac{n!}{1!} + \frac{n!}{2!} - \cdots + (-1)^n\frac{n!}{n!} \\[6pt] &= n!\left(1 - \frac{1}{1!} + \frac{1}{2!}-\frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right) \end{aligned} \]

3. 置换与不动点

给定集合 \(X = \{1,2,3,\cdots,n\}\) ，\(\varphi\) 是从 \(X\) 到 \(X\) 上的一一映射，通常记为 \[ \varphi = \left\{ \begin{matrix} 1&2&\cdots&n \\\varphi(1) & \varphi(2) & \cdots & \varphi(n) \end{matrix} \right\} \] 则称 \(\varphi\) 是 \(X\) 上的置换，其中 \(\varphi(i)\) 是元素 \(i\) 在映射 \(\varphi\) 下的象。

因为是一一映射，所以 \(\varphi(1),\varphi(2),\cdots,\varphi(n)\) 实际上是 \(1,2,\cdots,n\) 的一个排列

由此，满足 \(\varphi(i) = i\) 的数称为 \(\varphi\) 的一个不动点，并根据错排公式得到

推论：集合 \(X = \{1,2,\cdots,n\}\) 上没有任何不动点的置换 \(\varphi\) 的个数为 \[ D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!}-\frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right) \]