前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >卡特兰数入门

卡特兰数入门

作者头像
attack
发布2018-04-11 15:36:00
8400
发布2018-04-11 15:36:00
举报
文章被收录于专栏:数据结构与算法

简介

卡特兰数是组合数学中的一种常见数列

它的前几项为:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452

公式

递归公式1

f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)

递归公式2

f(n)=\frac{f(n-1)*(4*n-2)}{n+1}

组合公式1

f(n)=\frac{C_{2n}^n}{n+1}

组合公式2

f(n)=C_{2n}^n-C_{2*n}^{n-1}

这四个公式了解即可:joy:(众人:*******:angry:

最后一个,最重要的公式,必须要掌握的公式!!

递推公式

f[n]=\sum_{i=0}^{n-1}f[i]*f[n-i-1]

一般在做题的时候,都是利用这个公式进行递推

证明

不会:stuck_out_tongue_closed_eyes:。(众人:那你在这瞎bb啥。:triumph:

这个东西的证明我确实不会

不过我在这里教大家一种非常简单易懂的记忆方法,

记f[n]为卡特兰数的第n项

首先你要明白一件事情

一棵n个节点的二叉树的形态总数就是卡特兰数的第n项

对于一棵二叉树,递归的考虑

一棵只有一个节点的二叉树只有一种形态

对于不是一个节点的二叉树,按照他的左右孩子进行讨论

设它的左孩子有i个节点,那么它的形态数为f[i]

那么它的右孩子有n-i-1个节点,那么它的形态数为f[n-i-1]

又因为每一个节点都可以作为根节点

所以不难得到递推式

f[n]=\sum_{i=0}^{n-1}f[i]*f[n-i-1]

例题

都是裸题我就不细讲了

洛谷P1722 矩阵 II

http://www.cnblogs.com/zwfymqz/p/7725346.html

洛谷P1044 栈

洛谷P1976 鸡蛋饼

http://www.cnblogs.com/zwfymqz/p/7725386.html

总结

卡特兰数是一种常见的数列

需要每一位选手掌握它的递推式

卡特兰数一般不会单独出现,往往会出现在一些题目的部分分中,如2017某省省选(具体忘记了。)

在考场上,要证明一个东西是卡特兰数是非常困难的

自己手玩点小数据,只要前几项吻合,那一般就是卡特兰数啦

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-11-06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简介
  • 公式
  • 证明
  • 例题
    • 洛谷P1722 矩阵 II
      • 洛谷P1044 栈
        • 洛谷P1976 鸡蛋饼
        • 总结
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档