浅谈卡特兰数（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}$ 个结点。