NOIP 提高 2018 第一轮 第 8 题：关于Catalan 数Cn=(2n)!／(n+1)!／n！，下列说法中错误的是（

题目

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

选项

• A. $C_n$ 表示有 $n + 1$ 个结点的不同形态的二叉树的个数。
• B. $C_n$ 表示含 $n$ 对括号的合法括号序列的个数。
• C. $C_n$ 表示长度为 $n$ 的入栈序列对应的合法出栈序列个数。
• D. $C_n$ 表示通过连接顶点而将 $n + 2$ 边的凸多边形分成三角形的方法个数。

答案

A

题解

考点定位

Catalan 数的计数对象与下标。

解题过程

Cₙ 可以表示 n 个结点的有序二叉树形态数。A 写成 n+1 个结点，对应的应是 Cₙ₊₁，因此 A 错误。

其余三项都是 Cₙ 的经典模型：n 对括号的合法序列、n 个不同元素按固定顺序入栈所能产生的合法出栈序列，以及 n+2 边凸多边形的不相交三角剖分。

选 A。

易错提醒

“n 个结点的二叉树”和“n+1 个叶子的满二叉树”是不同表述，不要把叶子数替换为总结点数。