二叉树形态数推导 (Catalan 数)

问题：计算具有 n 个不同节点的不同形态二叉树数目（节点不可区分，只考虑拓扑结构）。

推导过程

1. 定义：

   • 设 ( C_n ) 表示 n 个节点的二叉树形态数
   • 基础情况：
     • ( C_0 = 1 )（空树）
     • ( C_1 = 1 )（单节点）

2. 递推关系（根节点 + 左子树 + 右子树）：

   • 根节点占用 1 个节点
   • 剩余 n-1 个节点分配给左子树（i 个节点）和右子树（n-1-i 个节点）
   • 递推公式：
     [
     C_n = \sum_{i=0}^{n-1} C_i \times C_{n-1-i}
     ]

3. 闭式解（Catalan 数）：
   [
   C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! , n!}
   ]

示例

n	形态数	二叉树示例
0	1	∅
1	1	●
2	2	● ●
		/ \
		● ●
3	5	见下图

n=3 的 5 种形态：
  ●       ●       ●       ●       ●
  /       /       / \       \       \
 ●       ●       ●   ●       ●       ●
  \       \               /       \
   ●       ●             ●         ●

---

K 叉树形态数推导 (Fuss-Catalan 数)

问题：推广到 k 叉树（每个节点最多 k 个子树）。

推导过程

1. 定义：

   • 设 ( C^{(k)}_n ) 表示 n 个节点的 k 叉树形态数
   • 基础情况：
     • ( C^{(k)}_0 = 1 )
     • ( C^{(k)}_1 = 1 )

2. 递推关系（根节点 + k 棵子树）：

   • 根节点占用 1 个节点
   • 剩余 n-1 个节点分配给 k 棵子树（每棵子树节点数非负整数）
   • 递推公式：
     [
     C^{(k)}n = \sum{\substack{i_1 + \dots + i_k = n-1 \ i_j \geq 0}} \prod_{j=1}^k C^{(k)}_{i_j}
     ]

3. 闭式解（Fuss-Catalan 数）：
   [
   C^{(k)}_n = \frac{1}{(k-1)n + 1} \binom{kn}{n}
   ]

特例验证

k	名称	n=0	n=1	n=2	n=3	公式
2	二叉树	1	1	2	5	(\frac{1}{n+1} \binom{2n}{n})
3	三叉树	1	1	3	12	(\frac{1}{2n+1} \binom{3n}{n})
4	四叉树	1	1	4	22	(\frac{1}{3n+1} \binom{4n}{n})

n=2 的三叉树形态（3 种）：
  ●         ●         ●
  │         │         │
  ●         ●         ●
  │        / \        │
  ●      ●   ●      ●

---

任意树形态数推导 (有序树 vs 无序树)

问题：n 个节点的不同树形态数目（子树数量任意）。

情况 1：有序树 (Ordered Tree)

子树顺序敏感（如 XML 结构）。

1. 递推关系：

   • 根节点占用 1 个节点
   • 剩余 n-1 个节点分配给子树序列（子树可为空）
   • 生成函数方程：
     [
     G(x) = x \cdot \frac{1}{1 - G(x)}
     ]

2. 闭式解（Catalan 数平移）：
   [
   \text{形态数} = C_{n-1} = \frac{1}{n} \binom{2n-2}{n-1}
   ]

情况 2：无序树 (Unordered Tree)

子树顺序不敏感（需考虑对称性）。

1. Pólya 计数理论：

   • 设 ( T(x) ) 为生成函数
   • 考虑子树对称群 ( S_m )（m 棵子树）
   • 方程：
     [
     T(x) = x \cdot \exp\left( \sum_{k=1}^\infty \frac{T(x^k)}{k} \right)
     ]

2. 解的特点：

   • 无显式闭式解
   • 前几项（n=0 到 4）：
     [
     1,\ 1,\ 1,\ 2,\ 3,\ \dots
     ]

形态数对比

n	有序树	无序树	差异原因
0	1	1	空树
1	1	1	单节点
2	1	1	只有 1 种可能结构
3	2	1	有序树区分子树位置
4	5	2	无序树合并对称结构
5	14	3	对称性减少计数

n=4 的无序树形态（2 种）：
  ●            ●
  ├─┬─┐        ├─┐
  ● ● ●        ● ●
               │
               ●

---

总结

1. 二叉树：
   [
   C_n = \frac{1}{n+1} \binom{2n}{n}
   ]

2. K 叉树：
   [
   C^{(k)}_n = \frac{1}{(k-1)n + 1} \binom{kn}{n}
   ]

3. 任意树：

   • 有序树：( \dfrac{1}{n} \binom{2n-2}{n-1} )
   • 无序树：无闭式解，使用 Pólya 计数或 Otter 公式

关键洞察：

• 二叉树和 k 叉树的形态数本质是 Fuss-Catalan 数
• 有序树形态数是 Catalan 数的平移
• 无序树需用 群论 处理对称性