组合数学（含二项式反演，特殊数列，置换群）

· · 个人记录

资料与前置知识

必备技能：数论

容斥计数部分已搬到：容斥&计数

当小球遇上盒子

组合基础

组合恒等式

nC(n,m)=mC(n-1,m-1) C(n,m)=C(n-1,m-1)+C(n-1,m) \sum_{0<=i<=n}C(n,i)=2^n \sum_{0<=i<=n}(-1)^i * C(n,i)=0 \sum_{m<=i<=n}C(i,m)=C(n+1,m+1) \sum_{0<=i<=p}C(n,i)C(m,p-i)=C(m+n,p) \sum_{i=0}^n(C_n^i)^2 (= \sum_{i=0}^n(C_n^i * C_n^{n-i}) = C_{2n}^n

组合数的算法：

  1. O(n^2) DP

  2. 当模数为质数时，O(n)阶乘+逆元

  3. 模数较小，n,m巨大时：P3807 【模板】卢卡斯定理；【简介】卢卡斯定理

  4. 模数可分解为 Πp^q，且p^q不大时：P4720 【模板】扩展卢卡斯；【简介】扩展卢卡斯

  5. 无任何特征，但n, m <= 1e6, M <= 1e9以内时：线性筛将阶乘分解质因数，然后除法 -> 减法，最后乘起来就好

  6. （不常用）对于大阶乘，有一个估算的方法：n! = \sqrt{2 \pi n} * (\frac{n}{e})^n，其中 e 为自然对数的底数。可以依据此算一些东西（当然不能暴力算阶乘），比如 n! 的十进制下的位数，就可以转而求 log_{10}n!，然后变为求 log_{10} (\sqrt{2 \pi n} * (\frac{n}{e})^n)，这个要好求一些。

经典模型

$n$ 个无标号球分成 $m$ 个有标号组可以为空（插板） $n$ 个有标号球分成 $m$ 个有标号组可以为空（$m^n$) $n$ 个有标号球分成 $m$ 个有标号组不可为空（枚举非空组数) $n$ 个有标号球分成 $m$ 个无编号组不可为空（第二类斯特林数） $n$ 个有标号球分成 $m$ 个无编号组可以为空（第二类斯特林数 + 枚举非空组数） $n$ 个无标号球分成 $m$ 个无标号组不可/可以为空（整数划分数）

长为 n 的序列中选择 m 个不相邻的元素的方案数

可以看作从剩下的 n-m 个元素所形成的 n - m + 1 个空位置中选择 m 个空位置的方案数。因此答案为:

{n-m+1 \choose m}

考虑插板。这个问题可以转化为将 k 个无标号球涂成 n 种颜色，每个球必须涂色，每种颜色不一定需要被涂，的方案数。那么就又可以转化为了 k 个球分成 n 个集合，集合可空，的方案数。这时可以直接用插板法解决，方案数为 {k + n - 1 \choose n - 1}。

二项式反演：

公式

二项式反演的主要的三种形式：

形式一

f[n] = \sum_{i=0}^n (-1)^iC_n^ig[i] g[n] = \sum_{i=0}^n (-1)^iC_n^if[i]

最对称了，也是最好背的一个。

形式二

f[n] = \sum_{i=0}^n C_n^ig[i] g[n] = \sum_{i=0}^n(-1)^{n-i}C_n^if[i]

形式三

f[n] = \sum_{i=n}^m C_{i}^ng[i] g[n] = \sum_{i=n}^m (-1)^{i-n}C_i^nf[i]

形式二，三一个是 n-i,C_n^i，一个是 i-n,C_i^n，主要还是和 i,n 的大小关系有关。

常见套路

通常是“恰好”与“至少”之间的转换。

注意，这里的“至少”通常不是由“恰好”以1为系数加和而来，而是包含许许多多的重复计数，否则就可以直接前缀和差分了。

设 f[i] 表示恰好选择 i 个元素的方案数， g[i] 表示至少选择 i 个元素的方案数。然而，g[i] 的计算通常过于无脑，以至于 1101 会被 g[2] 算三次（1001,1100,0101)，然后才能开始反演。

P4859 已经没有什么好害怕的了

首先把假的 k 转化为真的 k，然后递推DP之类的...

假设我们已经知道了选择 i 对 A > B ，其它的不管的方案数dp[i]。这样我们可以无脑地算出 g[i] = dp[i] * (n-i)!，但是会算重好多。

设 f[i] 表示恰好有 i 对的方案数。则：

g[i] = \sum_{j=i}^n f[j] * C_j^i

也就是说，g[i] 会将 f[j] 的每种情况都算重 C_j^i 次。

然后就是二项式反演的套路了。

