组合数学总结

本文移植自个人的原博客（原文）

基本原理

加法原理

做一件事情，完成它有$N$类方式，第一类方式有$M_1$种方法，第二类方式有$M_2$种方法，…，第$N$类方式有$M_N$种方法，那么完成这件事情共有$M_1+M_2+…+M_N$种方法。

乘法原理

做一件事，完成它需要分成$n$个步骤，做第一步有$m_1$种不同的方法，做第二步有$m_2$种不同的方法，…，做第$n$步有$m_n$种不同的方法。那么完成这件事共有$m_1×m_2×m_3×…×m_n$种不同的方法。

排列数

从$n$个不同元素中任取$r(r≦n)$个元素排成一列（考虑元素先后出现次序）称此为一个排列，此种排列的总数即为排列数，即叫做从$n$个不同元素中取出$r$个元素的排列数，记为$A(n,r)$。

对于$A(n,r)$，第一个元素有$n$种取法，第二个元素有$n−1$种取法，…，第$r$个元素有$n−r+1$种取法，则根据乘法原理可得通项公式。

$$A(n,r)=\frac {n!} {(n−r)!}$$

组合数

从$n$个不同元素中，任取$m(m≤n)$个元素并成一组，叫做从$n$个不同元素中取出$m$个元素的一个组合；从$n$个不同元素中取出$m(m≤n)$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数，记为 $C(n, m)$ 。

根据定义，可知组合数与排列数的不同便是组合数对顺序没有要求。对组合数来说 $1,2,3$ 与 $1,3,2$ 是一种组合，但 对排列数则不是。那么在组合数中重复计算的次数即为 $r$ 的全排列

则有

$$C(n, r)=\frac{A(n, r)}{r !}$$

即

$$C(n, r)=\frac{n !}{r !(n-r) !}$$

常见定理与组合论证

$$\text { 1. } C(n, r)=C(n, n-r)$$

将其表示为一个长度为 $n$ 的二进制串，则组合数为有 $r$ 位为 1 的串的个数，易知其与有 $n-r$ 位为 0 的串的个数等价。

$$\text { 2. } C(n, r)=C(n-1, r-1)+C(n-1, r)$$

将其表示为一个长度为 $n$ 的二进制串，利用动态规划的思想，可设 $C(n-1, r-1)$ 表示长度为 $n-1$ 的串且在末尾新加入一个$1$的方案数， $C(n-1, r)$ 表示长度为 $n-1$ 的串且在末尾新加入一个$0$，易证该递推式的正确性。（初始化为 $C(i, i)=0$）

$$\text { 3. }2^{n}=\sum_{k} C(n, k)$$

$2^{n}$ 为长度为 $n$ 的二进制串的总方案数，根据加法原理，易知其等价于长度为 $n$ 的二进制串且有 $0,1,…,n$ 个 $1$ 的方案数和。

$$\text { 4. }(a+b)^{n}=\sum_{k} C(n, k) a^{k} b^{b-k}$$

这个定理同样可以直接通过二项式定理求证。

$$\text { 5. } C(n+m, r)=\sum_{k} C(n, k) * C(m, r-k)$$

左项可以表示为一个长度为 $a+b$ 的二进制串，右项则可以表示为一个长度为 $a$ 的二进制串拼上一个长度为 $b$ 的二进制串，此处可以转化为定理 $3$，再结合乘法原理即可得证。

$$\text { 6. }C(n, r)=\frac{n}{r}(n-1, r-1)$$

结合定理一，可以通过简单的推导得到该定理。

$$\text { 7. } C(n, m) C(m, r)=C(n, r) C(n-r, m-r)$$

可以将左式表示为在 $n$ 个学生中选出 $m$ 个组长，再在 $m$ 个组长中选出 $r$ 班干部，则右式可以表示为在 $n$ 个学生中选 $r$ 个班干部，再 在剩余的学生 $n-r$ 中选出 $m-r$ 个不是班干部的组长，易知两者等价。

可重复组合数

