趣题一则——合法轴对称括号串计数

前言

题目源于一个信奥经典笑话：计数合法回文括号串。读者可自行思考笑点在哪（）
吃中饭时以此笑话硬控 lc 数分钟，恼羞成怒的 lc 提出了合法“轴对称”括号串计数问题，随后我、xlj、lc 耗时一中午合力解决。

前置芝士

建议读者掌握卡特兰数的常见组合意义及其通项的常见推导方法。
以下以 $C(s)$ 表示卡特兰数， $C_m^k$ 表示组合数。

题目描述&概念解析

记 $f_n$ 为长为 $2n$ 的合法轴对称括号个数，求 $f_n$。

合法括号串的定义为：

1. 空串为合法括号串。
2. 若 s 为合法括号串，则 (s) 也是合法括号串。
3. 若 a、b 均为合法括号串，则 ab 也是合法括号串。

轴对称定义为：
若 $s_i$ 为 (，则 $s_{2n-i+1}$ 必为 )，反之亦然。

例如，())(() 不是合法括号串， ()(()) 是合法括号串但不轴对称， (()()) 是合法轴对称括号串。

递推做法

由于该串具有“轴对称”的性质，以下我们仅计数该串的左半部分。
若记 ( 为 1，) 为 -1，则左半部分所有前缀和均非负。
易证这是充要条件。

由于长为 $n+1$ 的合法左半部分的前 $n$ 个字符必然也构成合法串，因此我们考虑由 $f_n$ 转移得到 $f_{n+1}$。
分类讨论 $n$ 的奇偶性。
$n$ 是奇数，前 $n$ 个前缀和不为 $0$ 即至少为 $1$，因此后加 (、) 均合法， $f_{n+1}=2f_n$。
$n$ 是偶数，前 $n$ 个前缀和为 $0$ 时构成合法括号串，由卡特兰数定义知方案数为 $C(n/2)$，此时只可后加 (，否则还是加 (、) 均合法，$f_{n+1}=2f_n-C(n/2)$。

通项的推导

作为信奥选手得到如上递推式已经满意了，毕竟即使计算通项也难以避免线性复杂度。
但把它看作数学题的话，我们希望得到更简洁的通项。

类似推导卡特兰数的过程，我们考虑将括号串转化为在网格图上行走，记 ( 为向左，) 为向上，则括号串等价于行走时始终在直线 x=y 下方（含）的情况下走到直线 x+y=n。下图中红色部分便是 n=12 时的一种合法路径。

还是先考虑 $n$ 为偶数的情况。类似卡特兰数的推导，我们用走到线段 $BC$ 的方案数减去跨过线段 $AB$ 后走到的，然后将不合法的方案第一次到达直线 y=x+1 （下图中青色直线 $LI$）之后的步骤翻折（向右、向上交换），可知不合法方案数等价于 $n$ 步内走到线段 $DM$ 的方案数。下图中的两条深蓝色路径分别对应两条红色路径的翻折。

注意到线段 $BM$ 与线段 $BC$ 是关于直线 $AB$ 对称的！即，到达 $DM$ 方案数等于到达 $BC$ 方案数减去到达点 $B$ 方案数，为 $C_n^{\frac{n}{2}}$。

如果没有直接观察到这一点，简单计算后也会得到相同结果。
具体的，到达 $BC$ 方案数为 $\frac{2^n+C_n^{\frac{n}{2}}}{2}$，到达 $DM$ 方案数为 $\frac{2^n-C_n^{\frac{n}{2}}}{2}$。

由递推式可以得到，$n$ 为奇数时，

$$f_n=2f_{n-1}-C(n-1)=2C_{n-1}^{\frac{n-1}{2}}-(C_{n-1}^{\frac{n-1}{2}}-c_{n-1}^{\frac{n-1}{2}-1})\\ =C_{n-1}^{\frac{n-1}{2}}+C_{n-1}^{\frac{n-1}{2}-1}=C_n^{\frac{n-1}{2}}$$

即对于所有 $n$，有 $f_n=C_n^{\lfloor\frac{n}{2} \rfloor}$。
经过手玩小数据，我们认为这个答案是正确的。
事实上，根据递推式硬算或是借助杨辉三角理解，我们都很容易证明其正确性。

更直观的组合意义

我们观察到这个看似复杂的问题有个非常好看的答案 $C_n^{\lfloor\frac{n}{2} \rfloor}$，从推导中也看出这等价于只向右向上从 $(0,0)$ 走到 $(\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil)$ 的方案数。那么，有没有更直观的方法让我们看出这个答案的正确性？
比如说，我们能不能构造一个简单映射使得 从 $(0,0)$ 走到 $(\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil)$ 的方案（下称路径A） 与 限制下走到线段 $BC$ 的方案（下称路径B）一一对应？

这是可行的。建议读者自行思考一小会后再阅读以下内容。

还是先考虑 $n=2k$ 的情况。
我们在构造映射时发现只有一条路径A 到达点 $(n,0)$，也只有一条路径B 经过点 $(0,k)$，于是尝试使这两条路径形成映射。

进一步地，我们猜想：是否到达点 $(k+t,k-t)$ 的路径A数量 恰好等于 路径上经过的点坐标 $y-x$ 最大值为 $t$ 的路径B的数量？
$\tiny{\text{即恰好碰到、不越过直线}y=x+t\text{的路径B}}$

是这样的。由于懒得推导，我使用如下代码（已省略头部分）在 $n$ 较小时验证了其正确性。推导留给读者作习题。

const int N = 110;
int __, n, lsa, f[N][N], g[N][N];
void initg() {
    g[0][0] = 1;
    for (int i = 1; i <= n * 2; i++)
        for (int j = 0; j <= i; j++) {
            g[i][j] = g[i - 1][j];
            if (j) g[i][j] += g[i][j - 1];
        }
}
int chk1(int t) { // (0,0) -> (n+t,n-t)
    return g[n + t][n - t];
}
int chk2(int t) { // max{y-x} = t
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= t; i++) f[0][i] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i + t; j++) {
            f[i][j] = f[i - 1][j];
            if (j) f[i][j] += f[i][j - 1];
        }
    int res = f[n][n] - lsa;
    lsa = f[n][n];
    return res;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; // (0,0) -> (n,n)
    initg();
    for (int i = 0; i < n; i++)
        cout << i << ":" << chk1(i) << ' ' << chk2(i) << endl;
    return 0 ^ __ ^ 0;
}