f[i]=\sum_{j=i}^n (-1)^{j-i}C_j^ig[j] ### [P5505 [JSOI2011]分特产](https://www.luogu.com.cn/problem/P5505) 同样大致的套路，都是先“无脑”，后推式子反演。 据说可以用容斥做，但是我刚容斥到第二项就脑壳疼了。 ### [#2839. 集合计数](https://darkbzoj.tk/problem/2839) 之前曾经用容斥的方法做过这道题，但是推的式子不一样。 那一次我是考虑当前 $g$ 选择的那 $i$ 个元素以外再多出那么几个元素，有多少种方案，然后乘上对应的组合数容斥打表。 这一次我还是按照套路，**将 $g$ 的实质分类讨论，其中对于交了 $j$ 个的情况，$g$ 的计算中一共有 $f[j]$ 种情况，并且每一种情况都恰好被计算了 $C_j^i$ 次；情况与情况之间无关，可以用加法原理，** 然后就是那个老套路了。看来这两种方法应该结果是一样的。 ## 特殊数列： ### prufer序列 将一棵无根树进行如下操作： 将找到编号最小的**叶子**节点，**记录**与其相连的节点编号，然后**删除**掉它。直至只剩两个点。其中**记录的编号序列即为该无根树的prufer序列**。 显然，大小为 $n$ 的无根树的prufer序列长度为 $n - 2$. **无根树与prufer序列是一一对应的**。已知一无根树可以求其prufer序列，已知prufer序列可以求其对应的无根树。方法见：[P6086 【模板】Prufer 序列](https://www.luogu.com.cn/problem/P6086)，主要是模拟求prufer序列，推测最小叶子节点构造无根树。 **无根树的prufer序列中，一个点的出现次数=其度数-1**，因为每个点只有在删除自己时会“消耗”一条连边而不将自己编号记录一遍。 根据无根树与prufer序列的一一对应的关系，可以将其互相转化，以简化问题。如：**n个点的完全图生成树有 $n^{n-2}$ 个**；另外还有：[P2624 [HNOI2008]明明的烦恼](https://www.luogu.com.cn/problem/P2624) ### 错排数 枚举最后一个的错排情况(两个位置互相“占用”，或者把 $n$ 放 $i$ 那里，把 $a_i$ 放 $n$ 那里）（或者说分类考虑最终答案里面放 $n$ 的那个位置的下标是否是 $a_n$,然后加法原理），O(n)递推： ```cpp f[n] = f[n - 1] * (n - 1) + f[n - 2] * (n - 1) = (n - 1)(f[n - 1] + f[n - 2]) 其中，f[0] = 1, f[1] = 0; ``` ### Catalan数 ![Catalan](https://s2.ax1x.com/2020/02/03/100eIA.png) ### 斯特林数： 实际上斯特林数还可以用于普通幂和阶乘幂之间的转化，不过就比较高级了。见[斯特林数](https://www.cnblogs.com/JiaZP/p/14162592.html)。 #### 第一类斯特林数 $s[n][m]$ 表示把 $n$ 个有标号元素划分为 $m$ 个非空圆排列的方案数。 $$s[n][m] = s[n - 1][m - 1] + s[n - 1][m] * (n - 1)$$ #### 第二类斯特林数 $s[n][m]$ 表示把 $n$ 个有标号元素分成 $m$ 个非空集合的方案数。即把 $n$ 个元素（有标号）分成 $m$ 份（无标号），不能为空。 $$s[n][m] = s[n - 1][m - 1] + s[n - 1][m] * m$$ 然后对比"把 $n$ 个元素（有标号）分成 $m$ 份（有标号），可以为空"的式子：$m^n

然后考虑它们之间的关系：枚举第二种中非空集合的个数：

m^n = \sum_{i=0}^{m} C_m^i × s[n][i] × i!

然后发现可以二项式反演：

s[n][m] * m! = \sum_{i=0}^{m} C_m^i × i^n × (-1)^{m-i} s[n][m] = \sum_{i=0}^m \frac{i^n(-1)^{m-i}}{i!(m-i)!}

令 A_i = \frac{i^n}{i!}，B_i = \frac{(-1)^i}{i!}，那么：

s[n][m] = \sum_{i=0}^m A_i * B_{m-i}

然后发现对于 n 固定的情况， s[n][m] 是 A_i 和 B_i 的卷积形式，这样我们就可以 NTT 优化到 O(nlogn) 求一批第二类斯特林数了。

一些小技巧

m^n = \sum_{i=0}^{m} C_m^i × s[n][i] × i!

对于这个式子我们可以把 a^k 这样的数换一种形式：

a^k = \sum_{i=0}^{a} C_a^i × s[k][i] × i!

