• 卡特兰(Catalan)数概念的简要介绍

    先说点概念的东西
    服务器君一共花费 12.393 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    由于卡特兰(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。

    • 1 h(0)=1
    • 1 h(1)=h(0)*h(0) = 1
    • 2 h(2)= h(0)*h(1) + h(1)*h(0) = 1 + 1 = 2
    • 5 h(3)= h(0)*h(2) + h(1)*h(1) + h(2)*h(0) = 2 + 1 + 2 = 5
    • 14 h(4)= h(0)*h(3) + h(1)*h(2) + h(2)*h(1) + h(3)*h(0) = 5 + 2 + 2 + 5 = 14
    • 42 h(5)= h(0)*h(4) + h(1)*h(3) + h(2)*h(2) + h(3)*h(1) + h(4)*h(0) = 14 + 5 + 4 + 5 + 14 = 42
    • ……

    卡塔兰数的一般项公式为:

    另一个表达形式:

    满足递推关系:

    也满足:

    这提供了一个更快速的方法来计算卡塔兰数。

    关于卡特兰数的概念就介绍到这里,后面再补充其它方面的知识。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [PHP程序设计] PHP中的Hash算法 3 个条目
  2. [计算机算法] TAOCP与算法 12 个条目
  3. [PHP程序设计] htaccess 设置技巧 6 个条目
  4. [JavaScript程序设计] jQuery与表单操作 2 个条目
  5. [运维管理] 防火墙原理与应用 5 个条目
  6. [运维管理] 路由器与交换机 4 个条目
  7. [数据库技术] MySQL常用自带函数 3 个条目
  8. [移动开发] Android加载器Loaders 5 个条目
  9. [数据结构] 散列表(哈希表) 13 个条目
  10. [计算机算法] 从双端队列引出的卡特兰数 3 个条目
  11. [Python程序设计] Django Web环境配置 2 个条目
  12. [Linux操作系统] 基本 Linux Shell 命令 2 个条目
窗口 -- [博客]