《数论杂文：组合计数篇》
Noby_Glds
·
·
个人记录
Part 0：目录
- 组合数及公式
- Lucas定理
- 经典组合问题
- 斐波那契和卡特兰数
- min-max 容斥
Part 1：组合数及公式
何为组合数
从 n 个不同元素中选出 m 个不同元素组成集合的方案数，我们将其表示为组合数 \dbinom{n}{m} 或 C_n^m。（个人更喜欢前者）
组合数如何计算？如果我们将组成集合改为组成排列，那么方案数如下：
\dfrac{n!}{(n-m)!}
接着我们考虑到 m 个不同元素组成排列有 m! 种，而组成的集合只有一种，所以：
\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}
当 n<m 时，\dbinom{n}{m}=0。
经典公式
- 上指标求和 \sum_{i=1}^r\dbinom{i}{x}=\dbinom{r+1}{x+1}-\dbinom{l}{x+1}
- 一个递推式 \dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1}
- 范德蒙德卷积 \sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}
附：卷积：两个函数运算形成第三个函数（并不准确）
- 二项式定理 (x+y)^n=\sum_{i=0}^n\dbinom{n}{i}x^iy^{n-i}
例题
Different Subsets For All Tuples
考虑到正向分析过于困难，我们不妨枚举一个子序列所做的贡献。
枚举子序列从长度 i 和末尾位置 j，可以分析出在 j 前面的不为子序列一部分的位置只能取 m-1 种情况（不能与该位置右边最近的子序列位置填的数相同），而 j 以后的位置则随便取，可以写出式子如下：
\sum_{i=1}^n\sum_{j=i}^n\dbinom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}
考虑到这个式子有点像二项式定理，可以变形：
\sum_{j=1}^n\sum_{i=1}^j\dbinom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}
\sum_{j=0}^{n-1}\sum_{i=0}^j\dbinom{j}{i}m^{n-j+i}(m-1)^{j-i}
\sum_{j=0}^{n-1}m^{n-j}\sum_{i=0}^jm^i(m-1)^{j-i}
\sum_{i=0}^{n-1}m^{n-i}(2m-1)^i
可以预处理出阶乘，时间复杂度 O(n)。
Part 2：Lucas 定理
卢卡斯定理内容
\dbinom{n}{m}\bmod p=\dbinom{n\bmod p}{m\bmod p}\dbinom{n/p}{m/p}\bmod p
没有了，我不会证明（
拓展卢卡斯定理
当模数 p 不为整数时，Lucas 就用不了了。
将 p 分解质因数，用 p 的质因子去模 \dbinom{n}{m}，最后用中国剩余定理合并。
没有了，就这些东西。
Part 3：经典组合问题
插板法
将排成一排 n 个物品分成连续的 m 组。
我们可以看做插 m-1 个板子在物品中，因此答案为 \dbinom{n-1}{m-1}
错排问题
求所有置换环都不为 1 的置换数目，说句人话，求有多少种打乱方案，使每个物品都不在原来的位置上。
若 n 在所在的置换环只有两个元素，方案为 f(n-2)*(n-1)。
否则将 n 从环上拆掉，然后就可以看作只有 n-1 个节点时的情况，方案为 f(n-1)*(n-1)。
合并，答案为 f(n)=(n-1)(f(n-1)+f(n-2))。
环上邻色不同的染色方案
首先 1 随便取，然后接下来每个位置都不能与上一个位置的颜色相同。
接着排除 n 与 1 的颜色相同时的情况，可以将 n 和 1 看做一个位置，就相当于 n-1 个位置的染色方案了。
f(n)=m*(m-1)^{n-1}-f(n-1)
网格图路径统计问题
对于一张 n*m 的网格图，一共有 \dbinom{n+m}{n} 无限制路径。
但是，事情没这么简单。
- 一张 n*m(n<=m) 的网格图，不经过 y=x 的路径：\dbinom{n+m}{n}-\dbinom{n+m}{n-1}
这里我难以解释，推荐一篇博客%%%。
-
n*m$ 网格图，两条不相交路径：$\dbinom{n+m-2}{n-1}^2-\dbinom{n+m-2}{n}\dbinom{n+m-2}{m}
首先我们可以确定两条路径必定经过的点：一条经过 (1,0)(n,m-1)，一条经过 (0,1)(n-1,m)，不考虑相交，直接求路径数。
接着交换两条路径的结束点 (n,m-1) 和 (n-1,m)，再求一次，这便是不合法的路径情况。
Part 4：斐波那契和卡特兰数
斐波那契数列
F_i=F_{i-1}+F_{i-2}(i\ge2)
这里讲一些有趣的性质：
-
- 在模 p 意义下，类斐波那契数列存在小于等于 6m 的循环节（不会证）
卡特兰数
首先要说，这真不是什么高深的东西（Noby_Gld你听到了吗）。
\begin{cases}C_0=1\\C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}\end{cases}
C_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}
C_n=\dfrac{4n-2}{n+1}C_{n-1}
一些应用如下：
Part 5：min-max 容斥
画风突变。
介绍
有没有想过，我们可以用容斥来求出一个集合里最大和最小的数？
设 max(a) 为集合 a 中最大的数，min(a) 为集合 a 中最小的数。
max(S)=\sum_{T\subseteq S(T\ne\varnothing)}(-1)^{|T|-1}min(T)
min(S)=\sum_{T\subseteq S(T\ne\varnothing)}(-1)^{|T|-1}max(T)
这么丑的式子，证明一下？
我们只证明第一个式子，对于集合内的一个数 x_i，当它作为 min(T) 时，共产生了多少贡献？
设集合内比 x_i 大的数有 p 个，则 \sum_{i=0}^p(-1)^p\dbinom{p}{i} 为它的贡献的系数。
稍微证明可以发现，只有 p=0 时，上面的式子才不为 0，然后就证完了。
但你给我这两个式子有什么用呢？最大值和最小值我不能直接求吗？
这个式子在期望下是成立的。
E(max(S))=\sum_{T\subseteq S(T\ne\varnothing)}(-1)^{|T|-1}E(min(T))
也就是说，如果我们能快速求出 E(min(T))，我就能求出本来很难求的 E(max(S))，反过来同理。
扩展 min-max 容斥（求第 k 大）
设 kthmax(S) 为集合中第 k 大的元素，则我们有如下式子：
kthmax(S)=\sum_{T\subseteq S(|T|\ge k)}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}min(T)
同样地，这个式子在期望下也成立，证明跟普通的 min-max 容斥差不多。
例题
P3175 [HAOI2015] 按位或
设 E(max(S)) 为最晚的元素出现时间期望，显然有：
E(max(S))=\sum_{T\subseteq S(T\ne\varnothing)}(-1)^{|T|-1}E(min(T))
考虑 E(min(T)) 怎么求，发现只要或上一个就可以了（这个地方我自己表述不清楚）：
E(min(T))=\frac{1}{\sum_{q|x\ne0}p[q]}
正面求 \sum_{q|x\ne0}p[q] 有点难，不如考虑与 x 无交的所有数，即 1-\sum_{q|x=0}p[q]，也就是 x 的补集，用 FWT（还是 FMT？）处理即可。