然后通常就可以优化一些式子了。比如：P4827 [国家集训队] Crash 的文明世界

普通幂阶乘幂转化

见上面的博客

斯特林反演

见博客

整数划分数

lhm大佬的博客

整数划分数可以解决“无标号球分到无标号盒子”的问题。此类问题可以直接用背包做（01背包/无限背包)，但是还有一些常用的DP方法，通常有更优秀的复杂度。

version1

将 n 划分为 m 个正整数的和的方案数：（整体加一或新建一）

f(n,m)=f(n-1,m-1)+f(n-m,m)

version2

将 n 划分为 m 个不同正整数的和的方案数：（整体加一或整体加一后新建一）

f(n,m)=f(n-m,m) + f(n-m,m-1)

version3

将 n 划分为 m 个不超过 l 的不同正整数的和的方案数：（version2后容斥，减去加完后出来 l+1 的情况）

f(n,m)=f(n-m,m)+f(n-m,m-1) - f(n-l-1,m-1)

version4

将 n 划分为 m 个至少为 l 的不同正整数的和的方案数：（整体加一或新建 l）

f(n,m)= f(n-l,m-1)+f(n-m,m)

version5

将 n 划分为 m 个奇数/偶数的和的方案数：（认为 0 不是偶数)

设 f(n,m) 表示将 n 划分为 m 个奇数的和的方案数， g(n,m) 表示将 n 划分为 m 个偶数的和的方案数：

f(n,m) = g(n-m,m)+f(n-1,m-1)\\ g(n,m)=f(n-m,m)

或者：

f(n,m)=f(n-2m,m) + f(n-1,m-1)

version6

将 n 划分为若干正整数的和的方案数：

对组成 n 的那些数进行根号分治，< \sqrt n 的数不超过 \sqrt n 种，无限背包复杂度为 O(n \sqrt n)，\ge \sqrt n 的数总共最多不会出现 \sqrt n 次，用 version4 的方法复杂度为 O(n \sqrt n)。最后乘法原理合并即可。复杂度：O(n \sqrt n)

version7

将 n 划分为若干不同的正整数的和的方案数：

数的总数不会超过 \sqrt n 个，可以直接用 version2 的方法做。复杂度：O(n \sqrt n)

更高级的做法

zbk五边形数

伯努利数

我们设自然数幂和：

S_m(n)=\sum_{i=0}^{n-1}i^m

将其用关于 n 的 m+1 次多项式表示，并在其中定义伯努利数 B_i：（证明见链接）

S_m(n)=\dfrac{1}{m+1} \sum_{i=0}^{m} {m+1 \choose i} B_in^{m+1-i}

伯努利数的递归定义式：

\sum_{i=0}^{m} {m+1 \choose i} B_i = [m=0]

生成函数定义式：

B(x)=\frac{x}{e^x-1}

具体见链接。

置换群：

给有n个珠⼦的项链染⾊，共有m种颜⾊，考虑旋转（或旋转+翻折），求方案数。

如何确定自己把置换群找对了？

  1. 不要重复
  2. 要有恒等置换
  3. 要有任两个置换的复合
  4. 要有任何⼀个置换的逆置换

本质不同的项链数 = sigma{每个映射的不动点数目} / |P|

其中，|P|为置换群大小，通常为旋转0次,1次，2次...n - 1次中的 n 。

对于这种只有翻转、旋转的置换，不仅是A到A的映射，还是珠子到珠子的映射。这时候，每个置换其实对应了一个排列，把原来珠子的位置映射到新的珠子的位置。
对于这种本质上是排列的置换，求不动点的实质就是求这个排列有多少个环。每个排列都是若干个循环的复合：我们把排列位置i上的数字设为p_i，i->pi连一条边，得到的是一个环的森林，每一个环都要染成一样的颜色。总的染色方案数，
就是颜色数 的 “环的个数” 次方。这个叫做polya定理。
-by gzz学长

例题：Color

双倍经验：P4980 【模板】Polya定理

其实是个推式子题。

第一张图片注释：

第二行把g除掉后，i/g和n/g互质，所以i/g有逆元。因此，给定唯一的t（<n/g），都有唯一不同的一个答案，从而得出结论：环的大小为n/g

第二张图片注释：

第二个等号：n -> n/g, i -> i/g，因此范围缩小g，到0~(n-1)/g，等价于0~(n/g)-1

Code:

inline ll polya(int n) {
    ll res = 0;
    for (register int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            register int g = i;
            res += quickpow(n, g - 1) * get_phi(n/g) % P;
            if (i * i != n) res += quickpow(n, n/g - 1) * get_phi(g) % P;
            res %= P;
        }
    }
    return res;
}

Continued...