组合数学知识点入门

· · 算法·理论

第一次写了一万多字。

这篇文章简要介绍了提高级及以下（？）的一些组合数学的知识点。一般来说，我对“组合数学题”的定义比较宽泛，一般的数数题，只要出现了任何公式，我都将其定义为一道“组合数学（有关）题”，但这些非纯数学的组合数学题并不在本文介绍的范围内。

准备出发

在学习组合数学前，我们回顾一下需要用到的基本知识。

数论相关的定理

有的时候合理运用这些定理可以化简式子，优化程序的时间复杂度。这里不给出证明。

费马小定理

对于质数 p，有 a^{p-1}\equiv1\pmod{p}，这里 a 是任意正整数。这个定理通常变形成 a^{p-2}\equiv a^{-1} 用于快速幂求逆元，但是也可以用于缩小幂运算中指数的规模。例如，n^m\bmod p 中 m 很大，我们就可以把 m 变为 m\bmod(p-1)。

Wilson 定理

对于质数 p，有 (p-1)!\equiv-1\pmod{p}。这个定理和阶乘相关所以放过来了，但是实际上在组合数学中用的并不多（不在组合数学中用的也不多）。

Lucas 定理

这个有用。对于质数 p，\begin{pmatrix}n \\m\end{pmatrix}\equiv\begin{pmatrix}\lfloor\frac{n}{p}\rfloor \\\lfloor\frac{m}{p}\rfloor \end{pmatrix}\begin{pmatrix}n\bmod p \\m\bmod p \end{pmatrix}\pmod{p}。这样来，当 p 不大的时候，你就可以在 O(p) 内预处理出所有的 \begin{pmatrix}n\bmod p \\m\bmod p\end{pmatrix}（具体方法在下面），然后在 O(\log_p n) 内求出组合数。

逆元

组合数学题的答案一般都很大，难免需要取模；式子又需要乘除，这时候我们就需要逆元来应对除法了。

求逆元有三种常用的方法：快速幂、转化为同余方程（一般使用 exgcd 解决）、线性递推。线性递推是最快的，快速幂不仅可以求逆元还可以求幂，因此最没用的 exgcd 很少被使用。

快速幂

利用了费马小定理 a^{p-1}\equiv1\pmod{p}，于是 a^{p-2}\equiv a^{-1}。接下来我们只需要快速求出 a^{p-2}，我们可以将 p-2 进行二进制拆分或者利用 a^{2k}=a^k\times a^k 和 a^{2k+1}=a\times a^k\times a^k 来在 O(\log p) 求出逆元，这被称为快速幂。

线性递推

它可以在 O(n) 内求出 1 至 n 的所有数的逆元，在无法承受 O(\log p) 的单次查询或者想要顺便预处理阶乘逆元的时候常用。

我们考虑带余除法：m\lfloor\frac{p}{m}\rfloor+p\bmod m=p。

改成模的形式：m\lfloor\frac{p}{m}\rfloor+p\bmod m\equiv0\pmod{p}。

同乘 m^{-1}(p\bmod m)^{-1}：(p\bmod m)^{-1}\lfloor\frac{p}{m}\rfloor+m^{-1}\equiv 0\pmod{p}。

变形得到 m^{-1}\equiv -(p\bmod m)^{-1}\lfloor\frac{p}{m}\rfloor，于是我们就可以 O(n) 递推求出 1 至 n 的所有数的逆元，结合 (n!)^{-1}\equiv[(n-1)!]^{-1}n^{-1}\pmod{p} 还可以同时递推出阶乘逆元。

排列组合

在这一章节，我们将介绍排列组合的基本知识以及一些基本的运用方法。

基础

加法原理

如果你干一件事有 n 种方法，第 i 个方法有 a_i 种做法，那么你总共有 \sum a_i 种做法。

乘法原理

如果你干一件事要分 n 步，每步有 a_i 种做法，那么总共有 \prod a_i 种做法。

排列

从 n 个东西里面挑出 m 个，考虑顺序，那么有 A_n^m=\frac{n!}{(n-m)!} 种挑法。

A_n^n=n!

组合

从 n 个东西里面挑出 m 个，不考虑顺序，那么有 C_n^m=\begin{pmatrix}n \\m\end{pmatrix}=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!} 种挑法。

\begin{pmatrix}n \\m\end{pmatrix}=\begin{pmatrix}n \\n-m\end{pmatrix} \begin{pmatrix}n \\0\end{pmatrix}=\begin{pmatrix}n \\n\end{pmatrix}=1 \begin{pmatrix}n \\m\end{pmatrix}=\begin{pmatrix}n-1 \\m\end{pmatrix}+\begin{pmatrix}n-1 \\m-1\end{pmatrix}

