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