《数论杂文：组合计数篇》

Noby_Glds

·

2023-07-12 17:55:07

·

个人记录

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

经典公式

上指标求和 \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？）处理即可。