浅谈卡特兰数（Catalan数）

卡特兰数的定义

卡特兰数是组合数学中一个常在各种计数问题中出现的数列。

卡特兰数的一般项公式为 \[ C_n = \frac{1}{n+1} \dbinom{2n}{n} = \frac{(2n)!}{n!(n+1)!}\quad (n\in \mathbb{N}) \tag{1} \] 还有以下常见公式 \((n \in \mathbb{N})\) \[ C_0=1,~C_1=1\\ C_n = \sum_{i=1}^{n} C_{i-1}C_{n-i},\quad n \ge 2\tag{2} \]

\[ C_n = \frac{(4n-2)C_{n-1}}{n+1} \tag{3} \]

\[ C_n = \dbinom{2n}{n}-\dbinom{2n}{n-1} \tag{4} \]

OEIS A000108

这张表很重要。因为有时候想不出来可以手推前几项猜卡特兰数。

\(n\)	0	1	2	3	4	5	6	\(\cdots\)
\(C_n\)	1	1	2	5	14	42	132	\(\cdots\)

我们可以用如下代码计算卡特兰数的第 \(n\) 项（~~改不了C++行末分号的习惯了~~）

n = int(input()); 
if(n == 0 or n == 1): print(1); exit(0); 
fac = [0 for i in range(2*n+5)]; fac[0]=1; 
for i in range(1, 2*n+1): fac[i] = fac[i-1] * i; 
print(fac[2*n] // (fac[n] * fac[n+1]))

卡特兰数的应用

有好多，这里就列举几个常见的。

1. 合法括号序列（Dyck word）

\(C_n\) 表示长度为 \(2n\) 的合法括号序列的个数。

注：a Dyck word is a balanced string of square brackets [ and ].

Dyck word是一个有 \(n\) 个 X 和 \(n\) 个 Y 组成的字串，且所有的前缀字串皆满足 X 的个数大于等于 Y 的个数。

以下为长度为 \(6\) 的 Dyck words

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

2. \(n\times n\) 的格点中不越过对角线的单调路径

\(C_n\) 表示所有 \(n\times n\) 的格点中不越过对角线的单调路径的个数。

一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。

计算这种路径的个数等价于计算Dyck word的个数：X代表“向右”，Y代表“向上”。

以下为 \(n=4\) 的情况

3. \(n\) 个结点的不同构二叉树

\(C_n\) 表示 \(n\) 个结点的不同构有根二叉树（无标号）的个数。

以下为 \(n=3\) 时的情况：

\(C_n\) 也能表示 \(2n+1\) 个结点的不同构有根满二叉树（无标号）的个数。

以下为 \(n=3\) 时的情况。

这里的满二叉树采用国外的定义。

国外定义：树上任何结点，如果不是叶子结点，则一定有 \(2\) 个儿子。

国内定义：\(2^k-1\) 个结点，第 \(i(i\ge 1)\) 层有 \(2^{i-1}\) 个结点。