卡特兰数（Catalan number）

licn · 2023-07-22 15:45:24 · 算法·理论

引入

卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。通常用 C_n来表示。

数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，...

与我们熟知的斐波那契数列类似都是一个通过递推得到的数列。相较于斐波那契数列，卡特兰数还可以用数学的组合数公式表示出来。

递推式

我们先来推导一下卡特兰数的递推式。 来看一个相对好想的例题：

一个凸 (n+2)边形用其 (n-1)条对角线将其分割为互不重叠的三角形，有多少种方法？

当 n=1 时：

构成了一个三角形，显然只有一种分发，C_1=1。

当 n=2 时：

四边形共有两种分发法，C_2=2。

通过观察发现：无论怎么分任意一边总是一个三角形的边。 那么我们只需要以任意一条边来构建三角形来计算。 我们以 CD 为边来计算。

先连接 BD：

左边没有图形，右边构成了一个四边形。那么左边的方法数是 C_0,右边的方法数是 C_2。根据加法原理连接先构成三角形 BCD 的方法数是：C_0 \times C_2。显然我们规定 C_0=1 。那么我们在依次构成三角形 ACD 和三角形 ECD。

其方法数分别为 C_1 \times C_1 和 C_2 \times C_0。那么 C_3=C_0 \times C_2+C_1 \times C_1+C_2 \times C_0 。由此我们推出了卡特兰数的递推式：C_n=\sum_{k=0}^{k<n}C_k \times C_{n-k-1}。

代码实现：

void Catalan(int n)
{
    if(C[n])return;
    for(int k=0;k<n;k++)Catalan(k);
    for(int k=0;k<n;k++)C[n]+=C[k]*C[n-k-1];
}