组合数学
Nine_Suns
·
·
个人记录
二项式系数
对于正整数 $n$，我们约定对于 $m<0$ 或 $m>n$ 的情况 $\dbinom nm=0$。
也可以将上指标的 $n$ 拓展到实数域有 $\dbinom {r}{m}=\dfrac {r^{\underline m}}{m!}$。
常用公式：
**对称性**：$\dbinom{n}{m}=\dbinom{n}{n-m}$。
拆开组合数容易验证。
**递推 / 拆分**：$\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$。
枚举第 $n$ 个球是否选择，选择的方案数为 $\dbinom{n-1}{m-1}$，不选则为 $\dbinom{n-1}{m}$。
**吸收 / 释放**：$\dbinom nm=\dfrac nm\dbinom {n-1}{m-1}$。
拆组合数可以验证。
**二项式定理**：$(x+y)^n=\sum\limits_{i=0}^n\dbinom{n}{i}x^iy^{n-i}$。
$x^iy^{n-i}$ 项的系数相当于是从 $n$ 个 $x$ 中选出 $i$ 个 $x$，其余选 $y$ 的方案数，即为 $\dbinom{n}{i}$。
实战中的 $y$ 常常为一些常数，需要仔细辨认。
从其中，我们令 $x=1$，$y=1$ 或 $y=-1$ 得到另两个重要的式子：
$\sum\limits_{i=0}^n \dbinom ni=(1+1)^n=2^n$。
$\sum\limits_{i=0}^n \dbinom ni(-1)^i= (1-1)^n=[n=0]$。
这指出一行二项式系数的 $\rm OGF$：$F(x)=\sum\limits_{i=0}^n\dbinom{n}{i}x^i=(x+1)^n$。
**上指标求和**：$\sum\limits_{i=0}^n\dbinom{i}{m}=\dbinom{n+1}{m+1}$。
考虑组合意义，设有 $n+1$ 个球，标号为 $0$ 到 $n$，$\sum\limits_{i=0}^n\dbinom im$ 相当于在枚举所选的球的标号最大值，再从小于最大值的 $i$ 个球中选出 $m$ 个，也就是从 $n+1$ 个球中选出 $m+1$ 个球的方案数。
**平行求和**：$\sum\limits_{i=0}^n\dbinom{i+m}{i}=\dbinom{n+m+1}{m+1}$。
$\sum\limits_{i=0}^n\dbinom{i+m}{i}=\sum\limits_{i=0}^n\dbinom {i+m}m=\sum\limits_{i=0}^{n+m}\dbinom im=\dbinom {n+m+1}{m+1}$。
先运用对称性，再补足 $\dbinom {i}{m}$ 中 $i<m$ 的部分，最后运用上指标求和。
**范德蒙德卷积**：$\sum\limits_{i=0}^k \dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}$。
$(x+1)^{n+m}=(x+1)^n(x+1)^m$，由二项式定理 $(x+1)^n=\sum\limits_{i=0}^n\dbinom nix^i$，模拟一下卷积就得到式子。也可以从组合意义的角度分析。
注：在运用公式化简二项式系数式，要特别注意**求和的上下界**，防止多加或多减。
___
[「KDOI-02」一个仇的复](https://www.luogu.com.cn/problem/P8594)
如果不考虑竖着的矩形，那么可以将上下两个 $1\times n$ 的矩形分开计算，枚举上面 $1\times n$ 用了几个矩形，得 $\sum\limits_{i=0}^{k}\dbinom{n-1}{i-1}\dbinom{n-1}{k-i-1}=\dbinom{2n-2}{k-2}$。
我们称没有竖着的矩形的一个 $2\times n(n>0)$ 的矩形为一个**整体**。
接下来我们枚举添加竖着的矩形后出现了多少整体，设为 $m$，再枚举有添加多少个竖着的矩形，设为 $s$。
不妨设 $m$ 个整体的长度和分配到的可用的矩形个数为 $a_i,b_i$。那么总的方案数即为 $\sum\limits_a \sum\limits_b\prod\limits_{i=1}^n\dbinom{2a_i-2}{b_i-2}=\sum\limits_a\dbinom{2\sum a_i-2m}{\sum b_i-2m}=\sum\limits_a\dbinom{2n-2s-2m}{k-s-2m}$。（其实是范德蒙德卷积拓展到多个组合数的情况），而根据插板法，将 $n-s$ 个数分给 $m$ 个整体有 $\dbinom{n-s-1}{m-1}$ 种方案，所以对于所有的 $a,b$，共 $\dbinom{n-s-1}{m-1}\dbinom{2n-2s-2m}{k-s-2m}$ 种方案。
我们目前已经计算了每个整体的长度和分配到的矩形个数，只再计算在整体与整体之间的夹缝中存在竖着的矩形的数量便可确定一种唯一的填法，根据插板法，有 $\dbinom{s+1}{m}$ 种方案（两端可以放 $0$ 个），与上面乘起来即可。
对于 $n=k$ 的情况，会多一种全放竖着矩形的情况（即没有整体），记得加上。
[梦现时刻](https://www.luogu.com.cn/problem/P7481)
统计答案的方式明显告诉我们应该对于每一个 $F(a,b)$ 求值。
然而直接求是 $O(n)$，而且没有什么好的公式或组合意义可以分析。
于是考虑拆组合数尝试递推。
$$F(a,b)=\sum_{i=0}^b\dbinom bi\dbinom {n-i}a$$
把 $\dbinom bi$ 拆成 $\dbinom {b-1}i+\dbinom {b-1}{i-1}$，得：
$$\sum_{i=0}^b\left(\dbinom {b-1}i+\dbinom {b-1}{i-1}\right)\dbinom{n-i}a$$
$$\sum_{i=0}^{b-1}\dbinom {b-1}i\dbinom{n-i}a+\sum_{i=0}^{b}\dbinom {b-1}{i-1}\dbinom {n-i}a$$
左边是 $F(a,b-1)$，很好，右边有 $\dbinom {b-1}{i-1}$，不好。用 $i-1$ 代换 $i$ 得到右边的和式：
$$\sum_{i=0}^{b-1}\dbinom {b-1}{i}\dbinom {n-i-1}a$$
然后把 $\dbinom {n-i-1}a$ 搞成 $\dbinom {n-i}a-\dbinom {n-i-1}{a-1}$，拆开：
$$\sum_{i=0}^{b-1}\dbinom {b-1}{i}\dbinom {n-i}a-\sum_{i=0}^{b-1}\dbinom {b-1}{i}\dbinom {n-i-1}{a-1}$$
左边成了 $F(a,b-1)$，很好。把右边式子拿出来，$\dbinom {b-1}i$ 再拆成 $\dbinom{b}{i+1}-\dbinom{b-1}{i+1}$，就有：
$$-\sum_{i=0}^{b-1}\dbinom {b}{i+1}\dbinom {n-i-1}{a-1}+\sum_{i=0}^{b-1}\dbinom {b-1}{i+1}\dbinom {n-i-1}{a-1}$$
用 $i+1$ 代换 $i$，得到：
$$-\sum_{i=1}^{b}\dbinom {b}{i}\dbinom {n-i}{a-1}+\sum_{i=1}^{b}\dbinom {b-1}{i+1}\dbinom {n-i}{a-1}$$
也就是 $-F(a-1,b)+F(a-1,b-1)$。（在 $i=0$ 时左右的值相等抵消了）。
于是得到 $F(a,b)=2F(a,b-1)-F(a-1,b)+F(a-1,b-1)$。
$O(m^2)$ 搞定。
还有一道题，比较细节的推式子：[「EZEC-6」0-1 Trie](https://www.luogu.com.cn/problem/P7386)。
## 卡特兰数
卡特兰数 $H$ 的组合意义很多，也有许多递推式。
常用的：
从 $(0,0)$ 出发，每一步只能向右或向上，到达 $(n,n)$ 且不**越过** $y=x$ 的方案数。
长度为 $2n$ 的合法的括号序列数。
$n$ 个结点的二叉树个数。
对应的，有几个不同的式子：
$H_n=\dfrac {\binom{2n}n}{n+1}=\dbinom{2n}{n}-\dbinom{2n}{n-1}$。
$H_n=\sum\limits_{i=1}^n H_{i-1}H_{n-i}$。其中 $H_0=1$。
___
对于卡特兰数的第一种组合意义，有其拓展：
从 $(0,0)$ 出发，每一步只能向右或向上，到达 $(n,m)$ 且不越过 $y=x$ 的方案数。
若一条路径越过了 $y=x$，则它必然经过 $y=x+1$，于是我们将这条路径从第一个经过 $y=x+1$ 的点开始关于 $y=x+1$ 进行翻折，于是它的终点将落在 $(m-1,n+1)$。于是从 $(0,0)$ 到达 $n,m$ 且越过 $y=x$ 的所有路径都可以一一对应到从 $(0,0)$ 到 $(m-1,n+1)$ 的所有路径，方案数即为 $\dbinom{m+n}{m-1}$。
于是不越过的方案数为 $\dbinom {m+n}m-\dbinom{m+n}{m-1}$。
推广到不越过 $y=x+b$ 的情形也是类似的。
___
[[HNOI2009] 有趣的数列](https://www.luogu.com.cn/problem/P3200)
很有趣的一道题。
先选出 $n$ 个奇数项，此时就确定了唯一的排列，考虑如何选择是合法的。
因为要满足第 $i$ 个偶数项大于第 $i$ 个奇数项，所以第 $i$ 个偶数项的前面至少有 $i$ 个奇数项。
于是把整个过程搬到坐标系上。
答案即为从 $(0,0)$ 开始走，依次考虑 $1$ 到 $2n$ 的所有值，若将其选为奇数项，则向右走一步，选为偶数项则向上走一步，不能越过 $y=x$，走到 $(n,n)$ 的方案数。也就是 $H_n$。
## 二项式反演 / 容斥
处理组合问题时重要的工具。
如果有：
$$f_n=\sum\limits_{i=0}^n\dbinom nig_i$$
则可以得到：
$$g_n=\sum_{i=0}^n(-1)^{n-i}\dbinom ni f_i$$
证明：
设 $F(x),G(x)$ 分别为 $f,g$ 的指数生成函数。
拆掉第一个式子的组合数，有：
$$\frac {f_n}{n!}=\sum_{i=0}^n \frac {g_i}{i!}\cdot \frac {1}{(n-i)!}$$
注意到卷积形式，并且 $e^x=\sum\limits_{i\ge0}\dfrac {x^i}{i!}$，所以有：
$$F(x)=G(x)e^x$$
所以：
$$G(x)=e^{-x}F(x)$$
提取系数就得到：
$$g_n=\sum_{i=0}^n(-1)^{n-i}\dbinom ni f_i$$
类似的，若 $f_n=\sum\limits_{i\ge n} \dbinom ing_i$，则 $g_n=\sum\limits_{i\ge n} (-1)^{i-n}\dbinom inf_i$。
___
容斥一般用在 $n$ 较小而集合大小相同的状态无法统一表示的时候，枚举子集，复杂度是 $O(2^n\times \text{计算时间})$。
二项式反演实质上在容斥时是将相同大小的集合打包在一起计算的情况，可以将“恰好”之类的描述转为“钦定”。
___
[[ZJOI2016] 小星星](https://www.luogu.com.cn/problem/P3349)
注意到 $n$ 很小，可以将对应好的位置状压，类似背包转移，但复杂度爆炸。
为什么需要将对应好的位置状压？因为题目要求新旧饰品一一对应。
考虑容斥掉这个关系。我们考虑 $O(n^3)$ dp 出在让新饰品的点对应到集合 $S$ 的方案。
然后枚举集合 $S$ dp 即可。复杂度 $O(2^nn^3)$。
一道类似的题是 [ [SHOI2016] 黑暗前的幻想乡](https://www.luogu.com.cn/problem/P4336)，不过需要矩阵树定理。
[[NOI Online #2 提高组] 游戏](https://www.luogu.com.cn/problem/P6478)
二项式反演典题。
看到计算非平局回合为 $k$ 的限制，直接反演变成钦定 $k$ 个非平局回合，其它随意的方案数。
不难发现一个非平局回合就是两个点异色点之间存在父子关系。
设 $f_{i,j}$ 表示在 $i$ 结点且子树内已有 $j$ 对异色点存在父子关系。树上背包 $O(n^2)$ 即可。
反演的过程也是 $O(n^2)$ 的。
## 斯特林数
第一类斯特林数的用处好像不太大，先不写了。~~才不是没学会~~
第二类斯特林数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示将 $n$ 个不同的元素分入 $m$ 个相同的集合的方案数（不能空集）。
根据定义可以得到递推式：
$$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$$
解释：考虑第 $n$ 个数的方法，可以新开一个集合，或者放入之前的任意一个集合。
第二类斯特林数常用来对付自然数幂。
具体的，有：
$$m^n=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}i!\binom {m}{i}$$
求和上界比较随意。也可以是 $m$。
证明：考虑组合意义，左边为将 $n$ 个不同的球放入 $m$ 个不同的盒子（允许空盒）0的方案数，我们枚举 $i$ 个盒子不是空的，对应的方案数为 $\begin{Bmatrix}n\\i\end{Bmatrix}i!\dbinom {m}{i}$，即将 $n$ 个球放入 $i$ 个不同的盒子（不允许空盒），再乘上 $\dbinom mi$ 表示这是哪几个盒子。
对上面的式子进行二项式反演可以得到第二类斯特林数的通项公式：
$$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac 1{m!}\sum_{i=0}^m (-1)^{m-i}i^n$$
是卷积形式，可以快速求出一行第二类斯特林数。
___
[[国家集训队] Crash 的文明世界](https://www.luogu.com.cn/problem/P4827)
自然数幂看着就没法操作，直接代换：
$$S(p)=\sum_{i=1}^n \sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom {{\rm dist}(p,i)}{j}$$
把与 ${\rm dist}(p,i)$ 无关的部分提到前面：
$$S(p)=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\binom {{\rm dist}(p,i)}j$$
由于 $k\le 100$，只需对每一个 $p$ 和 $j$ 求出 $\sum\limits_{i=1}^n\dbinom {{\rm dist}(p,i)}{j}$ 即可。
而由于 $\dbinom nm=\dbinom {n-1}m+\dbinom {n-1}{m-1}$，上面的式子可以 dp $O(nk)$ 搞出来。
还有一道斯特林数推式子的题，比较板：[Partitions](https://www.luogu.com.cn/problem/CF961G)。
## Lucas 定理
在数论里。
只有模数小的时候才有用。
___
[[SHOI2015] 超能粒子炮·改](https://www.luogu.com.cn/problem/P4345)
发现模数很小。$n,k$ 很大。
将 $n,k$ 分解成 $2333$ 进制类似数位 dp 搞搞。
[[AH2017/HNOI2017] 抛硬币](https://www.luogu.com.cn/problem/P3726)
先枚举小 A 比小 B 正面朝上的次数多几次，在枚举小 B 正面朝上的次数，有：
$$\sum_{i=1}\sum_{j=0}^b \binom bj\binom a{i+j}$$
辨识出范德蒙德卷积，得：
$$\sum_{i=1}\binom {a+b}{b+i}$$
似乎不太好搞，但注意到 $b-a\le 10^4$，考虑把答案分段看看。
从 $\dfrac {a+b}2$ 处将答案分开。右边是一行的一半，容易计算，左边的项数是 $O(a-b)$ 的，$\rm exLucas$ 计算。
## 其它
### 连链为环
如果没见过应该很难做。
[[ZJOI2011] 看电影](https://www.luogu.com.cn/problem/P3330)
首先概率是假的，转化为方案数。
发现很难做。考虑把链添加一个点连成环看看。
这样的话，如果一个人在原先的链上没有分配到空位，将会沿环走到新的位置。并且，如果是不合法的情况，则第 $k+1$ 个位置一定有人坐。
将问题转化为一个长度为 $k+1$ 的环，$n$ 个人任意分配位置，从分配到的位置开始走到第一个空位坐下，且没有人坐在第 $k+1$ 个位置的方案数。
于是会剩下 $k+1-n$ 个空位。可以任选一个空位作为 $k+1$，任意分配位置的方案数共 $(k+1)^n$，但由于是环编号旋转等价，要除掉一个 $k+1$，总方案为 $(k+1)^n(k+1-n)$。
[[ARC120F] Wine Thief](https://www.luogu.com.cn/problem/AT_arc120_f)
$O(nk)$ 的 dp 是显然的，但没什么用。
如果把整个序列连成一个环，相当于增加了限制不能同时选 $A_1$ 和 $A_n$，但有一个巨大好处，那就是每个点被选中的方案数是相等的，且容易计算。
然后我们强制选 $A_1,A_n$，那么 $A_2,A_{n-1}$ 不能选，之后是一个从 $A_3$ 到 $A_{n-2}$ 的新序列，可以递归下去按上面计算。
### 计数 dp
整体视角，变换 dp 顺序：[[AGC024E] Sequence Growing Hard](https://www.luogu.com.cn/problem/AT_agc024_e)
神仙题。
字典序的限制很难搞，发现 $k\le 300$，考虑从值域下手，从小到大插入数，这样的话，不管插入在哪里，都一定时合法的。但是实际的插入顺序也不一定从小到大啊？所以不能直接按题意来模拟。
由于统计的是序列组数而不是插入操作数，分析一下可以发现在一个同数量块中，插在哪里产生的新序列都是相同的，不妨强制插在末尾。
考虑将这个过程再转化一下，一开始一个序列也没有，插入一个数相当于是先在序列对中插入一个新的序列，再对后面的序列都在同样位置插入这个数。不难发现，若我们知道插入数在最后一个序列中的位置，则插入的这个序列也是可知位置的。
设 $f_{i,j,k}$ 表示已经有 $i$ 个序列，当前插入的数为 $j$，且最后一个序列有 $k$ 个数后面可以插入 $j$ 的方案数（因为开头也可以插入，所以共 $k+1$ 种插入方法）。
有转移
$f_{i+1,j,k}\gets (k+1)f_{i,j,k}$，相当于插入了一个数。
$f_{i,j,k-1}\gets f_{i,j,k}$，相当于我们决定不在这个位置放 $j$ 了。
$f_{i,j+1,i}\gets f_{i,j,0}$，位置已经用完了，可以用一个更大的数插入。
答案即为 $f_{n,k,0}$。
[[AGC002F] Leftmost Ball](https://www.luogu.com.cn/problem/AT_agc002_f)
观察发现白色球的本质是限制前缀中彩色球的颜色数量。具体地，若第 $i$ 个位置为第 $k$ 个白色球，则前 $i-1$ 个位置彩色球的不同颜色数必须小于 $k$。
不妨按照不同颜色球的出现位置给球的颜色重新标号，最后乘上 $n!$ 即可。
设 $f_{i,j}$ 表示已经放了 $i$ 个白球和 $j$ 种不同颜色的彩球的方案数，那么有转移 $f_{i,j}=f_{i-1,j}+\dbinom {n-(j-1)(k-1)-i-1}{k-2}f_{i,j-1}$。分别是选一个白球和用一种颜色的彩色球的方案数。一个需要注意的地方是用彩球时由于按出现位置标号，所以第一个新彩球必须紧接着白球的后面放。
答案即为 $n!f_{n,n}$，注意特判掉 $k=1$ 的情况。
局部观察 / 部分之间独立的性质：[Bracket Insertion](https://www.luogu.com.cn/problem/CF1781F)
概率直接变方案数。
括号序列的合法就是对前缀和的限制，不妨直接考虑前缀和。
若将 `()` 插入一个前缀和为 $x$ 的位置，那么会增加前缀和为 $x+1,x$ 的新位置，插入 `)(` 则增加前缀和为 $x-1,x$ 的位置。
注意到添加之后的三个位置不互相干扰，于是设 $f_{n,m}$ 表示一个初始前缀和为 $m$ 的位置经过 $n$ 次插入且的合法方案数，转移随便搞搞就行，就不写了。
### 欧拉数
记 $\left<\begin{matrix} n\\k\end{matrix}\right>$ 表示恰有 $k$ 个升高的 $n$ 阶排列数。（一个 $a_{i+1}>a_i$ 的位置是这个排列的一个升高）
考虑递推它。对于这种转移和相对大小有关的排列计数，转移时一般考虑枚举最大值。
若插入 $a_i<a_{i+1}$ 的两个数之间或最前面，那么不会产生新的升高，不难发现共有 $k+1$ 个这样的位置。
若插入 $a_i>a_{i+1}$ 的两个数之间，会产生一个新的升高，共有 $n-k$ 的这样的位置。
于是有：
$$\left<\begin{matrix} n\\k\end{matrix}\right>=(n-k)\left<\begin{matrix} n-1\\k-1\end{matrix}\right>+(k+1)\left<\begin{matrix} n-1\\k\end{matrix}\right>$$
这就可以 $O(n^2)$ 递推出欧拉数。