NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 8 题

关于 Catalan 数 $C_n = \dfrac{(2n)!}{(n + 1)!n !}$，下列说法中错误的是（ ）。

这题考的是卡塔兰数（Catalan 数）的四种经典组合意义。拿到题先别急着套公式，脑子里过一遍那四个场景：二叉树、括号匹配、出栈序列、多边形三角剖分。关键要盯准每个场景里数字 n 到底代表什么——是结点数、括号对数、元素个数，还是边数。命题人最喜欢在“结点个数”和“边数”这种容易混淆的地方挖坑，让你把 n 和 n+1 搞混。只要把这四个对应关系记牢，一眼就能看出 A 选项哪里不对劲。

学生最容易栽跟头的地方，就是把卡塔兰数里 n 的含义记混了。比如看到选项 A 说“n+1 个结点”，下意识觉得二叉树就是 n+1 个结点，其实标准定义里 C_n 对应的是 n 个结点。再比如选项 D 说“n+2 边”，很多人会误以为是 n 边，忽略了多边形的边数比顶点数多 2 这个几何事实。还有括号问题，C_n 对应的是 n 对括号，不是 n 个括号。这些坑都是命题人专门设计的，因为看起来很像，但数字差一，结果就全错了。一定要把每个场景的 n 指代对象背得清清楚楚，别靠感觉猜。

考点概念：卡塔兰数（Catalan）

卡塔兰数 C_n 的通项公式是 C_n = (2n)! / ((n+1)! · n!)。它之所以重要，是因为它在组合数学里对应着好几个经典模型，而且这些模型里 n 的含义虽然不同，但都指向同一个数列。解题的关键就是把这些模型和公式里的 n 对应起来。

命题视角：爱在“数字差一”处挖坑

命题人出这类题，从来不是让你死记硬背公式，而是考你对组合意义的理解。他们最喜欢在“数字差一”的地方设陷阱。比如二叉树，C_n 对应的是 n 个结点的不同形态二叉树个数，而不是 n+1 个结点。多边形三角剖分，C_n 对应的是 n+2 条边的凸多边形，而不是 n 条边。括号序列，C_n 对应的是 n 对括号，而不是 n 个括号。这些陷阱看起来很像，但数字差一，结果就全错了。所以拿到题，第一反应应该是：“这个 n 到底指代什么？”