组合计数

到处都能见到它的身影，它是一切数数题的基础。

概念基础

基本定义与一些常见公式与方法。

排列数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照一定的顺序排成一列，方案个数记作 $A_{n}^{m}$，有 $A_{n}^{m}=\cfrac{n!}{(n-m)!}$。

一个有限集合 $S$ 到自身的双射称为 $S$ 的一个置换，集合 $S={a_1,\cdots,a_n}$ 的置换可以表示为：

$$f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}$$

是将 $a_i$ 映射为 $a_{p_i}$，这样 $p$ 是 $1\cdots n$ 的一个排列，$S$ 上的所有置换的数量为 $n!$。

置换的过程可以使用有向图来理解，连边 $i\rightarrow p_i$，就是所有点移动 $1$ 的距离。置换中形成一个环的称为置换环，对于大小为 $1,2$ 的置换环，原排列和置换显然是一样的。

对于两个置换 $f,g$ 的乘积记作 $f\circ g$，代表先通过 $f$ 的映射，再通过 $g$ 的映射。

一个排列中的逆序对个数，也叫做反序数，如果是偶数就是偶排列，奇数则是奇排列。

对于一个排列 $1,\cdots,n$，如果将任意两个数 $i,j$ 交换，其它数保持不动，就会得到一个新的排列，那么这样一个变换叫做对换，用 $(i,j)$ 表示。

组合数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照任意的顺序组成一个集合，方案个数记作 $\binom n m$。组合数同时也是二项式系数，当 $m<0$ 时，组合数没有定义。

$$\binom n m = \frac{n!}{(n-m)!m!}=\frac {n^{\underline m}} {m!}\\ \binom n m = \binom {n-1} m + \binom {n-1}{m-1}$$

组合数有以下性质 / 恒等式：

1. $\dbinom n m = \dbinom n {n - m}$；
2. $\dbinom{n}{k}=\cfrac{n-k+1}{k}\dbinom{n}{k-1}$，常被用来递推组合数；
3. $\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}$；
4. 吸收恒等式：$\dbinom{r}{k}=\dfrac{r}{k}\dbinom{r-1}{k-1}$，当二项式外有一个无用的系数时，我们可以将它“吸收”进二项式系数。
5. 下指标求和（行求和）：$\displaystyle \sum_{i=0}^{n}\binom{n}{i}=2^n$，相当于是二项式定理中 $a=b=1$。注意这个东西是很特殊的完整一行，一般的行求和是无法快速计算的。它还有变式：
   • $\displaystyle \sum_{i=0}^{n}(-1)^i\binom{n}{i}=0$，这是二项式定理中 $a=1,b=-1$；
   • $\displaystyle \sum_{i=0}^{n}i\times \binom{n}{i}=n2^{n-1}$，因为 $m\times \dbinom{n}{m}=n\times \dbinom{n-1}{m-1}$。
6. 上指标求和（列求和）：$\displaystyle \sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}$，可以看作是枚举第 $m+1$ 个数的位置 $i+1$。
7. 对角线求和：$\displaystyle\sum_{i=0}^{n}\binom{m+i}{i}=\binom{m+n+1}{n}$，反复利用 $C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$ 即可证明。
8. 范德蒙德卷积：$\displaystyle \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$。从组合意义上很容易证明（枚举 $n$ 和 $m$ 中选的个数），常用于合并组合数，考虑它的推论：
   • $\displaystyle \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$，证明很简单，因为 $\dbinom{n}{i-1}=\dbinom{n}{n-i+1},\dbinom{2n}{n-1}=\dbinom{2n}{n+1}$；
   • $\displaystyle\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$，证明基本同理；
   • $\displaystyle\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}$，这个也是网格图路径计数方案。
9. Lucas 定理。若 $p$ 是质数，则 $\displaystyle\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$，常用于 $p$ 较小的情况。
10. 组合数奇偶性公式。$\displaystyle \binom{n}{m}\equiv 1 \pmod 2 \iff n\ \& \ m=m$，使用 Lucas 定理来证明，需保证不出现 $\dbinom{0}{1}$。
11. Kummer 定理。$\dbinom{n+m}{n}$ 中质因子 $p$ 的次数为 $n+m$ 在计算时 $p$ 进制意义下的进位次数，等价于 $\dbinom n m$ 中质因子 $p$ 的次数等于在计算 $n-m$ 时 $p$ 进制意义下的借位次数。其中 $p$ 是素数。
12. 上指标翻转。$\displaystyle \binom n k = (-1)^k\binom{k-n-1}{k}$。

多重组合数。是指先选 $n_1$，再选 $n_2$，以此类推。有（$\sum n_i = n$）：

$$\binom{n}{n_1,\dots,n_k}=\frac{n!}{\prod_{i=1}^k n_i!}$$

组合方法。在小学学过一些常用的组合方法。