算法 - Catalan数 (卡特兰)
2024-08-27 07:27:28
http://blog.csdn.net/linhuanmars/article/details/24761459
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的前缀字串皆满足X的个数大于等于Y的个数。
Cn的另一个表达形式为
所以,Cn是一个自然数;这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。)
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
卡塔兰数的渐近增长为
它的含义是当n → ∞时,左式除以右式的商趋向于1。(这可以用n!的斯特灵公式来证明。)
所有的奇卡塔兰数Cn都满足。所有其他的卡塔兰数都是偶数。
example:
https://leetcode.com/problems/unique-binary-search-trees/description/
最新文章
- Java项目往数据库中插入数据,出现中文乱码
- 【leetcode❤python】 203. Remove Linked List Elements
- 彻底解决_OBJC_CLASS_$_某文件名";, referenced from:问题转
- Css3 display用法
- 干货!如何正确使用Git Flow
- PHP XML Parser
- js一些通用方法的封装
- [Leetcode][Python]51: N-Queens
- CSS3秘笈:第五章
- Windows下编译Python2.7源码
- ThreadPoolExecutor 学习笔记
- 痞子衡嵌入式:飞思卡尔i.MX RT系列MCU特性介绍(4)- RT105x选型
- 《Spring Boot 入门及前后端分离项目实践》目录
- MySQL5.7使用错误解决:ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: NO)【取消或重设root密码】
- 商品和订单中使用MQ
- JUC 之 ThreadPoolExecutor 的一些研究
- me909e-821 拨号流程
- maven install 跳过test方法
- 继承AbstractRoutingDataSource再通过AOP实现动态数据源切换
- [gj]狮子经典语录
热门文章
- SpringMVC 上传文件and过滤器
- 网络请求 get 请求时, 如果参数中的字符带有+号
- Graph-684. Redundant Connection
- 使用泛型SwingWorker与EDT事件分发线程保持通讯
- ubuntu 16.04 docker下安装klee环境
- 【OpenCV3】threshold()函数详解
- JS滑动到页面底部
- Python 1行代码实现文本分类(实战笔记),含代码详细说明及运行结果
- webpack使用来打包前端代码
- Picasso加载网络图片失败,提示decodestream时返回null