Fuss-Catalan 数、(m-1)-Dyck 路与 m 叉树

· · 题解

Fuss-Catalan 数

定义 C_k(z) 满足

C_k(z) = 1 + z C_k^k(z)

有结论 [z^n] C_k^s(z) = \frac{s}{kn+s}\binom{kn+s}{n}，通过拉格朗日反演很容易证明，但此处不赘述。
当 s=1,k=2 时就统一到经典的 Catalan 数 \frac1{n+1} \binom{2n}n。

k-Dyck 路

考虑从 (0,0) 到 ((k+1)n,0) 的格点路径，其中只能走 (1,1) 或 (1,-k)，且不能走到 y=0 以下。

当 k=1 时就统一到许多常见的组合模型：括号序列、出栈序列、凸多边形三角划分、二叉树等。这也就是经典的 Catalan 数 \frac1{n+1} \binom{2n}n。

k 叉树

本文中考虑的 k 叉树满足每个结点必有 k 个儿子或没有儿子，其中有儿子的点称为内点，没有儿子的点称为外点。
容易发现此题即计数恰有 n 个内点的 m 叉树个数。

当 k=2 时就统一到经典的 Catalan 数 \frac1{n+1} \binom{2n}n。

一种联系

从 Symbolic Method 可以立刻建立起 k 叉树与 C_k(z) 的联系：后者即为前者的 OGF。
接下来，我们建立 k+1 叉树与 k-Dyck 路的双射，再介绍一种计数 k-Dyck 路的组合方法。

双射

树 -> 路

我们首先改写 k-Dyck 路为：第一步必为 (1,1)，最后走到 ((k+1)n+1,1)，且第一步之后不走到 y=1 以下的格点路径。
容易发现这样的 k-Dyck 路和原来的 k-Dyck 路也是一一对应的。

接下来我们考虑一棵 k+1 叉树如何映射到一条 k-Dyck 路。
首先在最前面添加一步 (1,1)；接下来从左往右考虑其 k+1 个儿子，将其各自子树所映射到的 k-Dyck 路接在已有的 k-Dyck 路后方；最后，如果这棵树的根结点为内点，则在最后添加一步 (1,-k)。
容易验证这样就可以得到一条合法的 k-Dyck 路。

路 -> 树

同样改写 k-Dyck 路。

从最后一步往前考虑一条 k-Dyck 路。若最后一步为 (1,-k)，则确定树的根结点为内点或外点；如为内点，则继续考虑倒数第二步，即可确定当前根结点最右的尚未确定的儿子为内点或外点，以此类推地递归构造即可。

k-Dyck 路计数

同样改写 k-Dyck 路。

考虑从 (0,0) 到 ((k+1)n+1,1)，不要求所有时刻不低于 y=1 的格点路径，我们可以将其映射到一个 k-Dyck 路：
考虑其最低点中最右方的位置，设其为 (x,y)；将 x 及以后的所有部分整体「剪切」到 (0,0) 开始的部分；接下来，将原路径中 x 以前的部分再直接接到其后方。容易发现这样满足条件。

不过这并不是双射。注意到对于一条 k-Dyck 路，其恰好可以映射到 (k+1)n+1 条如上的格点路径。
因此，k-Dyck 路的数量即为 \frac1{(k+1)n+1} \binom{(k+1)n+1}n。

这一方法也被称作是共轭原则，或者是环引理。
实际上，其在逻辑上与拉格朗日反演是等价的。

题解

因此，对于此题，直接使用 Lucas 定理计算 \frac1{nm+1} \binom{nm+1}n = \frac1n \binom{nm}{n-1} 即可。