卡特兰数的自卷积

Cry_For_theMoon · 2023-05-25 17:59:14 · 个人记录

卡特兰数生成函数 m 次幂的研究（F^{m}(x)）：

我们设 C_n 表示 n 个左括号，n 个右括号构成的合法括号序列个数，则有：

下面这个卷积的意义是：我们考虑一个括号序列的最外层若干对括号：(...)(...)(...)（当 n\ge 1 时至少有一个），我们分为两部分：前面若干对（可能为零对）和最后一对。然后枚举的是第一部分的左右括号个数 i，显然这部分就是 C_i，剩下的 n-i 对左右括号最外层是一个大的 (...) 所以我们能自由决定的只有里面的 n-i-1 对左右括号的分配。所以是 C_i\times C_{n-i-1}。

暴力算出前几项是 1,2,5,14,42,...，也容易验证正确性。

把上述转移写成生成函数形式：设 F(x) = \sum_{n\ge 0}C_nx^n，则我们可以写出这样的转移：

因此计算 [x^n]F^2(x) 是容易的，因为 xF^2(x)=F(x)-1，所以 [x^n]xF^2(x)=C_x-[x=1]，而 [x^n]F^2(x)=[x^{n+1}]xF^2(x)=C_{n+1}，换言之卡特兰数和自身卷积一次过后，得到的结果序列相当于卡特兰数整体左移一位。

举例：[x^4]F^2(x)=2(C_0C_4+C_1C_3) + C_2^2 = 2\times (14 + 5) + 4 = 42 = C_5。

因此 m\le 2 的情况是平凡的，但是当我们将 m 扩大，当 m=3 的时候这个性质就不再成立：我们得到的结果甚至不是卡特兰数。

例如：m=3 的时候，[x^n]F^3(x) 的 0\sim 4 项分别为：1 3 9 28 90。可以看出后面几项都不是卡特兰数。

下面我们来考虑通过组合意义研究 [x^n]F^{m}(x) 的真实值。

考虑这样一个问题：

问长度为 2n 的，最外层恰有 m 对括号的合法括号串数。 其中 1\le m\le n。

我们钦定了外层有 m 个 (...)，现在要做的就是往这 m 个括号里都去塞一个（可空）括号串，这 m 个括号串的长度和为 2(n-m)。

因此这个问题的答案实质上就是 [x^{n-m}]F^{m}(x)。

事实上这个问题还有另外一个方向：

考虑把 m 对括号里面的串分别记作 S_1,S_2,...,S_m，则 \text{(S_1)(S_2)...(S_m)} 就是我们要计数的一个串，它和 \text{(((...(S_1)S_2)...)S_m} 这样的串一一对应。

这个对应过程实质上是这样：以 m=5 为例，我们把 m-1 对括号嵌套在一起变成 ((((a)b)c)d)e 这样一个超级大结构，然后在 a 的位置填入 S_1，b 的位置填入 S_2，以此类推，最后 S_5 放在最外层。

不难看出两类串的个数形成一一对应。这一部分的转化和核仁在 APIO2023 题目选讲里提到的是一致的。

对于转化后的问题：我们在 (n-1)\times (n-1) 的网格图上考虑，则相当于先一口气向右走 m-1 步然后走到 (n-1,n-1) 且中途不越过 y=x 这条折线的方案数。

考虑比较经典的反射容斥：把不越过 y=x 变成不经过 y=x+1 这条直线，然后任何一条经过 y=x+1 的直线，我们只需要将起点(m-1,0) 关于这条直线对称过去得到 (-1,m) 即可。换言之：任何一条从 (m-1,0) 出发的不合法路径，和一条从 (-1,m) 出发的随意一条路径（当然行走方式依旧是每一步向上或者向右）形成一一对应。

因此方案总数是 \dbinom{2n-m-1}{n-1}，而不合法方案数是 \dbinom{2n-m-1}{n}。

所以上述问题的答案，也就是 [x^{n-m}]F^m(x) 即为 \dbinom{2n-m-1}{n-1}-\dbinom{2n-m-1}{n}。

因此，不难得到：

其中 m\ge 1。