由于卡特兰(Catalan)数经常会在算法题或面试题中出现,在这里做一下小小的总结。
卡特兰数是组合数据中一个常在各种计数问题中出现的数列,由比利时的数学家欧仁.查理.卡特兰(1814-1894)命名。
Catalan数的定义:令h(0)=1,Catalan数满足递归式:h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=0)。该递推关系的解为:h(n) = C(2n-2,n-1)/n,n=1,2,3,...(其中C(2n-2,n-1)表示2n-2个中取n-1个的组合数)。
卡特兰数:规定h(0)=1,而h(1)=1,h(2)=2,h(3)=5,h(4)=14,h(5)=42,h(6)=132,h(7)=429,h(8)=1430,h(9)=4862,h(10)=16796,h(11)=58786,h(12)=208012,h(13)=742900,h(14)=2674440,h(15)=9694845。
卡塔兰数的一般项公式为:
另一个表达形式:
满足递推关系:
也满足:
这提供了一个更快速的方法来计算卡塔兰数。
关于卡特兰数的概念就介绍到这里,后面再补充其它方面的知识。
现代魔法 推荐于 2013-02-27 10:23