NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 22 题

结点数为 $5$ 的不同形态的二叉树一共有_________种。（结点数为 $2$ 的二叉树一共有 $2$ 种：一种是根结点和左儿子，另一种是根结点和右儿子。）

这题考二叉树形态计数，本质是卡塔兰数。拿到题别慌，直接套公式 Cn=(2n)!/((n+1)!n!)，代入 n=5 算阶乘比值就行，或者用递推 f(n)=Σf(i)f(n-1-i) 从 f(0) 推到 f(5) 也行。

学生最容易把二叉树形态和树同构搞混，以为左右子树对称就算一种，其实二叉树左儿子和右儿子位置不同就是不同形态。还有人会记错递推式下标，把 f(n-1-i) 写成 f(n-i) 导致算出 420 这种离谱数。另外计算阶乘时容易把 10! 算错成 3628800 以外的数，或者除法时分母漏掉 (n+1)! 直接算成组合数 C(10,5)=252 就停手了，忘了除以 6。

考点概念：二叉树形态与卡塔兰数

n 个结点的不同形态二叉树个数等于第 n 个卡塔兰数 C_n。卡塔兰数公式是 C_n = (2n)! / ((n+1)!·n!)。递推式是 f(n) = Σ_{i=0}^{n-1} f(i)·f(n-1-i)，其中 f(0)=1。前几项是 f(0)=1, f(1)=1, f(2)=2, f(3)=5, f(4)=14, f(5)=42。

命题视角：为什么考这个？

命题人喜欢用具体小数字（n=5）让考生现场算，而不是背公式。坑点在于：1）递推式下标容易写错；2）组合数 C(10,5) 算出来是 252，但二叉树形态要再除以 (n+1)=6，得到 42，很多人会停在 252；3）把二叉树当成无序树（左右对称算一种），就会少算一半以上。