小蓝书 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}$