卡特兰数的应用,你知道几个?

2024-02-19 14:38
文章标签 应用 几个 卡特兰 知道

本文主要是介绍卡特兰数的应用,你知道几个?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

来自:https://blog.csdn.net/zhangmh93425/article/details/44677891

卡特兰递推公式

1. C_n = /frac{1}{n+1}{2n/choose n} = /frac{(2n)!}{(n+1)!/,n!} /quad n/ge 0  

2. C_n = {2n/choose n} - {2n/choose n+1} /quad n/ge 0

3. C_0 = 1 /quad , /quad C_{n+1}=/frac{2(2n+1)}{n+2}C_n

4. /begin{displaymath}C_0 = 1 /quad , /quad C_{n+1}=/sum_{i=0}^{n}C_i/,C_{n-i}/quad n/ge 0/end{displaymath}

5. /begin{displaymath}C_n= /frac 1{n+1} /sum_{i=0}^n {n /choose i}^2/end{displaymath}

 

卡特兰数的应用

1. 由n个+1和n个-1构成2n项a_1,a_2,...,a_n其部分和满足a_1 + a_2 + ... + a_k /ge 0 /quad , /quad 0 /le k /le 2n的序列个数等于第n个Catalan数C_n

假设不满足条件的序列个数为U_n,那么就有C_n + U_n = {2n /choose n}。而对于不满足的序列,必然存在某一个奇数位使a_1 + a_2 + ... + a_k < 0,而且+1的个数恰好比-1的个数少一个,此时我们将前k项中的+1变为-1,将-1变为+1,那么就得到一个有(n+1)个+1和(n-1)个-1的序列,即一个不满足条件的序列对应于一个由n+1个+1和n-1个-1组成的排列。所以 U_n = {2n/choose n + 1}。那么C_n = {2n/choose n} - U_n = {2n/choose n} - {2n/choose n + 1}}}

 

2. 我们可以将应用1变换形式:将-1看成右括号,+1看成左括号,就变成了左括号和右括号各有n个时,合法括号表达式的个数。比如2个左括号和2个右括号组成的合法表达式有C_2 = 2种,是()()和(())。

 

3. 再次转换形式,对于n+1个数连乘,乘法顺序有C_n种,比如三个数连乘a*b*c,n=2,相当于在式子上加括号,有2种乘法顺序,分别是(ab)c和a(bc)。四个数连乘a*b*c*d,n=3,有5种乘法顺序,分别是a(b(cd)),(ab)(cd),((ab)c)d,(a(bc))d和a((bc)d)。同时对于n为3得到合法的括号序列有5个,分别是:((())),()(()),()()(),(())()和(()()),也即与n+1个数连乘的顺序数一一对应关系。

 

4. n个节点构造二叉树的所有可能形态数为C_n。考虑随便取一个节点作为根,那么他左边和右边的儿子节点个数就确定了,假定根节点标号为x,那么左子树的标号就是从1到x-1,共x-1个,右子树的标号就是从x+1到n,共n-x个,那么将x从1取到n,就获得了所有的情况数/begin{displaymath}C_n = /sum_{i = 0}^{n - 1}C_i/,C_{n - i - 1}/end{displaymath}

 

5. n个非叶节点的满二叉树的形态数(对称后得到的二叉树除非自己本身对称,否则算是不同)

对于满二叉树,实际上就是将应用4中的每个子节点的空儿子上都加上叶子,就形成了对应的满二叉树,那么n个非叶节点形成的满二叉树的形态数即为Cn

 

6. 对于一个n*n的正方形网格,每次只能向右或者向上移动一格,那么从左下角到右上角所有在副对角线右下方的路径总数为C_n

可以将一条水平边记为+1,垂直边记为-1,那么就组成了一个n个+1和n个-1的序列,并且保证前k步中水平边数不小于垂直边数,换句话说前k个元素的和非负。

 

7. 对凸n+2边形进行不同的三角形分割(只连接顶点对形成n个三角形)数为Cn

8. n个数入栈后的出栈的排列总数是C_n。例如1,2,3入栈的出栈排序有123,132,213,231和321五种

 

9. 对于集合/{1,2,...,2n/},将集合元素两两分为n个子集,若任意两个子集都不交叉,那么我们称此划分为一个不交叉划分。此时不交叉的划分数就是C_n。考虑将每个子集中较小的数用左括号代替,较大的用右括号代替,那么带入原来的1至2n的序列中就形成了合法括号问题。例如集合{1,2,3,4,5,6}的不交叉划分有五个:{{1,2},{3,4},{5,6}},{{1,2},{3,6},{4,5}},{{1,4},{2,3},{5,6}},{{1,6},{2,3},{4,5}}和{{1,6},{2,5},{3,4}}。

 

10. n层的阶梯切割为n个矩形的切法数也是C_n。如下图所示:

 考虑先绘制如下图片,即n为5的时候的阶梯:

注意到每个切割出来的矩形都必需包括一块标示为*的小正方形,那么此时枚举每个*与#标示的两角作为矩形,剩下的两个小阶梯就是我们的两个更小的子问题了,于是我们的C_5 = C_0 * C_4 + C_1 * C_3 + C_2 * C_2 + C_1 * C_3 + C_0 * C_4

 

11. 在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是C_n

 

12. 平面上连接可以形成凸包的2n个点分成2个一组连成n条线段,两两线段之间不相交的情况总数是C_n,这里实际上和应用7本质上是一样的。

 

13. n+m个人排队买票,并且满足n /ge m,票价为50元,其中n个人各手持一张50元钞票,m个人各手持一张100元钞票,初始时候售票窗口没有钱,问有多少种排队的情况数能够让大家都买到票。

如果m=n的话那么这就是初始的Catalan数问题,也就是将手持50元的人看成是+1,手持100元的人看成是-1,任前k个数值的和都非负的序列数。

对于n>m的情况,假设大家都可以买到票的情况数是D_{n+m},无法让每个人都买到的情况数是U_{n + m},那么就有D_{n + m} + U_{n +m} = {n + m /choose n},假设最早买不到票的人编号是k,他手持的是100元并且售票处没有钱,那么将前k个人的钱从50元变成100元,从100元变成50元,这时候就有n+1个人手持50元,m-1个手持100元的,所以就得到U_{n + m} = {n + m /choose n + 1},同时D_{n + m} = {n + m /choose n} - {n + m /choose n + 1}

这篇关于卡特兰数的应用,你知道几个?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724985

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

hdu4828(卡特兰数+逆元)

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列 下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n,其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32.................................. 但是这题的n太大了,所以要用到逆元,

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/