格路计数学习(抄写)笔记
\(2\) \(\operatorname{Dyck}\) 路
\(2.1\) 格路
定义 2.1 在平面直角坐标系中，横坐标和纵坐标都是整数的点称为格点，平面格路是指从 一个格点到另一格点只走格点的路，格路的长度是指其所走的路的步数。
\(2.2\) 自由路
定义 \(2.2\) 对于一条从 \((0,0)\) 到 \((n,m)\) 的格路，若只使用上步 \(U = (0,1)\) 和右步 \(L = (1,0)\)，则我们称其为 \((n,m)\) 自由路。
定理 \(2.1\) 记 \(F(n,m)\) 为 \((n,m)\) 自由路的数量，\(\mathcal{F}(n,m)\) 为 \((n,m)\) 自由路的数量，则 \(F(n,m) = \binom{n+m}{n}\)。
\(2.3\) \(\operatorname{(n,m)-Dyck}\) 路的计数
定义 \(2.3\) 对于一条从 \((0,0)\) 到 \((n,m)\) 的自由路，若其始终不经过对角线 \(y = \frac{m}{n}x\) 下方，则我们称之为 \(\operatorname{(n,m)-Dyck}\) 路。
记 \(D(n,m)\) 为 \(\operatorname{(n,m)-Dyck}\) 路的数量，记 \(\mathcal{D}(n,m)\)。
考虑一条 \(\operatorname{(n,m)-Dyck}\) 路对应的 \(LU\) 序列。
定义 \(2.4\) 对于从 \((0,0)\) 到 \((n,m)\) 的 \(2\) 条格路 \((P,Q)\) ，其中 \(P = u_1u_2 \cdots u_{n+m}\)，\(Q = v_1v_2 \cdots v_{n+m}\) \((u_i,v_i \in \{L,U\})\)。若 \(\exist i,u_{i+1} \cdots u_{n+m}u_1 \cdots u_i=Q\)，则我们称格子 \(P,Q\) 等价（即循环同构）。将 \(P\) 的等价路全集记为 \([P]\)。
定义 \(2.5\) 对于任意格路 \(P\) ，记 \(P_k = u_{k+1}u_{k+2} \cdots u_{n+m}u_1 \cdots u_k\)。则 \([P] = \{P_k | k =1,2,3,\cdots , n+m\}\)。定义 \(P\) 的 周期 为使得 \(P = P_k\) 的最小数 \(k\) ，用 \(period(P)\) 表示，则显然有 \(\#[P] = period (P)\)。
引理 \(2.1\) 若 \((n,m)=1\)，则 \(\forall P \in \mathcal{F}(n,m)\)，有：
\[period(P) = n + m \] 证明：
显然有 \(period(P) \leq n + m\)。考虑反证法：
若 \(period(P) < n + m\)，设为 \(r\)。设 \(n + m = ar + b\) \((b < r)\)。
则由定义得 \(P = P_r = P_{2r} = \cdots = P_{ar}\)。所以有 \(P_b = P\)，则推出 \(b = 0\)。又因为 \(r < n + m\) ， 所以 \(a > 1\)。
因为 \(a>1\)，所以 \(a | n\) 且 \(a | m\)，与 \((n,m)=1\) 矛盾，所以 \(period(P) = n + m\)。
引理 \(2.2\) 当 \(n\) 和 \(m\) 互质时，\([P]\) 有且仅有一条 \(\operatorname{(n,m)-Dyck}\) 路。
证明：
首先证明存在性：
若 \(P\) 不是一条 \(\operatorname{(n,m)-Dyck}\) 路，则其一定存在一个点在对角线下方。设这些点当中离对角线最远 的点是 \(v\)，从这个位置断开，将 \(P\) 分为两个子路 \(L_1,L_2\)。则 \(P\) 可以表示为 \(P = L_1L_2\)。构建一条新 的格路 \(P'=L_2L_1\)，则 \(P'\) 显然是一条 \(\operatorname{(n,m)-Dyck}\) 路。
然后证明唯一性：
容易发现，我们只需要证明对角线下方距离对角线最远的点有且只有一个。
设两点距离对角线距离相同，则这两点形成直线与对角线斜率 \(\frac{m}{n}\) 相同。由 \(n,m\) 互质可知对角线 下方不存在这样的两个整点。
由上述两个引理我们就可以立刻得出：
定理 \(2.2\) 当 \((n,m)\) 互质时，\(\operatorname{(n,m)-Dyck}\) 路的数量为：
\[D(n,m) = \frac{1}{n+m} \binom{n+m}{n} \]\(2.4\) 有 \(k\) 个峰的 \(\operatorname{(n,m)-Dyck}\) 路计数
定义 \(2.6\) 对于一条从 \((0, 0)\) 到 \((n, m)\) 的自由路中的连续两步，若其为 UL，则我们称之为一个峰；若其为 LU，则我们称之为一个谷。
定理 \(2.3\) 记 \(\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} \] 这个很好理解，相当于在 \(n\) 个 L 中选择 \(k\) 个作为峰，在 \(m\) 个 U 作为峰，这两部分显然是独立的。每一种选法都能够对应一种方案。
定理 \(\mathrm {2.4}\) 记 \(\mathcal F^{UL} (n,m;k)\) 为所有有恰好 \(k\) 个峰，且首步为 \(U\)，末步为 \(L\) 的 \((n,m)\) 自由路的集合，\(F^{UL}(n,m;k) = \# \mathcal F^{UL}(n,m;k)\)。则有：
\[F^{UL} = \binom{n-1}{k-1} \binom{m-1}{k-1} \] 起始的一段 U 一定会与后面形成一个峰，结尾的一段 L 一定会和前面形成峰。那么这个公式就是易于理解，显然成立的。注意到他这么定义的动机就是要引入不能越过对角线的限制了。
定理 \(2.5\) 记 \(\mathcal D(n,m;k)\) 为所有有恰好 \(k\) 个峰的 \(\operatorname{(n,m)-Dyck}\) 路的集合，\(D(n,m;k) = \# \mathcal D(n,m;k)\)。则当 \(n,m\) 互质时，恰有 \(k\) 个峰的 \(\operatorname{(n,m)-Dyck}\) 路的个数为：
\[D(n,m;k) = \frac{1}{k} \binom{n-1}{k-1}\binom{m-1}{k-1} \] 证明：
对于任意格路 \(P \in \mathcal F^{UL}(n,m;k)\) ，其恰好有 \(k - 1\) 个谷，我们将其断开分成若干子路。则有 \(P = L_1L_2 \cdots L_k\)。
与 引理 \(2.1\) 类似，将 \(L\) 看做元素，\(P\) 的 周期 为 \(k\)。
因此每条 \(\operatorname {Dyck}\) 路的每个峰唯一对应 \(\mathcal F^{UL}(n,m;k)\) 中的一个元素。 同样的，我们这样的格路也找 到离对角线最远的点切开，交换两端。这个最远的点一定是谷。所以每个 \(\mathcal F^{UL}(n,m;k)\) 中的元素都可以 唯一对应 \(\operatorname {Dyck}\) 路中的一个峰。所以这个公式显然成立。
\(2.5\) \(\operatorname {t-Dyck}\) 路计数
定义 $2.7 $ 对于一条从 \((0,0)\) 到 \((n,m)\) 的自由路，若其始终不经过对角线 \(y = tx\) 下方，则我们称之为 \(\operatorname{t-Dyck}\) 路。特别地，若 \(m = tn\) ，则我们称之为 \(n\) 阶 \(\operatorname{t-Dyck}\) 路。
注意，因为 \((n,tn) \not = 1\) ，所以不满足之前所述定理的使用条件。
定理 \(2.6\) 有 \(k\) 个峰的 \(n\) 阶 \(\operatorname{t-Dyck}\) 路的个数是：
\[D(n,tn;k) = \frac{1}{k} \binom{n-1}{k-1}\binom{tn}{k-1} \] 证明：
记 \(m = tn + 1\) ，则显然 \((n,m)=1\)。带入 定理 \(2.5\)。
\[D(n,tn+1;k) = \frac{1}{k} \binom{n-1}{k-1}\binom{tn}{k-1} \] 考虑 \(\mathcal D(n,tn+1;k)\) 中的任意元素 \(P\) ，因为 \(\frac{tn+1}{n} > t \geq 1\) ，所以前两步必然为 U。则设去掉第一 个 U 的路径为 \(P'\)。
因为 \(\forall x \in \mathbb{Z}\) ，\(tn \in \mathbb Z\)。所以去掉第一个 U 不会使得 \(P'\) 到 \(y = tx\) 下方去。
类似地，因为 \(y=\frac{tn+1}{n}x\) 与 \(y = tx\) 之间没有整点，所以加上一个 U 会让路径到 \(\frac{tn+1}{n}x\) 上面去。
因此两个集合一一对应。
定理 2.7 \(n\) 阶 \(\operatorname {t-Dyck}\) 路的个数是：
\[D(n,tn) = \frac{1}{tn + 1} \binom{tn + n}{n} \] **证明：** 随便化一下式子，然后范德蒙德卷积易证。
值得注意的是，卡特兰数本质就是 \(n\) 阶 \(\operatorname{t-Dyck}\) 路的 \(t=1\) 的特殊情况。即 \(D(n,n) = \frac{1}{n+1} \binom{2n}{n}\)。
定理 2.8 从 \((0,0)\) 到 \((n,m)\) 的有 \(k\) 个峰的 \(\operatorname{t-Dyck}\) 路的个数是：
\[D_t(n,m;k) = \frac{m+1-tn}{n} \binom{n}{k}\binom{m}{k-1} \] 定理 2.9 从 \((0,0)\) 到 \((n,m)\) 的 \(\operatorname{t-Dyck}\) 路的个数是：
\[D_t(n,m;k) = \frac{m+1-tn}{n+1} \binom{n+m}{n} \] 证明比较复杂。论文也没写。有兴趣翻参考文献。
\(2.6\) \(\operatorname{Dyck}\) 路的另一种等价定义
\(n\) 阶 \(\operatorname{Dyck}\) 路是在 \(x\) 轴上分以上步 \(U_1 = (1,1)\) ，下步 \(D = (1,-1)\) 从 \((0,0)\) 到 \((2n , 0)\) 的格路。这个很好理解。相当于将原格路旋转 \(45^\circ\)，然后做相应的缩放即可。
\(n\) 阶 \(\operatorname{t-Dyck}\) 路是在 \(x\) 轴上方以上步 \(U_t=(1,t)\)，下步 \(D=(1,-1)\)，从 \((0,0)\) 到 \(((t+1)n,0)\) 的格路。
\(n\) 阶 \(\operatorname{t-Dyck}\) 路的全体记作 \(\tilde{\mathcal D_t}(n)\)，\(\tilde{D_t}(n) = \# \tilde{\mathcal D_t}(n)\)。
\(\tilde {\mathcal D_t}(n)\) 和 \(\tilde D(n,tn)\) 之间存在双射。构造双射的一个方法如下：
对于 \(P\)，我们将其倒序得到 \(P'\)，然后把 \(L\) 替换为 \(U_t\)，\(U\) 替换为 \(D\) 即可。 这个还是可以利用将整个格子图旋转至对角线水平理解。
\(3\) 不相交格路
\(3.1\) \(n\) 阶不交 \(\operatorname{Dyck}\) 路计数
定义 \(3.1\) 从 \((0,0)\) 到 \((n,n)\) 的两条 \(\operatorname{Dyck}\) 路 \(P、Q\) 称为一个 \(n\) 阶 \(\operatorname{Dyck}\) 路对。若 \(Q\) 始终不穿过 \(P\)，则 \((P,Q)\) 是一个 不交 \(\operatorname{Dyck}\) 路对，否则称为 相交 \(Dyck\) 路对。
定理 3.1 \(n\) 阶不交 \(\operatorname{Dyck}\) 路对数为
\[\begin{vmatrix}C_n & C_{n+1} \\C_{n+1} & C_{n+2} \end{vmatrix} \] 其中，\(C_n = \frac{1}{n+1} \binom{2n}{n}\)，是卡特兰数的第 \(n\) 项。
证明： 构造映射 \((P,Q) \rightarrow (\tilde{P} , \tilde Q)\)，其中 \(\tilde P = UUPLL\)，\(\tilde Q\) 为将 \(Q\) 向 \((1,1)\) 平移一格后得到从 \((1,1)\) 到 \((n+1,n+1)\) 的 \(\operatorname {Dyck}\) 路。那么 \((P,Q)\) 相交当且仅当 \((\tilde P,\tilde Q)\) 有交点。而且没有交点的 \(\tilde P\) 一定满足开头是两个 U，结尾是两个 L。那么就是两个起点两个终点的 LGV 引理了。
定理 3.2 \(k\) 条 \(n\) 阶不交 \(\operatorname{Dyck}\) 路对数为
\[\det (C_{n-i-j})^k_{i,j=1} = \begin{vmatrix} C_{n-2}&C_{n-3} & \cdots& C_{n - k} & C_{n-k-1} \\C_{n-3}&C_{n-4} & \cdots& C_{n - k-1} & C_{n-k-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\C_{n-k-1} & C_{n-k-2} & \cdots & C_{n-2k-1} & C_{n-2k} \end{vmatrix} \] 证明： 这个也可以直接平移起终点然后 LGV 证。
\(3.2\) 不交自由路对计数
定义 3.2 设 \(P、Q\) 是两条自由路，如果 \(Q\) 始终不穿越 \(P\)，则称 \((P, Q)\) 是从 \((0, 0)\) 到 \((n, m)\) 的两条不交自由路对，用 \(F_{nc}\) 表示。如果 \(P、Q\) 除了起点以及终点之外没有公共点，则称 \((P, Q)\) 是一个不接触自由路对，用 \(F_{nt}\) 表示。
定理 3.3 从 \((0,0)\) 到 \((n,m)\) 的不接触自由路对个数是
\[F_{nt}(n,m) = \frac{1}{n} \binom{n+m-1}{n-1} \binom{n+m-2}{n-1} \] 证明： 想必不用证了，直接就是一个裸的 LGV，整理一下式子就是这个样子。
定理 3.4 从 \((0,0)\) 到 \((n,m)\) 的不交自由路对个数是
\[F_{nc} (n,m) = \frac{1}{n+1} \binom{n+m+1}{n}\binom{n+m}{n} \] 证明： 令 \(P\) 在 \(Q\) 上方，那么可以将 \(P\) 向上平移一格，将 \(Q\) 向右平移一格，那么不交就会变成接触。
然后在 \(P\) 最后加上一个 L，\(Q\) 最后加上一个 U 补全就可以得到 \(F_{nc}(n,m) = F_{nt}(n+1,m+1)\)。