排列组合学习笔记
xuyunao
·
·
算法·理论
前言
由于自己的排列组合能力实在太差了，感觉计数类问题很多原理都是相互纠缠的，于是写一篇学习笔记记录，也便于自己以后复习。
Part.1 基础知识
- 组合数
\binom{n}{m} = C_n^m = \frac{n!}{m! (n - m)!}
- 排列
A_n^m = \frac{n!}{(n - m)!}
Part.2 二项式定理
(a+b)^n = \sum\limits_{i=0}^{n} {n\choose i} a^i b^{n - i}
:::success[推导]
式子中共有 $n$ 个 $a+b$ 因此每一项的次数均为 $n$，枚举 $i$ 表示多少个 $a+b$ 选出乘的是 $a$，剩下的 $n - i$ 个则为 $b$，于是就有了二项式定理的式子。
:::
## Part.3 组合数递推公式
$${i\choose j} = {i - 1\choose j} + {i - 1\choose j - 1}$$
:::success[组合意义证明]
我们先从组合意义理解这个式子，考虑 $i\choose j$ 的组合意义为从 $i$ 个选出 $j$ 个的方案数，考虑第 $i$ 个元素有两种情况：
- 选第 $i$ 个元素作为第 $j$ 个被选出的，则前 $i - 1$ 个元素中选出了 $j - 1$ 个，即为 $i - 1\choose j - 1$。
- 不选第 $i$ 个元素，相当于前 $i - 1$ 个元素中选 $j$ 个，即为 $i - 1\choose j$。
运用加法原理把两种情况方案数相加，即可得出递推式。
:::
:::success[代数证明]
$$
\begin{pmatrix}
a - 1 \\
b - 1
\end{pmatrix} + \begin{pmatrix}
a - 1 \\
b
\end{pmatrix}
$$
$$
= \frac{(a - 1)!}{(a - b)!\cdot (b - 1)!} + \frac{(a - 1)!}{(a - b - 1)!\cdot b!}
$$
$$
= \frac{(a - 1)(a - 2)\cdots(a - b + 1)}{(b - 1)!} + \frac{(a - 1)(a - 2)\cdots(a - b)}{b!}
$$
提公因式，得原式
$$
= (a - 1)(a - 2)\cdots(a - b + 1)\cdot\left(\frac{1}{(b - 1)!} + \frac{a - b}{b!}\right)
$$
$$
= (a - 1)(a - 2)\cdots(a - b + 1)\cdot\left(\frac{b}{b!} + \frac{a - b}{b!}\right)
$$
$$
= (a - 1)(a - 2)\cdots(a - b + 1)\cdot\frac{a}{b!}
$$
$$
= \frac{a(a - 1)(a - 2)\cdots(a - b + 1)}{b!}
$$
$$
= \frac{a!}{(a - b)!\cdot b!} = \begin{pmatrix}
a \\
b
\end{pmatrix}
$$
证毕！
:::
### 如何预处理组合数
- 当数据范围较小时，我们可以直接递推预处理组合数，即使用上面的公式递推，注意处理边界情况。
- 当数据范围较大，此时我们就不能 $O(n^2)$ 处理，需要更优的复杂度。考虑使用 Part.1 的定义式，直接预处理阶乘和逆元，每次可以 $O(1)$ 计算组合数。
## Part.4 杨辉三角与组合数之间的关系
在初中数学课本上经常出现杨辉三角与 $(a+b)^n$ 各项系数之间的关系，之前一直没有搞懂。
:::info[杨辉三角图]
:::
:::info[杨辉三角与组合数？]{open}
我们令杨辉三角行列均从 $0$ 开始编号，设 $f_{i,j}$ 表示杨辉三角第 $i$ 行第 $j$ 列得值，考虑杨辉三角得递推式 $f_{i,j} = f_{i - 1,j} + f_{i - 1,j - 1}$，发现这个式子和组合数递推公式 $C_i^j = C_{i-1}^j + C_{i - 1}^{j - 1}$ 是相同的，由此我们可以得出 $f_{i,j} = C_i^j$，也就是杨辉三角第 $i$ 行第 $j$ 列的值就是 $i\choose j$。
:::
:::info[杨辉三角与二项式定理？]{open}
由二项式定理的式子
$$(a+b)^n = \sum\limits_{i=0}^{n} {n\choose i} a^i b^{n - i}$$
我们就不难看出，展开后每一项的系数其实就是 $n\choose i$，由上面杨辉三角与组合数的关系，可以发现对于 $(a+b)^n$ 的各项系数实际上就是杨辉三角第 $n$ 行每一项的值。
:::
## Part.5 组合数的性质
:::info[对称恒等式]{open}
$${n \choose k} = {n \choose n - k}$$
考虑选出 $k$ 个数之后，能确定出唯一的补集，于是得出这个式子。
:::
:::info[吸收恒等式]{open}
$${n \choose k} = \frac{n}{k} {n - 1 \choose k - 1}$$
组合意义不太好想，考虑把 Part.1 的式子拆开，就能得到这个式子。
:::
::::info[杨辉三角行求和]{open}
$${n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n$$
:::success[推导]
考虑组合意义，从 $n$ 个元素中选出任意个的方案数之和，那么就是每个元素选或不选，总共 $2^n$ 种方案。
代数的证明，我们取二项式定理中 $a=1,b=1$ 的特殊情况，那么有 $(1 + 1)^n = \sum\limits_{i=0}^n {n\choose i}$，即上面的式子。
:::
::::
::::info[杨辉三角列前缀和]{open}
$$\sum\limits_{i = k}^n {i \choose k} = {n +1\choose k + 1}$$
:::success[推导]
考虑讲 $\sum$ 展开，变成了
$${k\choose k} + {k + 1\choose k} + \cdots + {n\choose k}$$
其中 ${k\choose k} = {k + 1 \choose k + 1}$，由组合数递推公式，依次合并相邻两项，得原式
$$= {n \choose k + 1} + {n\choose k}$$
$$= {n + 1\choose k + 1}$$
:::
::::
::::info[范德蒙德卷积]{open}
$$\sum\limits_{i = 0}^k {n\choose i}{m\choose k-i} = {n + m\choose k}$$
:::success[推导]
证明考虑使用二项式定理。
$$\sum\limits_{k = 0}^{n + m} {n + m\choose k} x^k = (x + 1) ^ {n + m}$$
$$= (x + 1)^n(x + 1)^m$$
$$= \sum\limits_{r = 0}^h {n\choose r} x^r \sum\limits_{s = 0}^m {m\choose s} x^s$$
$$= \sum\limits_{k=0}^{n+m} \sum\limits_{r=0}^k {n\choose r} {m\choose k - r} x^k$$
可得
$$\sum\limits_{r=0}^{k} {n\choose r}{m\choose k-r} = {n+m\choose k}$$
:::
::::
::::info[不知名性质]{open}
$${n\choose m} {m\choose k} = {n\choose k} {n - k \choose m - k}$$
:::success[推导]
组合意义上，考虑这个式子，实际上是先从 $n$ 个元素里选出 $m$ 个，再从这 $m$ 个中选 $k$ 个。
考虑先选出这 $k$ 个作为 $m$ 的一部分，然后从剩下的 $n-k$ 个中选出另外的 $m - k$ 个，也就是这个式子。
:::
::::
## Part.6 多重集排列
$n$ 个球有 $k$ 个种类，每一类有 $a_i$ 个完全相同的球，求这 $n$ 个球的排列数。
这里用一种类似容斥的考虑方式，由于同一种类之内的排列是相同的，这一类被算重了 $a_i!$，因此我们考虑从 $n!$ 种排列内去掉每一类算重的贡献。
具体的，对于每一类 $i$ 我们要从 $n!$ 除掉这一类的贡献 $a_i!$，最终答案也就是
$$\frac{n!}{\prod\limits_i a_i!}$$
## Part.7 两道简单题
[Shaass and Lights](https://www.luogu.com.cn/problem/CF294C)
:::info[Hint]
发现点亮的灯会把整个序列划分为若干连续段。
:::
:::success[Solution]
做过的第一道多重集排列！
发现连续段之间互不影响，因此考虑对于每个连续段计算方案数，发现连续段只能从两个端点向内扩展。
因此每个连续段 $i$ 内方案数为 $2^{len - 1}$，然后考虑总排列数，由于同一连续段内方案数已经固定了，要从总排列数中去掉，最终答案大概就是
$$\frac{n!}{\prod\limits_i len_i!} \times \prod\limits_i 2^{len_i}$$
需要注意处理两端的边界情况，边界只有一种点亮方案。
:::
[Count Sequences 2](https://www.luogu.com.cn/problem/AT_abc425_e)
:::warning[一个并不正确的做法？]
场上很快就想到了一个多重集排列做法，设 $s = \sum\limits_{i = 1}^n c_i$，则最终方案数为
$$\frac{s!}{\prod\limits_i c_i}$$
这也就是这个题多重集排列的理解方式，但我们发现模数是给定的，不保证质数也不保证互质，因此不好处理逆元，于是考虑换种做法。
:::
:::success[Solution]
考虑每次从剩下的位置中选择 $c_i$ 个位置放上，然后剩余的位置就会减少 $c_i$ 个，直接从 $1$ 到 $n$ 依次做即可。
:::