我们发现确定了路径B 经过的 $y-x$ 最大的点（记为 $(x_0,y_0)$，$y_0=x_0+t$，有多个时取 $x$ 最大的）后，该路径有非常好的性质。

具体的，从 $(x_0,y_0)$ 往后，该路径上每一步都满足 $(x-x_0)-(y-y_0)>0$ 即向右多于向上；往前，每一步都满足 $(y_0-y)-(x_0-x)\ge 0$ 即向下不少于向左。此外，往后部分总的 向右步数-向上步数 恰好等于往前部分总的 向上步数-向右步数，均为 $t$。

于是我们将该路径前 $x_0+y_0$ 步翻转（右变上，上变右）然后反向（从后往前执行每一步），再拼接上后半部分，就得到了一条合法路径A。

同理，对于一条到达 $(k+t,k-t)$ 的路径A，我们找到其最后一次经过满足 $x_1-y_1=t$ 的点 $(x_1,y_1)$，将路径前 $x_1+y_1$ 步翻转后反向，就得到了一条合法路径B。

下图中的红色、深蓝色路径对应一种路径A 和路径B 的映射。

这样构造出的路径是一一对应的，读者可自行思考证明，应该是容易的，并且还存在不少类似的构造方式。
$n$ 为奇数时的情况是类似的，这里不再赘述。

由此我们便构造出了较直观的对其通项的证明。希望可以对大家有所启发，也欢迎大家关于证明过程进行探讨。