计数总结

巨长还没人看的笔记第二弹。

本文md源码全长超过25KB/900行，除非有时间并不建议完整阅读而是通过Ctrl+F查找想阅读的部分

建议在食用前熟读本博客的数论总结一文中的同余部分。

排列与组合

加法原理与乘法原理

加法原理：假设我们要做一件事情，有类方法，每类方法有种，则一共有种做这件事情的方案。

乘法原理：假设我们要做一件事情，有个步骤，每步方法有种，则一共有种做这件事情的方案。

排列与组合

排列数

有个球，从其中按顺序选出个并按一定顺序排列的方案数，记作。

可以轻易地推导排列的计算公式：

理解：取第次时剩下个球，直接乘即可。

组合数

在个球中选择个（忽略选取顺序）的方案数，记作或。下文中都将采取后一种记法。

组合数的公式也很容易推导。

理解：我们选择的个球有种排列顺序。

一般而言我们都不使用排列而是使用组合，因为组合转排列只需要乘而排列转阶乘需要除，在取模横行的 OI 界相当不友好；并且大部分题目要求的也是组合数。

特别的，当时，。

多重集的排列数/多重组合数

考虑一个多重集有种个元素，第种元素有个。

则此多重集的全排列数/多重组合数为：

记作。

理解：

我们并不关心相同种类的元素的顺序，因此每一种都要除以。
可以理解为：有个球，第次选取其中没有选过的个球涂色，求最终方案数，答案即为

插板法

插板法一般用于求解元素划分问题，核心思想是考虑待求式的组合意义。

求下列方程的整解组数：

解：我们考虑方程的解数相当于下面这个情景：

有个球排成一排，你可以在任意两个球的空隙种插入板以把左右两边分开，一个空隙只能插一块板，求插块板方案数。

那么答案显然是。

求下列方程的整解组数：

看起来这个情景中没法插板了，因为一个空隙能插很多块板。

但是我们可以考虑变形：

这样就可以插板了。答案。

杨辉三角

懒得做图了。直接贺亿张 Wikipedia 的图。

上图即为杨辉三角，从第二行开始其每一个值都是其左上方和有右上方数的和（不存在即为）。

杨辉三角的性质：在左对齐后，第行第列的值即为。（见下图）

由此我们可以得出组合数的递推式：

这个公式也可以用组合意义理解：我们要考虑第个元素选不选，如果选则从转移；否则从转移。

严格的 proof 可以展开组合数。

此外我们还可以观察到：第行的和是，因此我们推出

二项式定理

proof可以用归纳。

理解：考虑组合意义，相当于在 $项$ 中选出个，其余选，这样就会组合出，而组合出的方案数为。

组合数的重要性质

下面这些式子基本上写作阶乘之后都一目了然，因此不再给出证明。

这些式子非常重要，大部分计数题基本上都只用得上这些，剩下的式子基本上都可以从这些推导出来，因此务必要熟悉。

对称式

理解：选个等同于选没选的个。

吸收式

或

我们也可以使下指标不变：

这个式子的意义在于可以将系数移入或移出组合数。

上指标求和（同列求和）

理解：从个元素中选择个，我们枚举选择的第个元素的位置即可。

组合数“约分”/三项式系数

前一个名字是我乱取的，主要真的很像约分啊。

理解：左式相当于在个球中选个再从这个里选个涂色的方案数，右式相当于先选个涂色，再从剩下的里面选个不选中（剩下的即为选中但不涂色）。

下指标卷积（范德蒙德卷积）

理解：在个元素中选个，将序列划为前个和后个，枚举前个里要选多少个即可。

变形：

上指标卷积

组合数的常用推导方式

组合意义：把抽象的组合式转化成等价的计数模型，再寻找这个计数模型的性质。
- 优点：理解直观，可能可以更快地发现一些关键性质
- 缺点：对思维要求较高，泛用性不强。
拆解组合数：把组合数拆解为阶乘式，可以在分子分母上同时乘一些其他的式子，并重新组合新的组合数。
- 优点：较为泛用，在不能用组合意义的时候有用；对思维要求没有组合意义高。
- 缺点：对计算能力和数学直觉要求高。

