2017 August 23

卡特兰数

卡特兰数(Catalan Numbers)是组合数学中经常出现在各种计数问题中的数列，前几项为：1,2,5,14,42,132,429,1430,4826,16796。

递推关系

令h(0)=h(1)=1，那么卡特兰数满足递推式：

h(n) = h(0) * h(n-1) + h(1) * h(n-2) + ... + h(n-1) * h(0)   (n>=2)

也可表示成：

h(n) = h(n-1) * (4n-2) / (n+1)    (n>=1)

对上述递推式求解，可得通项公式：

h(n) = C(2n,n) / (n+1)    (n>=0)

也可以写成：

h(n) = C(2n,n) - C(2n,n-1)   (n>=0)

要计算卡特兰数，简单的做法是根据递推式直接推。

#include <stdio.h>
typedef long long LL;
LL h[30] = {1, 1};
int main() {
    int i;
    for (i = 2; i <= 30; i++)
        h[i] = h[i-1] * (4 * i - 2) / (i + 1);
    return 0;
}

由于增长较快，int64范围内所能表示的最大卡特兰数为h(33)，往后的卡特兰数需用高精。

卡特兰数的应用

Table of Contents