从 $n$ 个不同元素中，任取 $m(m \leq n)$ 个元素并成一组 (可以重复选择)，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个可重复组合；从 $n$ 个不同元素中取出 $m(m \leq n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的可重复组合数。

可重复组合即为

$$C(n+m-1, m)$$

对于此结论的证明可以逆向来看， $n$ 中选 $m$ 个元素即为将 $m$ 个球放在 $n$ 个盒子内的方案数，每个盒子中允许放 0 到 $m$ 个球。对于 这 $m$ 个球来说，即为 $n-1$ 个断点将其分为了 $n$ 部分。

不妨将断点用二进制串表示为 0 ，球表示为 1 ，那么在 3 个元素中选 5 个元素的一种方案即可表示为

$$1-1-1-0-1-0-1$$

易观察到可重复组合数等于在 $n+m-1$ 个元素中选取 $m$ 个 $1$ 的方案数

即为

$$C(n+m-1, m)$$

可重复组合数同样可以解决如下的问题:

已知

$$x_{1}+x_{2}+x_{3}+\ldots \ldots+x_{n}=m\left(x_{i}>=0\right)$$

求方程的解数。

此处可以看出答案即为 $C(n+m-1, m)$ ，论证方法同上，该问题同样有很多变式，如改变 $x_{i}$ 的取值范围等，同样可以通过如 上方式得解，此处不再赘述。

斯特林数

斯特林数分为第一类斯特林数和第二类斯特林数，其中第一类斯特林数为将$n$个物体排成$m$个非空循环排列的方案数，记为$s(n,m)$，第二类斯特林数为将$n$个物体划分到$m$个集合的方案数，记为$S(n,m)$。

第一类斯特林数

$s(n, m)$ 的递推公式:

$$s(n, m)=(n-1) * s(n-1, m)+s(n-1, m-1)(1<=m<=n-1)$$

边界条件:

$$s(n, n)=1(n>=0)$$

$$s(n, 0)=0(n>=1)$$

递推关系的说明:

考虑第 $n$ 个物品， $n$ 可以单独构成一个非空循环排列，这样前 $n-1$ 种物品构成 $m-1$ 个非空循环排列，方法数 为 $s(n-1, m-1)$ 。

也可以前 $n-1$ 种物品构成 $m$ 个非空循环排列，而第 $n$ 个物品揷入第 $i$ 个物品的左边，这有 $(n-1) \times s(n-1, m)$ 种方法。

第二类斯特林数

$S(n, m)$ 的递推公式是:

$$S(n, m)=m \times S(n-1, m)+S(n-1, m-1)(1<=m<=n-1)$$

边界条件:

$$s(n, n)=1(n>=0)$$

$$s(n, 0)=0(n>=1)$$

递推关系的说明:

考虑第 $n$ 个物品， $n$ 可以单独构成一个非空集合，此时前 $n-1$ 个物品构成 $m-1$ 个非空的不可辨别的集合，方法数 为 $S(n-1, m-1)$ ；

也可以前 $n-1$ 种物品构成 $m$ 个非空的不可辨别的集合，第 $n$ 个物品放入任意一个中，这样有 $m \times S(n-1, m)$ 种方法。

第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同，两者在计数问题中均有着广泛的运用。

卡特兰数

一个栈(无穷大)的进栈序列为 $1 , 2 , 3 , \ldots, n$ ，有多少个不同的出栈序列?

该答案的解即为卡特兰数。实际上，卡特兰数也同样可以表示为有 $n$ 个节点的无标号树的个数，汉诺塔问题的解，括号表达式的方案数，凸多边形的三角划分数等等，在组合数学中有着广泛的应用。

令$h(0)=1, h(1)=1$, 则卡特兰数数满足递推式:

$$h(n)=h(0) \times h(n-1)+h(1) \times h(n-2)+\ldots+h(n-1) \times h(0)(n>=2)$$

亦或

$$h(n)=h(n-1) \times(4 \times n-2) /(n+1)$$

同样可以用组合数表示

$$h(n)=\frac{C(2 n, n)}{n+1}$$

或者

$$h(n)=C(2 n, n)-C(2 n, n-1)$$

证明可以将出栈入栈的操作集合，看作一个长度为 $2 n$ 的二进制串，$0$代表入栈操作，$1$代表出栈操作，则该字符串有两个限制：$0$和$1$的个数相同（即对应每个元素只能入栈出栈一次），对于所有前缀，$0$的个数要大于等于$1$的个数（对应栈为空时不能继续出栈)。

先求出只满足第一个限制的方案数，易知其为 $C(2 n, n)$ 。

再考虑第二个限制需要排除的方案，易知其前缀必有一处 $1$ 的个数大于 $0$ 的个数，可设此处有 $k$ 个 $0$，$k+1$ 个 $1$ ，剩下的串中 有 $n-k$ 个 $0$，$n-k-1$ 个 $1$ ，将剩下的串按位取反，则得到的新串中共有 $n-1$ 个 $0$，$n+1$ 个 $1$ ，这样的串共有 $C(2 n, n-1)$ 。

则有

$$h(n)=C(2 n, n)-C(2 n, n-1)$$

以上的组合论证均涉及模型的转化，实际上，模型的建立在组合论证中具有重要的作用，模型需要满足尽可能简化问题，确保与 原问题等价等条件，才能优美地求解。

容斥原理

在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

易知

则通项公式表示为

（在个人讲课ppt中有着详细的证明，后续会整理到博客中）

错排公式

错排是给定原顺序（一般为有序数列），求每个元素都不在原位置的排列方案数。
递推式为：

$$D(n)=(n−1)*(D(n−2)+D(n−1))$$

初始条件为：

$$D(1)=0$$

$$D(2)=1$$