组合数的编程求法

根据题目要求，有以下几种求组合数的方法：

本文内容不包括exLucas，建议出模数不是质数数据范围还大的出题人干点人事

递推

直接使用递推式计算组合数。

const int M=1000;
int binom[M+5][M+5];
void getbinom(){
    for(int i=0;i<=M;++i)binom[i][0]=1;
    for(int i=1;i<=M;++i)
        for(int j=1;j<=i;++j)
            binom[i][j]=binom[i-1][j]+binom[i-1][j-1];
}

时间复杂度：预处理 + 查询

优点：代码简单，对模数没有要求，在需要大量查询的时候常数最小

缺点：只能处理较小（）的情况。

适用范围：较小的时候

预处理+阶乘式

当需要取模且模数为质数时，可以预处理的阶乘和阶乘的逆元。

const int P=1e9+7;
const int M=5e7;
int fac[M+5],inv[M+5];
void pre(){
    fac[0]=fac[1]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%P;
    for(int i=1;i<=n;++i)inv[i]=ksm(fac[i],P-2,P);//快速幂
}
int binom(int n,int m){
    return n>=0&&m>=0&&n>=m?1ll*fac[n]%P*inv[m]%P*inv[n-m]%P:0;
}

优化

ちょっと待って，这份代码是的，的时候真的不会出事吗？

会，因此我们可以考虑一个性质：

根据阶乘的定义即可证明。

因此我们就得到了一个递推式。我们只需要计算出然后递推计算就行了。

