双射之美——卡特兰数/反射容斥/格路计数
StayAlone
·
·
算法·理论
最后怎么变成论文搬运工了……
引入
格路
在平面直角坐标系中，横坐标和纵坐标都是整数的点称为格点，平面格路是指从一个格点到另一格点只走格点的路，格路的长度是指其所走的路的步数。
自由路
对于一条从 (0, 0) 走到 (n, m) 的格路，若其只使用了上步 U = (0,1)、水平步 L=(1, 0)，则称其为 (n, m) 自由路。
易知 (n, m) 自由路的数量为 \dbinom{n+m}{n}。
卡特兰数
从 (0, 0) 走到 (n, n)，且不越过直线 y=x 的自由路数量。
有递推式 H_i=\sum\limits_{i=1}^n H_{i-1}H_{n-i}。证明考虑：枚举第一次碰到直线 y=x 的位置，则从 (0, 0) 走到 (i, i) 的方案数为 H_{i-1}，从 (i, i) 走到 (n, n) 的方案数为 H_{n-i}。
卡特兰数有很多等价问题，如 P1375，P1754，AT_arc145_c，P7118，P2532，P5879。
P5879 的 solution 可以看到下一节。
卡特兰三角
反射容斥
利用反射容斥证明 H_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}。
补集转化，求越过了直线 y=x 的自由路数。发现这样的路一定与直线 y=x-1 有交点。取最靠右的交点，并将交点后的原路径关于直线 y=x-1 对称。如下图：
至此，我们可以构建 越过直线 y=x 的自由路 与 从 (0, 0) 走到 (n+1,n-1) 的自由路 的双射。集合大小相同，均为 \dbinom{2n}{n-1}，故原问题 H_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}。
卡特兰三角
定义
定义 C(n, k) 表示，由 n 个 1，k 个 -1 构成的序列中，前缀和不小于零的序列数。
则有：
-
-
-
-
证明
由反射容斥可知，$C(n, k)=\dbinom{n+k}{k}-\dbinom{n+k}{k-1}=\dfrac{n-k+1}{n+1}\dbinom{n+k}{k}$。故 2 情况可以代数证明。
同样补集转化，将最靠右的交点之后的路径关于直线 $y=x-1$ 对称，如下图：
我们可以构建 越过直线 $y=x$ 的自由路 与 从 $(0, 0)$ 走到 $(n+1,k-1)$ 的自由路 的双射，故原问题 $C(n, k)=\dbinom{n+k}{k}-\dbinom{n+k}{k-1}$。
#### 性质
由定义式可知，$C(n, k)=\sum\limits_{i=0}^kC(n-1, i)=\sum\limits_{i=k}^nC(i, k-1)$。
#### P5879 / 组合意义
反过来做，题意转化为，求满足如下条件的序列 $a_i$ 的数量：$0\le a_i\le i$，$a_i\le a_{i+1}$，此外 $a_i$ 不全为 $0$。
考虑 dp，设 $f_{i, j}$ 表示考虑前 $i$ 个数，$a_i=j$ 的方案数。钦定 $j>i$ 时，$f_{i, j}=0$，则有转移方程：
$$
f_{i, j}=\sum_{k=1}^{j} f_{i-1,k}=f_{i, j-1}+f_{i-1,j}
$$
答案就是 $\sum\limits_{i=1}^n f_{n, i}$。
发现转移方程完美符合卡特兰三角的形式。由卡特兰三角的性质，最终答案求和后就是 $C(n+1,n+1)-1=H_{n+1}-1$。
----
扩展一下，求满足如下条件的序列 $a_i$ 的数量：$0\le a_i\le \min(i, k)$，$a_i\le a_{i+1}$，其中 $k$ 是给定值。
只需再钦定 $j>k$ 时 $f_{i, j}=0$ 即可，转移方程完全一致。答案为 $\sum\limits_{i=0}^k f_{n, i}=C(n+1,k+1)$。
#### 一般化
定义 $C_m(n, k)$ 表示，由 $n$ 个 $1$，$k$ 个 $-1$ 构成的序列中，前缀和大于 $-m$ 的序列数。由定义，$C_1(n, k)=C(n, k)$。
同样可以反射容斥，这里不再赘述。
同样有 $C_m(n, k)=C_m(n-1,k)+C_m(n, k-1)$。这个其实很显然，只要 $n-k>-m$，$C_m(n-1,k)$ 和 $C_m(n, k-1)$ 就是分别对应最后一个数是 $1$ 或 $-1$ 的方案数。
## 双线反射容斥
求从 $(0, 0)$ 走到 $(n, m)$，且不**碰触**直线 $y=x+b$ 和直线 $y=x+c$ 的自由路数量。
若两直线在点 $(n, m)$ 同侧，则等价于一条直线的情况。
否则终点 $(n, m)$ 被夹在两直线之间，同样考虑容斥。
对于一条自由路，它与某条直线连续多次相交，总是钦定从第一个交点开始作对称操作。
用 B 表示与直线 $y=x+b$ 相交，C 表示与直线 $y=x+c$ 相交，则现在相交的情况形如 BCBC... 或 CBCB...（多次相交已归为一次）。
那么直接容斥，方案数就是 $\dbinom{n+m}{n}-f(\textrm B)-f(\textrm C)+f(\textrm{BC})+f(\textrm {CB})-f(\textrm {BCB})-f(\textrm {CBC})\cdots$。
点 $(x, y)$ 关于直线 $y=x+b$ 对称所得的点为 $(y-b, x+b)$；直线 $y=x+c$ 关于直线 $y=x+b$ 对称所得的直线为 $y=x+2b-c$。
例如情况 BCBCB...，与直线 $y=x+b$ 相交后对称，此时原路径与直线 $y=x+c$ 相交就体现为对称后路径与直线 $y=x+2b-c$ 相交。故而将一条直线和终点均关于另一条直线对称，得到另一个子问题，在过程中维护终点和对称后的直线即可算出方案数。每次减少 $b-c$，时间复杂度 $\mathcal O(\frac{n+m}{b-c})$。
另外的话还可以发现终点总是满足 $x+y=n+m$，所以需要的只有这条线上的组合数。
~~图暂时懒得画了，以后再说。~~
## 格路优化 dp
### P3266
显然每一行恰好有一个数未选择，其余数递增排列。设 $f_{i, j}$ 表示考虑前 $i$ 行，第 $i$ 行不选 $j$ 的方案数，有 $f_{i, j}=\sum\limits_{k=0}^{j+1}f_{i-1,k}=f_{i, j-1}+f_{i-1,j+1}$，答案是 $f_{n+1, m}$。
将转移画到网格上（$n=3,m=4$）：
将斜线拉直：
则原问题等价于，从 $(0, 0)$ 走到 $(n, n+m-1)$，且不触碰直线 $y=x+m+1$ 和 $y=x-2$ 的方案数。
```cpp
#define G(x) C(n + m, x)
il ll f(int b, int c) {
int x = n, y = m;
ll sum = 0; int coe = 1;
while (x >= 0 && y >= 0) {
(sum += coe * G(x)) %= mod;
x += c; y -= c; swap(x, y);
b = 2 * c - b; swap(b, c);
coe = -coe;
} return sum < 0 ? sum + mod : sum;
}
int main() {
read(n, m);
int b = -2, c = m + 1; m += n - 1;
printf("%lld", (f(b, c) + f(c, b) - G(n) + mod) % mod);
return 0;
}
```
### CF1821F
由于求的是种树方案数，故对于一种种树方案，能向左倒就向左，否则向右，构建种树方案与此倒树方案的双射。
设 $f_{i, j}$ 表示考虑种了前 $i$ 棵树，考虑到位置 $j$ 的方案数。
- $f_{i, j}\gets f_{i, j-1}
该 dp 等价于，从 (0, 0) 走到 (m, n)，每次有三种向量：(0, 1)，贡献为 1；(1, k+1)，贡献为 2；(1,2k+1)，贡献为 -2。一条路径的贡献为向量贡献之积，求总贡献和。
则枚举选择了第三种向量 t 次，则恰好选择了第二种向量 m-t 次，第一种向量 n-(m-t)(k+1)-t(2k+1) 次。
先排好后两种向量，方案数为 \dbinom{m}{t}，再与第一种排好，方案数为 \dbinom{n-(m-t)(k+1)-t(2k+1)+m}{m}。答案就是：
\sum_{t=0}^m 2^{m-t}(-1)^t \dbinom{m}{t} \dbinom{n-(m-t)(k+1)-t(2k+1)+m}{m}
Dyck 路计数
(n, m) 互质时的 (n, m)-\textrm{Dyck} 路计数
定义
对于一条从 (0, 0) 到 (n, m) 的自由路，若其始终不经过对角线 y=\frac{m}{n}x 下方，则称之为 (n, m)-\textrm{Dyck} 路。
记 \mathcal D(n, m) 为 (n, m)-\textrm{Dyck} 路的集合，D(n, m)=\# \mathcal D(n, m) 为 (n, m)-\textrm{Dyck} 路的数量。每条 (n, m)-\textrm{Dyck} 路可唯一对应一个 LU 序列。
对于从 (0,0) 到 (n,m) 的两条格路径 P, Q ，其中
P = u_1 u_2 \cdots u_{n+m}, \quad Q = v_1 v_2 \cdots v_{n+m} \quad (u_i, v_i \in \{L, U\}, i=1,2,\cdots,n+m)
若存在
u_{i+1} \cdots u_{n+m} u_1 \cdots u_i = v_1 v_2 \cdots v_{n+m},
则称格路径 P, Q 等价。将 P 的等价格路径全体记为 [P] 。
对于任意格路径 P ，记
P_k = u_k u_{k+1} u_{k+2} \cdots u_{n+m} u_1 \cdots u_{k-1}, \quad (k = 1, 2, 3, \cdots, n+m).
定义 P 的周期为使得 P = P_k 的最小整数 k ，用 \operatorname{period}(P) 表示，则显然有 $
# [P] = \operatorname{period}(P).
#### 引理
若 $ \gcd(n,m)=1 $，则 $ \forall P \in \mathcal{F}(n,m) $，有 $ \operatorname{period}(P) = n + m.
可通过反证法证明。
若 \gcd(n,m)=1 ，则一组 [P] 中有且仅有一条 (n, m)-\textrm{Dyck} 路。
存在性：找出一条不合法路 P，找出其中直线下方距离直线 y=\frac{m}{n} 最远的点，将路径划分为两条子路 L_1,L_2 使得 P=L_1L_2，则 P'=L_2L_1 一定是一条 (n, m)-\textrm{Dyck} 路。
唯一性：等价于证明直线下方距离直线最远的点有且仅有一个。考虑反证法，若有两个，设为 (x_1,y_1),(x_2,y_2)，其中 0<x_1<x_2<n，0<y_1<y_2<m。则这两个点连接所得直线与直线 y=\frac{m}{n} 平行，即 k=\dfrac{y_2-y_1}{x_2-x_1}=\dfrac{m}{n}，与 \gcd(n, m)=1 矛盾。
结论
### 有 $k$ 个峰的 $(n, m)$-$\textrm{Dyck}$ 路计数
#### 定义
对于一条从 $ (0,0) $ 到 $ (n,m) $ 的自由路中的连续两步，若其为 UL，则我们称之为一个峰 (peak)；若其为 LU，则我们称之为一个谷 (valley)。
#### 推论
记 $ \mathcal{F}(n,m;k) $ 为有恰好 $ k $ 个峰的 $ (n,m) $ 自由路的集合，$ F(n,m;k) = \# \mathcal{F}(n,m;k) $。
则从 $ (0,0) $ 到 $ (n,m) $ 的 $ k $ 个峰的自由路数量为 $F(n,m;k) = \binom{n}{k} \binom{m}{k}$。
> 将峰 UL 之间的格点叫做 **峰点**。任取一条格路径 $ P \in \mathcal{F}(n,m;k) $，设 $ P $ 的 $ k $ 个峰点分别为 $ (x_1,y_1), (x_2,y_2), \cdots, (x_k,y_k) $。则峰点坐标满足 $0 \le x_1 < x_2 < \cdots < x_k \le n - 1, 0 \le y_1 < y_2 < \cdots < y_k \le m$。
> 峰点的选取方案与 $ \mathcal{F}(n,m;k) $ 中的路径形成双射。
记 $ \mathcal{F}^{UL}(n,m;k) $ 为 $ \mathcal{F}(n,m;k) $ 中，第一步为 U，最后一步为 L 的自由路集合，$ F^{UL}(n,m;k) = \# \mathcal{F}^{UL}(n,m;k) =\dbinom{n-1}{k-1}\dbinom{m-1}{k-1}$。
> 第一个峰的横坐标和最后一个峰的纵坐标已经确定。
记 $ \mathcal{D}(n,m;k) $ 为有恰好 $ k $ 个峰的 $(n, m)$-$\textrm{Dyck}$ 路的集合，$ D(n,m;k) = \# \mathcal{D}(n,m;k) $。当 $(n, m)$ 互质时，有 $D(n, m; k)=\frac{1}{k}F^{UL}(n, m;k)$。
> 对于任意格路 $P$，若其有 $k$ 个峰，则有恰好 $k-1$ 个谷。以谷为界，划分成 $L_1,L_2,\cdots,L_k$ 共 $k$ 条子路，使得每条子路中有恰好一个峰，$P=L_1L_2\cdots L_k$。
>
> 对于任意一条 $\textrm{Dyck}$ 路，每个峰都可以唯一对应 $ \mathcal{F}(n,m;k) $ 中的一个元素：对于第 $i$ 个峰，构建 $P'=L_iL_{i+1}\cdots L_kL_1L_2\cdots L_{i-1}$。
>
> 考虑任意自由路 $Q\in \mathcal F^{UL}(n, m;k)$，其在对角线下方最远的点，其必然是谷点。同样以这个点断开形成两条子路 $L_1,L_2$，使得 $Q=L_1L_2$。
>
> 已知 $Q'=L_2L_1\in \mathcal D(n, m;k)$，因此 $\mathcal F^{UL}(n, m;k)$ 中的元素都可以唯一对应一条 $\textrm{Dyck}$ 路的峰。
### $t$-$\textrm{Dyck}$ 路计数
#### 定义
对于一条从 $(0, 0)$ 到 $(n, m)$ 的自由路，若其始终不经过对角线 $y=t\cdot x$ 下方，则称之为 $t$-$\textrm{Dyck}$ 路。特别地，若 $m=t\cdot n$，则称之为 $n$ 阶 $t$-$\textrm{Dyck}$ 路。
#### 推论
有 $k$ 个峰的 $n$ 阶 $t$-$\textrm{Dyck}$ 路的数量为 $D(n, tn;k)=\dfrac{1}{k}\dbinom{n-1}{k-1}\dbinom{tn}{k-1}$。
> 记 $m=tn+1$，有 $\gcd(n, m)=1$，则 $D(n, tn+1;k)=\dfrac{1}{k}\dbinom{n-1}{k-1}\dbinom{tn}{k-1}$。
>
> 对于任意 $P'\in \mathcal D(n, tn+1;k)$，$P'$ 的第一步肯定是 U。设 $P'=UP$。
>
> 由于直线 $y=\frac{tn+1}{n}x$ 和直线 $y=t\cdot x$ 之间没有整点，故 $P\in \mathcal D(n, tn;k)$，且是一一对应的。
$n$ 阶 $t$-$\textrm{Dyck}$ 路的个数是 $D(n, tn) =\dfrac{1}{tn+1}\dbinom{tn+n}{n}$。
> $$
> \begin{aligned}
> D(n, tn) &=\sum_{k=1}^n D(n, tn;k)\\
> &=\sum_{k=1}^n\dfrac{1}{k}\dbinom{n-1}{k-1}\dbinom{tn}{k-1}\\
> &=\dfrac{1}{tn+1}\dbinom{tn+n}{n}
> \end{aligned}
> $$
>
> 这里有一个恒等式：
> $$ \sum_{k=1}^{n} \frac{1}{k} \binom{n-1}{k-1} \binom{m}{k-1} = \frac{1}{m+1} \binom{m + n}{n}
> $$
## 不相交格路 / LGV 引理的特殊情况
### $n$ 阶不交 $\textrm{Dyck}$ 路计数
#### 定义
从 $(0, 0)$ 到 $(n, n)$ 的两条 $\textrm{Dyck}$ 路 $P, Q$ 称为一个 $n$ 阶 $\textrm{Dyck}$ 路对。若 $Q$ 始终不**穿过** $P$，则 $(P,Q)$ 是一个不交 $\textrm{Dyck}$ 路对，否则是一个相交 $\textrm{Dyck}$ 路对。
#### 推论
$n$ 阶不交 $\textrm{Dyck}$ 路对数为 $H_nH_{n+2}-H_{n+1}^2$，其中 $H_n$ 表示卡特兰数的第 $n$ 项。
> 如图，构建映射 $(P, Q)\to (P',Q')$，$P'=UUPLL$，并平移，$Q'=Q$，则 $(P,Q)$ 相交当且仅当 $(P',Q')$ **有公共点**。
>
> 则不交 $\textrm{Dyck}$ 路对数等于 $\textrm{Dyck}$ 路对 $(P',Q')$ 的数量减去有公共点的 $(P',Q')$ 路对数。前者显然是 $H_nH_{n+2}$，考虑计算后者。
>
> 对于任意有公共点的 $\textrm{Dyck}$ 路对 $(P',Q')$，以第一个交点为界，分别分为两条子路。令 $P'=P'_1P'_2,Q'=Q'_1Q'_2$，则构建映射 $(P',Q')\to (P'_1Q'_2,Q'_1P'_2)$。容易发现是双射。那么这部分的答案就是 $H_{n+1}^2$。
### 不交自由路对计数
#### 定义
若 $ P, Q $ 是两条自由路，若 $ Q $ 始终不穿越 $ P $，则称 $ (P, Q) $ 是从 $ (0,0) $ 到 $ (n,m) $ 的一对不交自由路对，用 $F_{nc}$ 表示。
若 $ P, Q $ 除起点和终点外无公共点，称为不接触自由路对，用 $F_{nt}$ 表示。
#### 推论
从 $ (0,0) $ 到 $ (n,m) $ 的不接触自由路对数目为：
$$
F_{nt}(n,m) = \frac{1}{n} \binom{n+m-1}{n-1} \binom{n+m-2}{n-1}
$$
> 对于任意不接触自由路对 $(P, Q)$，不妨设 $P$ 在 $Q$ 上方。显然可以令 $P=UP'L,Q=LQ'U$。根据定义，$P',Q'$ 无公共点。$(P,Q)$ 与 $(P',Q')$ 一一对应，考虑求出无公共点的路对 $(P',Q')$ 数。
>
> 考虑用总自由路对数减去有公共点的路对数。前者显然为 $\dbinom{n+m-2}{n-1}^2$。
>
> 同样构建双射，以第一个交点为界，使得 $P'=P'_1P'_2,Q'=Q'_1Q'_2$。则 $P'_1Q'_2$ 为从 $(0,1)$ 到 $(n, m-1)$ 的自由路，$Q'_1P'_2$ 为从 $(1, 0)$ 到 $(n-1,m)$ 的自由路，数量为 $\dbinom{n+m-2}{n}\dbinom{n+m-2}{n-2}$。
从 $ (0,0) $ 到 $ (n,m) $ 的不交自由路对数目为：
$$
F_{nc}(n,m) = \dfrac{1}{n+1}\binom{n+m+1}{n} \binom{n+m}{n}
$$
## 不接触自由路对与 $k$ 个峰的 $\textrm{Dyck}$ 路的关系
可以发现，从 $(0,0)$ 到 $(k, n - k + 1)$ 的不接触自由路对个数与 $k$ 个峰的 $n$ 阶 Dyck 路是一样的，均为
$$
\frac{1}{k} \binom{n}{k-1} \binom{n-1}{k-1}
$$
事实上，可以证明这两者间存在双射：
对于任意一个从 $(0,0)$ 到 $(k, n - k + 1)$ 的不接触自由路对 $(P,Q)$，将其展开为 $UL$ 序列：
$$
P = U \underbrace{U \cdots U}_{i_1} L \underbrace{U \cdots U}_{i_2} L \cdots L \underbrace{U \cdots U}_{i_k} L
$$
$$
Q = L \underbrace{U \cdots U}_{j_1} L \underbrace{U \cdots U}_{j_2} L \cdots L\underbrace{U \cdots U}_{j_k} U
$$
则有：
$$
\sum i_t = n - k
\quad
\sum j_t = n - k
$$
令
$$
R = \rho(P,Q) = \underbrace{U \cdots U}_{i_1 + 1} \underbrace{L \cdots L}_{j_1 + 1} \underbrace{U \cdots U}_{i_2 + 1}
\underbrace{L \cdots L}_{j_2 + 1} \cdots \underbrace{U \cdots U}_{i_k + 1} \underbrace{L \cdots L}_{j_k + 1}
$$
则 $R$ 是一个有着 $k$ 个峰的 $n$ 阶格路。而因为 $(P,Q)$ 是不接触自由路，因此：
$$
i_1 + 1 > j_1
$$
$$
i_1 + i_2 + 1 > j_1 + j_2
$$
$$
\vdots
$$
$$
\sum_{r=1}^{k} i_r + 1 > \sum_{r=1}^{k} j_r
$$
$$
\Rightarrow \sum_{r=1}^{s} i_r \ge \sum_{r=1}^{s} j_r
$$
故 $R$ 是 $\textrm{Dyck}$ 路。一个通过 $P, Q$ 构造 $R$ 的例子如图所示：
而 $\rho$ 的逆映射的构造以及证明是类似的，因此 $\rho$ 是一个双射。
------
参考资料：
- 戴言《浅谈格路计数相关问题》
- [Catalan's triangle - Wikipedia](https://en.wikipedia.org/wiki/Catalan's_triangle)
- [[Trick] 格路记数 - 反射容斥 - g1ove - 博客园](https://www.cnblogs.com/g1ove/p/18448337)