组合数学习笔记

定义:

排列：从 $n$ 个元素中选取 $r$ 个元素，当考虑顺序时，所有可能的方案一共有：

$$A_n^r = \frac{n!}{(n - m)!}$$

组合：从 $n$ 个元素中选取 $r$ 个元素，当不计顺序时，所有可能的方案一共有：

$$C_n^r = \left ( n \\ r \right ) = \frac{n!}{m!(n - m)!} = \frac{A_n^m}{A_m^m}$$

组合数递推公式

如果将杨辉三角形写出来的话：

$$\begin{array}{l} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \end{array}$$

会发现这个三角形中的第 $(i, j)$ 项恰好对应了组合数 $C_i^j$ ，所以我们可以直观的得到这样一个式子：

$$C_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m$$

一种证明方法是将组合数的式子带进去算，但这样证明太复杂了。

另一种证明方法：在 $n$ 个元素中选取 $m$ 个元素中，考虑元素 $m$ 有选与不选两种情况；当选 $m$ 时，则需要在剩下 $n - 1$ 个元素中选取 $m - 1$ 个元素，当不选 $m$ 时，则需要在剩下 $n - 1$ 个元素中选取 $m$ 个元素。根据加法原理， $C_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m$ 。

• 在后续证明中，将组合数的计算公式带入显然是一个万能的方法，但如果我们考虑好 $C_n^m$ 的意义，证明就会更容易些。

组合数及其相关性质

• $C_{n+m}^n = C_{n + m}^m$

显然 $n + m$个物品中 选 $n$ 个元素的方案数等于挑出 $m$ 个元素不选的方案数。

• $C_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m$

• $C_{n + r + 1}^r = C_{n + r}^r + C_{n + r - 1}^{r - 1} + \cdots + C_n ^ 0$

反复套用上一个性质就可以证明。

• $C_n^lC_l^r = C_n^rC_{n - r}^{l - r}$

对于 $n$ 个元素，先无序取出其中 $l$ 个元素，再无序从这 $l$ 个元素中取出其中 $r$ 个元素，与先无序取出 $r$ 个元素，再从剩余的 $n-r$ 个元素中无序取出 $l-r$ 个元素是等效的。

• $C_n^0 + C_n^1 + \cdots C_n^n = 2^n$

对于 $n$ 个互异元素，将其每种选择数相加，就是选取任意个元素的情况，对应到每个元素只有选和不选两种情况。

• $C_n^0 - C_n^1 + C_n^2 - \cdots = 0$

在杨辉三角中，第 $n$ 行每个排偶数位的元素相加等于第 $n - 1$ 行元素每个元素相加，且每个排奇数位的元素相加也等于第 $n - 1$ 行元素每个元素相加。

• $C_r^r + C_{r + 1}^r + \cdots + C_n^r = C_{n + 1}^{r + 1}$

同样可以反复套用第二个性质。

• $(1 + x)^n = \Sigma_{k = 0}^n C_n^kx^{n - k} = \Sigma_{k = 0}^n C_n^kx^k$

二项式展开： $(x + y)^n = \Sigma_{i = 0}^nC_n^ix^{n - i}y^i$ ，证明可用数学归纳法

• $\Sigma_{i = 0}^n{C_n^i}^2 = C_{2n}^n$

$\Sigma_{i = 0}^n{C_n^i}^2 = \Sigma_{i = 0}^nC_n^i \times C_n^{n - i}$ 即等于 $C_{2n}^n$ 。

组合数取模

• 目标：求出 $C_n^m \equiv ? \pmod k$

• 情况一： $k = 1$ 太过于麻烦，跳过

• 情况二： $k > 1, nm \leq 10^7$

使用组合数递推公式求并每步取模，时间复杂度 $O(nm)$ 。

• 情况三： $n \leq 10^9, m \leq 10^4, k \leq 10^9$

核心要点：将 $C_n^m$ 写为 $\frac{n(n - 1)\cdots(n - m + 1)}{m!}$ ，上下相除最多只用计算 $O(m)$ 项。
对上下每一项进行质因数分解，然后统计每个质因子出现个数，快速幂合并。

• 情况四： $n, m \leq 10^10, k为小质数$

Lucas 定理（下文将讲）。

• 情况五： $n,m \leq 10^9, k \leq 10^5$

扩展 Lucas 定理（下文也将讲）。

Lucas 定理

对于求 $C_n^m\ mod\ k$ 的值，一种方法是将 $n$ 和 $m$ 分别变为 $k$ 进制的 $t$ 位数 $n_1, n_2, \cdots, n_t$ 与 $m_1, m_2,\cdots, m_t$ ，位数不足的用前导零补足。 $C_n^m\ mod\ k$ 就等于对这两个数的 $k$ 进制逐位求组合数相乘再取模。

即 $C_n^m \equiv C_{n_1}^{m_1} \cdot C_{n_2}^{m_2} \cdots C_{n_t}^{m_t} \pmod k$ 。

扩展 Lucas 定理

将 $k$ 质因数分解为 $p_1^{r_1} \cdot p_2^{r_2} \cdots p_t^{r_t}$ ，计算每一个 $C_n^m\ mod\ p_i^{r_i}$ ，最后用中国剩余定理合并。

如何求 $C_n^m\ mod\ p^k$ 呢？

先将 $C_n^m$ 写为 $\frac{n!}{m!(n - m)!}$ ，则可以将这里面每个阶乘都写为 $p^r \cdot z$ 的形式，原式的值就很好求了。

对于质数 $p$ ，有 $n! = p^r \cdot z$ ，所以可以把这 $p^r$ 个数写出来，将每个 $p^r$ 的因子都提出来，剩下的数得到一个新的序列：

$$fac = 1, 2, \cdots , p - 1, 1, p + 1, p + 2 , \cdots , 2p - 1, 2, 2p + 1, 2p + 2 , \cdots , p^r - 1 , 1$$

同时还可以记录当前数贡献了几个 $p^r$ 的因子，对应上序列为：

$$num = 0, 0, \cdots , 0, 1, 0, 0, \cdots , 0, 1, 0, 0, \cdots, 0, r$$

则显然 $i! = fac[i] \cdot p^{num[i]}$ ，若 $n \leq p^r$ ，则 $n!$ 可以直接查表求出。

当 $n > p^r$ 时，将 $p^r + 1, p^r + 2, \cdots, 2p^r$ 的 $p^r$ 的因子提出来可以得到以下序列：

$$1, 2, \cdots , p - 1, 1, p + 1, p + 2 , \cdots , 2p - 1, 2, 2p + 1, 2p + 2 , \cdots , p^r - 1 , 2$$

观察这个序列可以发现这个序列与序列 $fac$ 只差最后一个数，所以对于 $(i - 1) \cdot p^r + 1$ 到 $i \cdot p^r$ 这个序列提出 $p^r$ 的因子后 ，最后一个数显然等于 $i$ 。

如果只观察所有段序列的最后一个数，显然还需要计算 $\lfloor \frac{n}{p^r} \rfloor !$ ，这就回到了之前的问题，所以可以通过递归的形式求解 $n!$。

所以我们可以通过这种方法求出 $n!, m!, (n - m)!$ 的值分别为 $x_1 \cdot p^{y_1}, x_2 \cdot p^{y_2}, x_3 \cdot p^{y_3}$ ，则：

$$C_n^m\ mod\ p^r= \frac{x_1}{x_2 \cdot x_3} \cdot p^{y_1 - y_2 - y_3} \ mod\ p^r$$