卡特兰数,卡特兰数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430
令h(1)=1,h(2)=1,catalan数满足递推式[1]:
h(n)= h(1)*h(n-1)+h(2)*h(n-2) + ... + h(n-1)h(1) (n>=3)
卡特兰数的应用 实质上都是递归等式的应用
矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
分析
对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。
不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。
显然,不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
(这个公式的下标是从h(0)=1开始的)
类似问题
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
求将一个凸多边形区域分成三角形区域的方法数。
类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
用给定节点组成二叉树的问题,给定N个节点,能构成多少种不同的二叉树?(能构成h(N)个)
相关推荐
- **卡特兰数**:对于 n 个结点的不同二叉树的数量可以用卡特兰数 \(C_n = \frac{1}{n+1} {2n \choose n}\) 来表示。 #### 八、二叉树的存储结构 - **链式存储结构**:通过指针来表示二叉树中的各个结点之间的关系...
4. 对于含有5个结点的二叉搜索树,其结构的个数可以通过卡特兰数计算,即C(2n, n) / (n+1),这里n=5,则有C(10, 5) / (5+1) = 252 / 6 = 42,故选择B.42。 5. 连通图至少应有N-1条边,因此选择A.N-1。 6. 函数重载...
辣椒油树脂检验表格(食品添加剂食用香精质量验收记录表).docx
字体路径文件
Screenshot_2025-03-14-16-46-14-26.jpg
交警队伍管理制度.docx
乳酸链球菌素检验表格(食品添加剂食用香精质量验收记录表).docx
编译的axel windows工具,有需要的拿去 使用命令例子如下 cmd 界面下cd 到axel.exe 文件路径 比如下载image net 1k axel -n 8 -o ./ https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_train.tar --insecure 编译过程的记录为 https://blog.csdn.net/Magicapprentice/article/details/146250906?sharetype=blogdetail&sharerId=146250906&sharerefer=PC&sharesource=Magicapprentice&spm=1011.2480.3001.8118 可以参照这个链接从零开始自己编译
羧甲基淀粉钠检验表格(食品添加剂食用香精质量验收记录表).docx
光学多层膜系统模拟仿真matlab代码 这段代码是一个光学多层膜系统的模拟程序,计算了TE模和TM模的反射率,并绘制了反射率随波长和入射角变化的等高线图。 这里是代码的主要流程: 1. 加载材料参数数据(Al2O3、Si3N4、SiO2、Ag)和波长数据(lambda)。 2. 循环遍历不同的入射角度(theta0)。 3. 对于每个入射角度,计算TE模和TM模的传输矩阵,包括各个层的传输矩阵。 4. 计算反射率,并将TE模和TM模的反射率取平均作为总的反射率。 5. 将总的反射率随波长和入射角度的变化绘制成等高线图。 这段代码非常详细,而且注释也很清晰,让人容易理解。 不过最后一行的中文注释应该是解释如何使用`colormap`函数来设置绘图的颜色映射,可以将其翻译为“设置颜色映射为Jet色彩”。 ,多层膜系统模拟; TE模和TM模反射率计算; 波长和入射角变化; 传输矩阵; 平均反射率; 绘制等高线图; 颜色映射设置。,光学多层膜系统模拟仿真:Matlab代码实现
中国城市统计年鉴全集(1985-2022).zip。内容来源于网络分享,如有侵权请联系我删除。
双向DC DC全钒液流蓄电池充放电储能matlab simulink仿真模型,采用双闭环控制,充放电电流和电压均可控,直流母线端电压可控,电流为负则充电,电流为正则放电,可以控制电流实现充放电 (1)完整复现文献全钒液流模型,多个全钒液流电池串联成电池组,提供模型参数,电压等级可调 (2)可通过电流环控制电池充放电电流,可实现不同充放电电流,控制速度快(电流闭环) (3)可通过电压环控制电池两端充放电电压,可实现不同充放电电流,控制速度快(电压闭环) ,全钒液流电池; 双向DC-DC; 充放电控制; 电流环控制; 电压环控制; MATLAB Simulink仿真模型; 电池组; 模型参数; 电压等级可调; 电流闭环; 电压闭环,Matlab Simulink仿真模型:全钒液流电池双闭环充放电控制储能系统
windows平台mysql版本安装包 mysql-installer-community
分享课程——BEV模型部署全栈教程(3D检测+车道线+Occ)课程
基于FPGA流水线结构并行FFT的设计与实现-王英喆.caj
内核驱动开发,调试监控IRP请求包发送接收工具
comsol三元锂离子电池模型 NCA111三元锂离子电池21700 电化学-热耦合模型 老化模型 容量衰减模型 参数已经设置好 自己更改参数即可进行使用学习 可进行多倍率充放电仿真 有对应参考文献 A17 ,comsol模型;三元锂离子电池;NCA111电池;电化学-热耦合模型;老化模型;容量衰减模型;参数设置;仿真学习;参考文献,COMSOL三元锂离子电池模型与NCA111电池仿真研究
野火征途Pro FPGA开发板 实现基于帧差法的运动目标检测与跟踪 摄像头:OV5640 显示屏:TFT LCD,VGA,HDMI ,野火征途Pro; FPGA开发板; 帧差法; 运动目标检测与跟踪; OV5640摄像头; TFT LCD; VGA; HDMI,野火征途Pro FPGA开发板:运动目标检测与跟踪的视觉处理