Catalan数及其应用

1. 定义

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名，其前几项为 :

1, 2, 5, 14, 42, 132...

递推式：
令h(0)=1,h(1)=1,

(1) Catalan数满足递推式：
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)

e.g., h(2) = h(0)*h(1) + h(1)*h(0) = 2.

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

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

(4) h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

2. 应用

(1) 括号化

矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n-1)种)

Catalan数及其应用

原文：http://www.cnblogs.com/harrygogo/p/4568752.html