二叉树的计数问题：给定 $n$ 个互不相同的结点，问能构成多少棵结构不同的二叉树（结点值视为可区分，只关心形状；若结点值固定，则每棵形状对应一种标号方式）。
答案是著名的卡特兰数（Catalan number）：
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$$设 $b_n$ 为 $n$ 个结点的二叉树数量，则满足递推：
$$b_n = \sum_{i=0}^{n-1} b_i\,b_{n-1-i},\quad b_0 = 1$$该递推的解正是卡特兰数：$b_n = C_n$。
从递推出发可推得 $C_n = \frac{1}{n+1}\binom{2n}{n}$，也可用生成函数法证明。
# 递推计算前 n 项卡特兰数
C = [0]*(n+1); C[0] = 1
for i in range(1, n+1):
for k in range(i):
C[i] += C[k] * C[i-1-k]
# C[i] 即 i 个结点的二叉树数量| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| $C_n$ | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 |
3 个结点共有 $C_3 = 5$ 棵不同形状的二叉树，如下图所示：
$n$ 个结点的二叉树数量 = 第 $n$ 个卡特兰数：
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$递推：$C_0=1,\ C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}$。前几项 1,1,2,5,14,42,132,429。