void pre(){
    fac[0]=fac[1]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=ksm(fac[n],n-2,P);
    for(int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%P;
}

时间复杂度：预处理 + 查询

优点：可以处理较大范围，代码简单

~~缺点：只能在模数为质数时使用~~

适用范围：范围较大（），且

卢卡斯定理

有时我们会遇到非常大的情况，如果此时模数较小且为质数就可以调用卢卡斯定理。

定理内容

由于这个式子还能递归，因此我们也可以换一种方式：

设在进制下第位的值为，则

proof

引理1：。

proof: 必定含有因子。

引理2：。

proof:我们考虑使用二项式定理：

我们观察右半边的第三项，其中包含，根据引理1这一项一定被整除。因此

我们接下来证明。

然后就可以开始归纳了。

我们现在正式开始证明。

我们设

根据二项式定理，中这一项的系数为，而同时

根据引理2有

我们已知的展开式中这一项的系数等于，而同时

而我们又有

因此我们抽出第个求和式中一项然后乘起来：

消掉一项：

证毕。

拓展

对于不是质数的情况，您要是真的想看的话出门左转 OI-Wiki。

时间复杂度：预处理 + 查询。

优点：可以求解很大的

缺点：~~只能在模数为质数时使用~~不适用很大的情况或很小查询很多的情况（后一种基本上不会出现）。

适用范围：

质因数分解

前置知识：阶乘的质因数分解

我们直接对三个数质因数分解然后对每个质因数分别乘起来即可。

时间复杂度：单次

优点：对模数没有要求，处理数据范围较大

缺点：多次查询复杂度高

适用范围：查询次数较少，左右

卷积快速幂

我们考虑下面这个下指标卷积：

于是我们可以设计一个快速计算的算法：用这个卷积先处理出等的值，然后将二进制拆分并用卷积式合并。

时间复杂度： ~~可用狒狒贴优化到~~

适用范围：巨大，但是很小（）

总结一下：

算法			特殊限制
递推	小	大	无	大
预处理阶乘	中	大		大
卢卡斯定理	大	中		大
质因数分解	中	大	无	小
卷积快速幂	大小	大	无	小
~~exLucas~~	大	~~大，要求最大质因数幂小~~	无	中

容斥原理

引入

一个班上有人，人喜欢篮球，人喜欢足球，那么既喜欢篮球又喜欢足球的人有个。

用数学的语言来讲，设表示喜欢篮球的人的集合，表示喜欢足球的集合，则

直观理解：被算了两次，要减掉一次。

子集容斥

三个集合的情况：

推广到个集合：

proof：我们考虑必须选择第个元素的方案数为

因此每个元素只被算了一次。

容斥原理的常用套路是把“至少”、“至多”与“恰好”互化，这样就可以用一些交集算并集或用并集算交集。

例子

求解下列方程的自然数解组数：

我们考虑表示至少个不符合要求的方案数，则答案为

我们考虑枚举每个表示集合内的数满足，则它对的贡献为

直接算即可。

二项式反演

证明直接暴力展开即可。

...所以这玩意是拿来干嘛的啊？

在做题的时候我们常常要计算“恰好满足”，但是“恰好满足”常常不好计算，而“至少满足”或“至多满足”反而更好计算。

此时我们可以用二项式反演。式子中表示“ 条限制中至少满足项限制”的方案数，表示“ 条限制恰好满足项限制”的方案数，因此左边是显而易见的。

这样我们就可以用“至少”与“恰好”互推了。

类似的，我们也可以用“至多”与“恰好”互推：

事实上二项式反演的本质也是容斥。下文不会特别区分“子集容斥”与二项式反演。

特殊的数

在 OI 中经常会遇到一些模型，这些模型往往都对应一种特殊的数且具有高度的类似性，掌握这些数的性质往往会对快速解题有帮助。

错排

定义一个排列是错排当且仅当对于任意都有。

求长为的错排数。

容斥计算

我们可以轻易地用子集容斥计算：定义为至少有个位置的方案数，则

所以答案即为

递推计算

我们考虑一个错排的具体问题：把锁和把钥匙编号为，编号为的锁只能被编号为的钥匙打开，问有多少种把钥匙和锁配对使得没有锁能被打开的方案数。

考虑递推计算。我们假设已经把编号为的锁和钥匙配对了，那么现在加入编号为的锁，我们有两种选项：

如果前面的钥匙全部不配对，那么随意选择一个钥匙与编号为的钥匙交换即可。这种情况会出现次，而交换方案数为种。
如果前面恰好有一把钥匙与锁配对，那么我们就可以把这两个钥匙交换就得到了错排。这种情况会出现次，而交换方案数为种。

综上我们得到了错排数递推式：

卡特兰数

卡特兰数（Catalan Number）的组合数形式与递推式如下：

其中取自然数。

的前几项为。

卡特兰数可能是 OI 中对应模型最多的特殊数了。下面这些都是卡特兰数的组合意义：

从出发走到，每次只能向上或向右，可以碰到但是不能穿过对角线，合法路径的条数。
长为的合法括号序列数。
依次进栈，合法的出栈序列数。
在圆上均匀选取个等距的点连条弦，这些弦互不相交的方案数。
个结点的二叉树的数量。
个结点的森林或个结点的树的数量。
凸边形的三角剖分方案数。
用边长为整数的矩形水平或竖直放置填满一个高为的楼梯的方案数（详见 AHOI2012 树屋阶梯）。

我们以第一个为例浅证一下。

先转化为“不能碰到 ”。做“不能碰到”比较难，我们考虑算“必须碰到”。

我们发现对于每一条碰到的路径，我们都可以沿着它第一次碰到的位置将其向上翻折：

这样每一种要碰到的方案就与走到的方案一一对应。

由于走到的方案数为，总方案数为，因此合法方案数为

斯特林数

第二类斯特林数

第二类斯特林数（Stirling Number）的组合意义：把个有标号的球放进个无标号的盒子里，不允许有空盒的方案数，记作

我们可以根据组合意义写出递推式：我们考虑怎么转移到一个合法的把个球放进个盒子的方案。

我们把第个球单独放进某个盒子，转移到。
我们把第个球放进之前的某个盒子，转移到，系数为。

因此递推式为

边界。

我们接下来考虑推导通项公式。

我们发现“不能有空盒”不太好计算，考虑容斥。

先把盒子暂时标号，设表示至少有个空盒的方案数，则

因此

贝尔数

贝尔数（Bell Number）：把个元素划分为若干个集合的方案数。

容易发现贝尔数就是同行斯特林数的和，即

我们考虑推导一个贝尔数的递推形式。

不难发现，我们只要枚举有多少元素和第个划在同一个集合里就行了。

因此

第一类斯特林数

第一类斯特林数的组合意义：把个元素划分成个无标号的圆排列的方案数（如与是同一种方案，但是与不是），记为

同样考虑递推：对于已有的个元素和个圆排列：

把第个元素新开一个圆排列。转移到。
把第个元素放到之前的排列里。转移到，系数为（注意不是，我们枚举的是把它放在哪个元素的后面）。

因此

边界。

第一类斯特林数没有通项公式。

上升幂与下降幂

我们定义的上升幂与下降幂如下：

容易发现。

斯特林数与上升幂&下降幂

斯特林数是用于沟通普通幂与升降幂的桥梁。

上升幂转化为普通幂：

下降幂转化为普通幂：

普通幂转化为上升幂：

普通幂转化为下降幂：

欧拉数

欧拉数（Eulerian Number，不要和数论的搞混了）的组合意义：长为的排列恰有个“上升”的方案数，记作

$是长为的排列$

比如，下面是满足要求的排列：

我们还是先考虑递推。

我们考虑是怎么构成的。

原先有个上升位置。
- 在排列的右端放一个。转移到。
- 在排列某个下降的位置插入一个。转移到，系数为。
原先有个上升位置。
- 在排列的左端放一个。转移到。
- 在排列某个上升的位置插入一个。转移到，系数为。

综上：

那这个东西有通项公式吗？

有，是这个：

推导请参考final_trump的博客-Eulerian Number 组合推法。

十二重计数

十二重计数（Twelvefold Way）是指十二个计数问题，其都有下列形式：

你要把个球放进个盒子里，有多少种方案？

我们有三个条件可以选：球是否标号（Label/Unlabel），盒子是否标号，特殊限制：

A：无限制
B：每个盒子最少一个球
C：每个盒子最多一个球

我们用三个字母描述一个问题，比如 LUB 就是球标号、盒子不标号、每个盒子最少一个球。

我们一个一个来解决。

LLA

球和盒子都标号，无特殊限制。

每个球都可以选个盒子放，因此答案为。

LLB

球和盒子都标号，每个盒子最少一个球。

第二类斯特林数，然后再乘盒子排列数，答案。

LLC

球和盒子都标号，每个盒子最多一个球。

考虑选个盒子放球然后乘上球排列数，答案。

LUA

球标号盒子不标号，无特殊限制。

枚举多少个盒子放球，答案即为第二类斯特林数的和：

如果，上式也是贝尔数的定义式。

LUB

球标号盒子不标号，每个盒子最少一个球。

第二类斯特林数的组合意义，答案为

ULA

球不标号盒子标号，无特殊限制。

辅助元素插板即可。答案。

ULB

球不标号盒子标号，每个盒子最少一个球。

直接插板即可。答案。

ULC

球不标号盒子标号，每个盒子最多一个球。

也就是选个盒子放球。答案。

UUB

球和盒子都不标号，每个盒子最少一个球。

我么考虑为个球放进个盒子的方案数。

乍一看没有什么好的 DP 方法，但是这里有一个非常玄学的 DP：

边界。

我们用刷表考虑它的组合意义：

加一个新的空盒子，转移到。
给每个盒子都放一个球。转移到。

这样可以保证先加入的盒子一定不比后加入的盒子放的球少。

这个被称为划分数。

UUA

球和盒子都不标号，无特殊限制。

有两种方法：

枚举有几个空盒。答案即为。
我们加个球然后强制在每个盒子至少一个球，答案即为。

因此。

最后再来点好笑的。

UUC

球和盒子都不标号，每个盒子最多一个球。

你是否清醒？

答案。

LUC

球标号盒子不标号，每个盒子最多一个球。

你在搞笑吗？

答案。

总结

组合数学虽然繁杂且看起来需要背很多东西，但是其最核心的部分还是阶乘、组合意义、容斥原理，并不需要刻意的去背。

组合数学尤其需要大量练题，尤其是容斥原理与二项式反演需要反复练习以掌握其技巧。

部分参考资料

《具体数学》，Graham、Knuth、Patashnik著
OI-Wiki