:::info[P2181 对角线] 对于一个 n 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如，6 边形：

:::

:::info 不是所有对角线都能相交。我们需要用一种其他的方法来表示交点。 :::

:::success[正解] 我们可以发现，四个顶点刚好可以形成一个交点。那么交点数就是“从所有顶点内选出四个，不考虑顺序”的方案数，即 \begin{pmatrix} n \\4\end{pmatrix}。注意溢出。 :::

插板法

:::info[例题] 有 n 个男生和 m 个女生排成一排（考虑顺序），但是男生不可以放在一起。有几种排法？ :::

:::info 我们可以考虑先把女生排好，再选择男生的位置。 :::

:::success[正解] 先排好女生有 A_m^m=m! 种方法，接下来考虑把男生放进女生中间。具体地，男生总共可以放进 m+1 个空里，而且两个男生不可以放进同一个空内。这使得男生的排法有 A_{m+1}^n 种，总排法数就是 m!A_{m+1}^n。 :::

:::info[例题] 把 n 分成不超过 k 个正整数的和（考虑顺序），有几种分法？ :::

:::info 分成不超过 k 个正整数就相当于分成 k 个非负整数。 :::

:::success[正解] 我们考虑将 n 个小球里面放入 k-1 个其他小球，这会把序列分成 k 段。那么，问题就变为了：从 n+k-1 个小球中选出 k-1 个小球的方案数，即 \begin{pmatrix}n+k-1 \\k-1\end{pmatrix}。 :::

捆绑法

:::info[例题] 有 n 个男生和 m 个女生排成一排（考虑顺序），但是女生一定要放在一起。有几种排法？ :::

:::info 把女生当成一个整体再考虑。 :::

:::success[正解] 捆绑完共有 n+1 个，他们的方案有 (n+1)! 种，女生内部的方案又有 m! 种，所以总方案数就是 (n+1)!m! 种。 :::

容斥原理

经常和其他东西套在一起，可以很难。

引入

:::info[例题] 班上有 n 个学生学 OI，m 个学生学 MO，k 个学生学了 OI 又学 MO，那么总共有多少学生学 OI 或者 MO？ :::

:::success[正解] 很好想到把学 OI 的和学 MO 的人数加起来，但是既学 OI 又学 MO 的人被多算了一次，所以总答案是 n+m-k。 :::

:::info[例题] 班上有 a 个学生学 OI，b 个学生学 MO，c 个学生学 PHO，d 个学生又学 OI 又学 MO，e 个学生又学 OI又学 PHO，f 个学生又学 MO 又学 PHO，最后还有 g 个学生同时学了 OI 和 MO 和 PHO，那么总共有多少学生学 OI 或者 MO 或者 PHO？ :::

:::success[正解] 同样的，把 a,b,c 加起来，学两项竞赛的就被多算了一次，学三项的被多算了两次，于是我们把 d,e,f 减掉，但这下学三项的被少算了，于是我们把 g 加回来。a+b+c-d-e-f+g 即为答案。 :::

一般化

