• 卡特兰数通项公式在TAOCP里的推导

    自行研究!
    服务器君一共花费 54.226 ms 进行了 3 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

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

    至于怎么推导,《计算机程序设计艺术(卷一)》2.2.1节习题4的解答提到的精彩解法“反射原理”,下面是对其的概括:

    问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n)。

    显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件)。

    在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置。然后在导致并包括这个X的部分序列中,以S代替所有的X并以X代表所有的S。结果是一个有(n+1)个S和(n-1)个X的序列。反过来,对一垢一种类型的每个序列,我们都能逆转这个过程,而且找出导致它的前一种类型的不允许序列。例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS。这个对应说明,不允许的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1)。

    具体可以看看TAOCP的原练习题:

    这里翻书确认了一下Knuth援引的卡特兰数通项的证明方法,有兴趣可以自己研究一下。

更多 推荐条目

Welcome to NowaMagic Academy!

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

本章最新发布
随机专题
  1. [Python程序设计] urls.py设置技巧 8 个条目
  2. [移动开发] Android Studio的使用技巧 4 个条目
  3. [Python程序设计] Django与表单 4 个条目
  4. [Python程序设计] Tornado 服务器环境配置 3 个条目
  5. [移动开发] Android根基概念Context 8 个条目
  6. [软件工程与项目管理] 呈现器的布局与绘制 11 个条目
  7. [JavaScript程序设计] Web实时通信技术名词解析 5 个条目
  8. [智力开发与知识管理] 学习编程为什么没会这么难? 7 个条目
  9. [运维管理] 路由器与交换机 4 个条目
  10. [移动开发] Android与SQLite数据库 7 个条目
  11. [PHP程序设计] PHP里的布尔类型 3 个条目
  12. [PHP程序设计] 命令式编程范式 6 个条目
窗口 -- [八点]