引子——括号匹配问题

2n 个'('和')'组成的括号序列, 有多少种合法的组合方法?
把括号从 0 到 2n-1 编号, 合法的序列第 0 个一定是 '(' , 假设第 0 个括号与第 k 个括号匹配, 则序列 [1 ... k-1] 和 [k+1 ... 2n-1] 应也是合法的括号序列, 所以 k 必须是奇数, 设 k=2i+1 , 得公式:

如果换种说法, n 对括号的序列, 可得更简单的公式:

进一步证明

如果 '(' 看做是入栈, ')' 看做是出栈, 则 2n 个括号的合法序列, 一一对应于 2n 步合法的入栈出栈序列.
n 步入栈 n 步出栈的序列总数为 . 对于一个不合法的序列, 一定会在某一步(设为 2i+1 )发现此时遇到的出栈符号数多于入栈符号数, 即遇到了 i 个 '(' 和 i+1 个 ')'. 此时后面还有 n-i 个 '(' 和 n-i-1 个 ')', 如果将后面的 '(' ')' 互换则得到 n-1 步入栈 n+1 步出栈的序列, wikipedia 上说, 两者是一一对应的, 即一个不合法的 n 入 n 出序列(我擦我XE了), 一一对应了一个 n-1 入 n+1 出的序列. 所以可得公式:

化简得方便的计算公式:

应用

有一大票的问题可以归约到卡特兰数上, 看书也经常会看到把这个当做公式用在和式相关的证明中. wikipedia 上说某书列了66个可以归约到卡特兰数的问题(orz). 一般问题要么可以归约到括号匹配问题, 要么可以归约到入栈出栈问题, 比如:

• n+1 个矩阵连乘的括号化方案数, 可以归约到 n 对括号匹配问题, 所以为 Cn
• 所有在 n×n 格点中不越过对角线的单调对角路径的个数, 可以归约到入栈出栈序列问题, 所以为 Cn
• 有 n+1 个叶子的二叉树的个数, 括号匹配, Cn
• 给定 n 个节点，能构成多少种不同的二叉树, 括号匹配, Cn
• 长度 2n 的dyck word的个数, 入栈出栈序列, Cn
• 通过连结顶点(连接线不相交)而将 n+2 边的凸多边形分成三角形的方法个数, 括号匹配, Cn
• n 个长方形填充一个高度为 n 的阶梯状图形的方法个数, 大概是括号匹配, 不明显不好证, Cn