寻找规律。一般地，如果元素（一般放在全集 U 中，例如班级中的所有人）可以有 n 种属性（学各种竞赛），组成集合 A_1,A_2\cdots A_n，那么有： `

|\bigcup A_i|=(-1)^{1-1}\sum_i|A_i|+(-1)^{2-1}\sum_{i<j}|A_i\cap A_j|+(-1)^{3-1}\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\cdots+(-1)^{n-1}\bigcap A

练习

:::info[P1450 [HAOI2008] 硬币购物] 共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。 :::

:::info 如果我们直接多重背包的话时间复杂度是难以接受的。硬币的限制很烦人，我们可以假设成完全背包，然后再一步步改进？ :::

:::success[正解] 完全背包得到的答案肯定是多的，我们要把多的部分减掉。我们可以求第 i 种硬币不合法的方案数，第 i,j 种硬币都不合法的方案数，第 i,j,k 种硬币都不合法的方案数……然后容斥。我们强制某种硬币不合法就相当于我们提前花掉了所有这种硬币多一。 :::

各种数

卡特兰数

有非常多变形。由于非常常用，如果你看到（或者打表打出来了）一串以 1,1,2,5,14,42,\cdots 开头的数就可以基本确定这是卡特兰数。

最经典的例子之一是，从 (0,0) 开始，不断向右或上走 n 次而不越过 y=x 的方法数。但是，如果要理解更多例子，我们可以旋转一下图：从 (0,0) 开始，不断向右上或左下走，不越过水平轴的方法数。这就相当于从 0 开始向上或下随机游走而不到 0 以下。

公式

卡特兰数最经典，也是最常用的递推公式是这个：

C_x=\begin{cases}1 & \text{ if } x=0 \\\sum_{i=0}^{x-1}C_iC_{x-i-1} & \text{ if } x\geq1\end{cases}

此外，还有一些公式。

C_x=\dfrac{1}{x+1}\begin{pmatrix}2x \\x\end{pmatrix} C_x=\begin{pmatrix}2x \\x\end{pmatrix}-\begin{pmatrix}2x \\x-1\end{pmatrix} C_x=\frac{4x-2}{x+1}C_{x-1}

经典例题

这里引用了我很早之前的一篇文章。

P1044 [NOIP2003 普及组] 栈

题意简述：

依次在栈里面放入 n 个数，求有多少种合法的出栈序列。

我们考虑把这道题和网格路径题进行转化。很显然在任意时刻栈的大小都不能是负数，也就是说进栈的数量要始终大于等于出栈的数量，所以进栈就对应于往右走，出栈就对应往上走。答案就是 C_n。

P1722 矩阵 II

题意简述：

你现在有 n 个红和 n 个黑，问有多少个长度为 2n 的红黑序列，使得序列的任意一个前缀中红的个数都大于等于黑的个数。

很显然，红对应进栈，黑对应出栈，序列的任意一个前缀中红的个数都大于等于黑的个数对应栈的数量要始终大于等于出栈的数量，结束。答案是 C_n。

括号匹配

你现在有 n 个左括号和 n 个右括号，问有多少个长度为 2n 的括号序列，使得括号可以成功匹配。

很显然，由于左括号数和右括号数相等，一个可以成功匹配的括号序列的每一个前缀中左括号的个数都大于等于右括号的个数。即不可以有这种情况：[已经匹配成功的序列/空序列]+一个/多个)，这样子是无论如何都无法匹配成功的。所以我们把左括号转化成上一题的红，右括号转化成上一题的黑，整个问题都化为了上一题。结束。答案是 C_n。

不相交弦问题（P1375 小猫，P1976 鸡蛋饼）

每次连线都会把图劈成两块。

P1754 球迷购票问题

题意简述：每位购票者限购一张门票，且每张票售价为 50 元。在排成长龙的球迷中有 n 个人手持面值 50 元的钱币，另有 n 个人手持面值 100 元的钱币。假设售票处在开始售票时没有零钱。试问这 2n 个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。 例如当 n=2 时，用A表示手持 50 元面值的球迷，用B表示手持 100 元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。第一种：\mathtt{[A,A,B,B]}；第二种：\mathtt{[A,B,A,B]}。对于给定的 n，计算 2n 个球迷有多少种排队方式，可以使售票处不至于找不出钱。

前两题都不那么轻松，这题来了个简单的。每一个A都是给售货员一张零钱，每一 B都是拿走一张零钱。说白点，每一个A都是进栈，每一个B都是出栈。结束。

二叉树问题

题目简述：求用 n 个点能组建多少种二叉树，注意 n 个点要全用上。

很显然，对于 n=0,1 答案都是 1。

对于其他情况，我们枚举左右子树节点数的个数。我们设答案为 f_n，很显然的对于在根节点的左子数放 i-1 个节点并在右子树放 n-i 个节点的情况数就是 f_{i-1}f_{n-i}。我们写出 f 的完整递推公式：

f_n=\begin{cases}1 & n=0,1 \\\sum_{i=1}^nf_{i-1}f_{n-i} & n\leq2,n\in N_+\end{cases}

这不卡特兰数吗，怎么改名了？

凸多边形三角划分问题

题目简述：一个凸的 n 边形，要用线段连接它的两个顶点，使之分成多个三角形，每条线段不能相交，问一共有多少种划分方案。

类似的，我们可以枚举一条线段两侧的顶点数，写出答案的递推公式：

f_n=\begin{cases}1 & n=0,1 \\\sum_{i=1}^nf_{i-1}f_{n-i} & n\leq2,n\in N_+\end{cases}

没新意，下一个。

P2532 [AHOI2012] 树屋阶梯

由于题目是图片，没法ctrlCV，直接放图了：

很显然阶梯的每一级都会被一个不同的矩形占住。然后我们考虑把阶梯角占住的那个矩形。它会切割这个阶梯，所以我们又能愉快的写公式了……

斯特林数

据说（？）很有用，但是我的能力还不足以用上它们。

二类

二类比一类有用。

第二类斯特林数的定义是这样的：把 n 个两两不同的元素无序分为 k 个非空子集的方案数，记为 \begin{Bmatrix}n\\k\end{Bmatrix}。

我们可以由组合意义得出递推式：

\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}

如果我们把一个新元素加进了原来的 n-1 个元素，我们有两种选择：单独放进一个子集，有 \begin{Bmatrix}n-1\\k-1\end{Bmatrix} 种方案，或者放进一个已有的子集，有 k\begin{Bmatrix}n-1\\k\end{Bmatrix} 种方案。

接下来我们试着推导通项公式。设 n 个不同的元素划成 k 个有序的可空集合的方法数为 G_k，不允许空集则为 F_k。显然， G_k=k^n 且 G_k=\sum_{i=0}^k \begin{pmatrix}k\\j\end{pmatrix}F_j。

二项式反演得到 F_k=\sum_{j=0}^i\dfrac{k!(-1)^{m-k}k^n}{j!(k-j)!}。

显然 F_j=k!\begin{Bmatrix}n\\k\end{Bmatrix}，因此得到通项公式：

\begin{Bmatrix}n\\k\end{Bmatrix}=\sum\limits_{i=0}^k\dfrac{(-1)^{k-i}i^n}{i!(k-i)!}

一类

一类斯特林数则是这样的：把 n 个两两不同的元素无序分为 k 个非空轮换的方案数，记为：\begin{bmatrix}n\\ k\end{bmatrix}。同样地，我们可以得出递推公式：\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}。

应用

我们可以用斯特林数转换上升指数幂 n^{\overline{k}}=\dfrac{(n+k-1)!}{(n-1)!} 或下降指数幂 n^{\underline{k}}=\dfrac{n!}{(n-k)!} 到普通幂。具体说：

x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}

其他

贝尔数

贝尔数是大小为 n 的几何的划分方法数。显然，贝尔数等于其对应的第二类斯特林数的和。

贝尔数有递推公式：B_{n+1}=\sum \begin{pmatrix}n\\i\end{pmatrix}B_i。

考虑新增的元素，如果它自己一个集合，那么有 B_n 种情况；如果它和一个元素一个集合，那么有 \begin{pmatrix}n\\n-1\end{pmatrix}B_{n-1} 种情况，以此类推。

你可以使每一行的行首等于上一步的末项，以此构造贝尔三角形，用来求贝尔数。

错排数

错排数是没有任何元素出现在其有序位置的排列的个数。利用容斥原理可以求出错排数 D_n=n!\frac{(-1)^k}{k!}。

对于 k 个不同的 i，“满足 A_i=i 的排列数”很显然是好求的，它等于

\begin{pmatrix}n \\k\end{pmatrix}(n-k)!

（有 \begin{pmatrix}n \\k\end{pmatrix} 种 i 的组合，而每种组合有 (n-k)! 种排列）。

我们知道：

\begin{pmatrix}n \\k\end{pmatrix}=\dfrac{n!}{k!(n-k)!}

（这是组合数公式），于是我们就可以把这个式子化简为 \dfrac{n!}{k!}。代入容斥，我们得到：

D_n=\sum_{k=0}^n \dfrac{n!(-1)^k}{k!}

把 n! 提出来可以得到：

D_n=n!\sum_{k=0}^n \dfrac{(-1)^k}{k!}

也有递推公式：

D_n=(n-1)(D_{n-2}+D_{n-1})

如果前面所有数都错位了，那么新的数找随便一个数交换位置即可；如果前面所有数只有一个数在原位，那么把在原位的那个数与新数交换即可变成错位排列。

还有另一个递推公式：

D_n=nD_{-1}+(-1)^n

有一个很神奇的事是 D_n=\lfloor\dfrac{n!}{e}+\dfrac{1}{2}\rfloor(n\geq1)。接下来证明一下：

比较敏锐的读者可能已经观察到了

\sum_{k=0}^n \dfrac{(-1)^k}{k!}

的形式有点像

e^x=\sum_{k=0} \dfrac{x^k}{k!}

，所以如果令 R_k 为 e^{-1} 和它的前 k 次泰勒展开的差的话，我们就有：

D_n=n!(e^{-1}-R_k)

事实上，这个余项 R_k 是一个交错级数，由莱布尼茨判别法可得：

R_k\leq \dfrac{1}{(k+1)!}

而对于 n\geq1，我们有：

n!R_n\leq\dfrac{1}{n+1}=\dfrac{1}{2}

这意味着 n!e^{-1}=\dfrac{n!}{e} 在 n\geq 1 时是 D_n 的一个很好的近似，误差不超过 \dfrac{1}{2}。于是我们只要对其进行一些修正就可以得到 D_n=\lfloor\dfrac{n!}{e}+\dfrac{1}{2}\rfloor。证毕。

事实上由于 e 是一个无理数且直接递推 D_n 不比算 n! 慢多少，这个公式在 OI 中几乎无用（如果有谁找到了用途欢迎来私信讨论）,但反正挺好玩。

小练习：箱球模型

箱球模型是这样一类问题：把 n 个球放进 m 个箱子，区分/不区分箱子；区分/不区分球；允许/不允许空箱。八个问题！这里同样引自我很早之前的一篇文章，没有经过事实审查，有误指出。

球不同，箱不同，允许空

很简单。对于每一个球，我们可以把它放进 k 个箱子中的任意一个，易得答案为 k^n。

球同，箱不同，不允许空箱

也是很简单。注意到球是相同的，所以我们可以把球排成一列，名字都叫没有差别小球球，都是一家人，顺序不重要，只要是一列就好。然后我们可以把 k 个箱子转化为 k-1 个隔板，隔板只可以插到在两个小球之间的地方（边缘就不能插），也不可以和其他的隔板抢位置，这样就不会隔出空的箱子。同时隔板是有顺序的，不然就会有一堆重复计数。所以是 C，不是 A。答案：C_{n-1}^{k+1}。

球同，箱不同，允许空箱

和 第二问 很像，但是箱子能空箱。空箱实在是太难办了，于是我们考虑惩罚箱子。我们可以硬送给箱子一个小球，但是那样我们就会WA，所以让我们把题目改成：有 n+k 个小球， k 个箱子，球同，箱不同，不允许空箱。如果箱子想在原来的题目里空箱的话只需要在新题里只留一个我们送箱子的小球就行了。答案： C_{n+k-1}^{k-1}

球不同，箱同，不允许空箱

很显然，这是第二类斯特林数。

球不同，箱不同，不允许空箱

我们发现它与 第四问 的区别仅在箱子不同了。我们只要在4的基础上乘上一个 k! 就行了。或者把第二类斯特林数的通项公式里那个用来去重的 \frac{1}{k!} 删掉就行了。答案 k!\begin{Bmatrix} n\\k \end{Bmatrix}=\sum_{i=0}^{k}(-1)^iC_k^i(k-i)^n。

球不同，箱同，允许空箱

我们发现它与 4 的区别仅在允许空箱。于是我们考虑枚举有多少个箱子是非空的。最后求和就行。答案：

\sum_{i=1}^{k}\begin{Bmatrix} n\\i \end{Bmatrix}

球同，箱同，允许/不允许空箱

这不是拆数问题吗？

我们只需要求出递推公式，对于答案的具体求值，我们可以使用 DP。不过由于这个 DP 太简单了，说是递推也可以。

先给第七题答案：

B1(n,k)=\begin{cases} 1 & n=0\vee k=1 \\ 0 & k=0\wedge n\ne 0 \\ B1(n,n) & n<k \\ B1(n-k,k)+B1(n,k-1) & \text{otherwise} \end{cases}

第一项的意思是说“如果一个小球都没有的话，那就只有一种方法：不放；如果只有一个箱子的话也只有一个方法：把所有小球都放进去”，第二项的意思是说“如果一个箱子都没有，还要放球进去的话，那肯定是不可能的”，第三项的意思就是“如果球比箱子还少，那就把一定没用的箱子丢了，反正箱子都一样”，而第四项的意思就是“我们可以把盒子放满，如果不想放满也是可以的”。

接下来是第八题的答案：

\begin{cases} 1 & n=0\wedge k=0\\ 0 & (k=0\oplus n=0) \vee n<k\\ B1(n-k,k) & \text{otherwise} \end{cases}

第一项的意思就是说“如果没有箱子也没有小球，那唯一一种方法就是啥也不干”，第二项的意思是说“如果没箱子或者没小球而且还不是箱子小球一起没有的话。那压根不可能。如果小球比箱子还少，那就一定有空箱，也是不符合要求的。”，第三项说的是“我们可以考虑先给每个箱子配一个小球，接下来问题就变成了第七问的问题。”