「学习笔记」组合数学

本文部分内容来自 \(\texttt{OI-Wiki}\)。

---

加法 & 乘法原理

加法原理
完成一个工程可以有 \(n\) 类办法，\(a_i(1 \le i \le n)\) 代表第 \(i\) 类方法的数目。那么完成这件事共有 \(S=a_1+a_2+\cdots +a_n\) 种不同的方法。
乘法原理
完成一个工程需要分 \(n\) 个步骤，\(a_i(1 \le i \le n)\) 代表第 \(i\) 个步骤的不同方法数目。那么完成这件事共有 \(S = a_1 \times a_2 \times \cdots \times a_n\) 种不同的方法。

排列与组合

排列

从 \(n\) 个不同元素中，任取 \(m\)（\(m\leq n\)，\(m\) 与 \(n\) 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个排列；从 \(n\) 个不同元素中取出 \(m(m\leq n)\) 个元素的所有排列的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的排列数，用符号 \(\mathrm A_n^m\)（或者是 \(\mathrm P_n^m\)）表示。

\[\mathrm A_n^m = n \cdot (n - 1) \cdot (n - 2) \cdots (n - m + 1) = \dfrac{n!}{(n - m)!} \]

公式可以这样理解：\(n\) 个人选 \(m\) 个来排队 \((m \le n)\)。第一个位置可以选 \(n\) 个，第二位置可以选 \(n-1\) 个，以此类推，第 \(m\) 个（最后一个）可以选 \(n-m+1\) 个，得：

\[\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} \]

全排列：\(n\) 个人全部来排队，队长为 \(n\)。第一个位置可以选 \(n\) 个，第二位置可以选 \(n-1\) 个，以此类推得：

\[\mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! \]

全排列是排列数的一个特殊情况。

组合

从 \(n\) 个不同元素中，任取 \(m \leq n\) 个元素组成一个集合（不是排列），叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合；从 \(n\) 个不同元素中取出 \(m \leq n\) 个元素的所有组合的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数，用符号 \(\dbinom{n}{m}\) 来表示，读作「\(n\) 选 \(m\)」。

组合数计算公式

\[\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} \]

如何理解上述公式？我们考虑 \(n\) 个人选 \(m\) 个出来（\(m \le n\)），不排队，不在乎顺序。如果在乎顺序那么就是
\(\mathrm A_n^m\)，如果不在乎那么就要除掉重复，那么重复了多少？同样选出来的 \(m\) 个人，他们还要「全排」得 \(m!\)。
组合数也常用 \(\mathrm C_n^m\) 表示，即 \(\mathrm C_n^m=\dbinom{n}{m}\)。现在数学界普遍采用 \(\dbinom{n}{m}\) 的记号而非 \(\mathrm C_n^m\)。

特别地，规定当 \(m>n\) 时，\(\mathrm A_n^m=\dbinom{n}{m}=0\)。

关于组合数的一些公式

\[\dbinom{n}{0} = \dbinom{n}{n} = 1\\ \]

这个应该很好理解，不选和全选的方式就只有一种情况。

---

\[\dbinom{n}{m} = \dbinom{n}{n - m}\\ \]

这个公式可以这么理解，你在 \(n\) 个人中选走了 \(m\) 个人，另一个人把剩下的 \(n - m\) 个人给选走了，对你来说，你选人的方案数为 \(\dbinom{n}{m}\)，而另一个人选人的方案数与我们是一样的，换位思考一下，倘若主动权在另一个人手中，则他选人的方案数就是 \(\dbinom{n}{n - m}\)，方案数不变，两者是等价的，故得 \(\dbinom{n}{m} = \dbinom{n}{n - m}\)。

---

\[\dbinom{n}{m} = \dbinom{n - 1}{m - 1} + \dbinom{n - 1}{m} \]

这个公式可以这么理解，对于从 \(n\) 个人中选 \(m\) 个人的方案数，可以分第一个人选或不选两种方案，如果第一个人选，则方案数为 \(\dbinom{n - 1}{m - 1}\)，如果第一个人不选，则方案数为 \(\dbinom{n - 1}{m}\)，加起来即为 \(\dbinom{n}{m}\)。
由此，我们可以得到组合数的递推公式，下面是递推求组合数的代码。

for (int i = 0; i <= n; ++ i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++ j) {
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}

二项式定理

之前写了：「学习笔记」从二项式定理到多项式定理

抽屉原理（鸽巢原理）

现在有 \(n + 1\) 个东西，放到 \(n\) 个抽屉里面去，那么肯定有一个抽屉放了 \(2\) 个东西。
不信你自己试试看。
让我们扩展一下：现在要把 \(kn + 1\) 个东西放到 \(n\) 个抽屉中去，则至少有 \(1\) 个抽屉至少有 \(k + 1\) 个东西。
定理很简单，这类题目真正难的地方在于你要能看出它是抽屉原理，要知道谁是抽屉，谁是东西。

容斥原理

之前写了：「学习笔记」容斥原理

组合数的题目

有 \(n\) 个数，\(1, 2, 3, 4, 5, 6, \cdots\)，选 \(m\) 个数，不计顺序，一个数可以选多次，求方案数。

假设选出的数是 \(a_1, a_2, a_3, \cdots, a_m\)，这 \(m\) 个数不能重复，且递增选出。方案数：\(\dbinom{n}{m}\)
这是我们所知道的，\(a \le a_1 < a_2 < a_3 < \cdots < a_m \le n\\\)。
但是，对于这个题来说，情况是 \(1 \le b_1 \le b_2 \le b_3 \le \cdots \le b_m \le n\)，因此我们需要转化过去，即

\[a \le a_1 < a_2 < a_3 < \cdots < a_m \le n\\ \Uparrow\\ 1 \le b_1 \le b_2 \le b_3 \le \cdots \le b_m \le n\\ \]

考虑构造，\(C_1 = b_1, C_2 = b_2 + 1, C_3 = b_3 + 2, \cdots , C_m = b_m + m - 1\)
那么，\(1 \le b_1 \le b_2 \le b_3 \le \cdots \le b_m \le n\) 就转化为了 \(1 \le C_1 < C_2 < C_3 \cdots < C_m \le n + m - 1\)
我们的方案数也呼之欲出了：\(\dbinom{n + m - 1}{m}\)。