排列与组合

本节导读

从这一节起进入组合数学，大纲列了四个单元：排列与组合、母函数与递推关系、容斥原理和鸽巢原理、Polya 定理。本节讲第一个单元的七条：加法法则与乘法法则、排列与组合、Stirling 近似公式、排列的生成算法、组合的生成算法、可重组合、若干等式及其组合意义。

组合计数题常以填空出现，要求写出具体的数；也有「用组合意义证明一个等式」这样的证明题。计数题最怕重复和遗漏，所以本节反复强调一个习惯：先说清「一个方案是什么」，再决定是分类相加还是分步相乘。学完你应该能把一个计数问题对应到下表的某个公式上，并会手工推出字典序的下一个排列和下一个组合。

加法法则与乘法法则

完成一件事有几类办法，各类互不重叠，总方法数等于各类方法数之和，这是加法法则；完成一件事要分几步，每一步的方法数不受前面怎么选的影响，总方法数等于各步方法数之积，这是乘法法则。用之前先自问两句：分类有没有重叠或遗漏？各步是不是真的互不影响？

排列、组合与可重组合的公式

问题	方法数
从 n 个不同元素中取 r 个排成一列	$P(n, r) = \frac{n!}{(n-r)!}$P(n,r)=(n−r)!n!​
每次可以重复取，取 r 个排成一列	$n^r$nr
n 个不同元素排成一圈（旋转算同一种）	$(n-1)!$(n−1)!
多重集：$n_1$n1​ 个第一类、…、$n_k$nk​ 个第 k 类，共 n 个全排列	$\frac{n!}{n_1! \, n_2! \cdots n_k!}$n1​!n2​!⋯nk​!n!​
从 n 个不同元素中取 r 个，不计顺序	$C(n, r) = \frac{n!}{r!(n-r)!}$C(n,r)=r!(n−r)!n!​
从 n 类元素中可重复地取 r 个（可重组合）	$C(n + r - 1, r)$C(n+r−1,r)
$x_1 + \cdots + x_n = r$x1​+⋯+xn​=r 的非负整数解	$C(n + r - 1, r)$C(n+r−1,r)
$x_1 + \cdots + x_n = r$x1​+⋯+xn​=r 的正整数解	$C(r - 1, n - 1)$C(r−1,n−1)
从 $1, 2, \ldots, n$1,2,…,n 中取 r 个互不相邻的数	$C(n - r + 1, r)$C(n−r+1,r)
平面格路：从 (0, 0) 每步向右或向上走到 (m, n)	$C(m + n, m)$C(m+n,m)

可重组合的公式来自「隔板法」：r 个相同的球放进 n 个盒子，相当于 r 个球和 n − 1 块隔板排成一列，选出隔板的位置。方程的解有下界时，先把下界减掉，化成非负整数解再套公式；比如 $x_i \ge 1$xi​≥1 时令 $y_i = x_i - 1$yi​=xi​−1，就得到正整数解的公式。

Stirling 近似公式

n 较大时直接算 $n!$n! 很麻烦，可以用 Stirling 公式估计：

$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$n!≈2πn​(en​)n

比如 $10! = 3628800$10!=3628800，公式给出约 3598696，相对误差约 0.83%。n 越大，相对误差越小（大约是 $\frac{1}{12n}$12n1​）；但绝对误差会越来越大，所以它只用来估计数量级和比值。

排列与组合的生成算法

字典序法求下一个排列，分四步：一，从右往左找第一个比右边邻居小的数 $p_i$pi​；二，再从右往左找第一个比 $p_i$pi​ 大的数 $p_j$pj​；三，交换 $p_i$pi​ 与 $p_j$pj​；四，把第 i 位之后的部分倒过来。例如 1432：$p_i = 1$pi​=1，比 1 大的最右边的数是 2，交换得 2431，把 431 倒过来，得 2134。

另一种常用的是邻位对换法：从 $12 \cdots n$12⋯n 开始，每个数带一个方向（开始都指向左），比所指方向的邻居大的数叫「活动」的数；每一步把最大的活动数与它所指的邻居对换，再把所有比它大的数调转方向。它的特点是相邻两个排列只差一次邻位对换。此外还有递增进位制数法、递减进位制数法，把排列与一个变进制的数对应起来，按数加 1 生成下一个排列。

组合按字典序生成：把 r 元子集从小到大写成 $a_1 \lt a_2 \lt \cdots \lt a_r$a1​<a2​<⋯<ar​，从右往左找第一个满足 $a_i \lt n - r + i$ai​<n−r+i 的位置，把 $a_i$ai​ 加 1，后面依次写成前一个数加 1。例如 $\{1, \ldots, 5\}${1,…,5} 的 3 元子集，{1, 4, 5} 的下一个：$a_3 = 5$a3​=5、$a_2 = 4$a2​=4 都已到上限，$a_1 = 1 \lt 3$a1​=1<3，加 1 得 2，后面写 3、4，得 {2, 3, 4}。