卡特兰数入门

简介

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

它的前几项为:

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某省省选(具体忘记了。)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ImportSource

必须知道的Spring Boot中的一些Controller注解

本文旨在向你介绍在Spring Boot中controller中最基本的一些注解,不可能涵盖所有的,但至少让你了解最基本的,然后可以通过这些注解来写出一个API...

4.7K100
来自专栏性能与架构

CSS选择器是如何确定优先级的?

先看下面的示例 <div id="content"> <p id="title">Hello world</p> </div> 有如下的2个css选择器...

320100
来自专栏码神联盟

碎片化 | 第五阶段-02-公司IT部门的组成介绍-视频

如清晰度低,可转PC网页观看高清版本: http://v.qq.com/x/page/l0500zwsius.html 企业IT部门组成 ?

31660
来自专栏猿天地

hbuilder 开发5+ APP采坑记录

开发一款APP产品需要在安卓和苹果2大平台发布,同时开发团队也需要有安卓和IOS。 HTML5 Plus移动App,简称5+App,是一种基于HTML、JS、C...

95990
来自专栏码神联盟

碎片化 | 第六阶段-04-搭建nginx和Tomcat集群环境-视频

如清晰度低,可转PC网页观看高清版本: http://v.qq.com/x/page/g0500ly03ud.html Ngnix+Tomcat集群 1:修改...

28770
来自专栏码神联盟

碎片化 | 第七阶段-11-小明的故事之集群、负载、并发-视频

如清晰度低,可转PC网页观看高清版本: http://v.qq.com/x/page/h0500917nyz.html 分布式、集群、高并发、负载、缓存、云端...

29570
来自专栏码神联盟

碎片化 | 第四阶段-55-OpenSessionInViewFilter组件配置解决session问题-视频

如清晰度低,可转PC网页观看高清版本: http://v.qq.com/x/page/s05686to2z4.html OpenSessionInViewFi...

345110
来自专栏数据小魔方

用R语言抓取网页图片——从此高效存图告别手工时代

今天这个标题实在是有点言过其实了,对于R的爬虫知识,我只是领会了一点儿皮毛。 主要看不懂正则表达式,特别是那种一个括号里要匹配多种类型文本的语句,特像火星文,估...

562110
来自专栏互联网杂技

40个重要的HTML 5面试问题及答案

目录 介绍 SGML、HTML、XML和XHTML之间的关系? 什么是HTML 5? 如果我不输入<!DOCTYPE HTML>,HTML 5能工作吗? 哪些浏...

697130
来自专栏性能与架构

影子(Shadow) DOM

什么是 Shadow DOM? Shadow DOM 是一个革命性的新技术,先来看下他是什么样子的 以<video>标签为例非常适合,例如 <video ...

39880

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励