卡特兰数(Catalan)的原理和题目

2024-05-11 19:18

本文主要是介绍卡特兰数(Catalan)的原理和题目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Catalan数的定义令h(1)=1,Catalan数满足递归式:h(n) = h(1)*h(n-1) +h(2)*h(n-2) + ... + h(n-1)h(1),n>=2该递推关系的解为:

证明:

令1表示进栈,0表示出栈,则可转化为求一个2n位、含n个1、n个0的二进制数,满足从左往右扫描到任意一位时,经过的0数不多于1数(也就是1的个数>=0的个数)。显然含n个1、n个0的2n位二进制数共有个,可以理解为 (2n)!/(n!*n!)

下面考虑不满足要求的数目。用上面的所有组合数减去不满足的要求的数量

考虑一个含n个1、n个0的2n位二进制数,扫描到第2m+1位上时有m+1个0和m个1(容易证明一定存在这样的情况),然后互0和1的值,则后面的0排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0,则对应一个n+1个0和n-1个1的二进制数。反之亦然(相似的思路证明两者一一对应)。

从而

证毕。

个人理解

解答: 设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为 C(n 2n)

不填1的其余n位自动填以数0。从C(n 2n)中减去不符合要求的方案数即为所求。

不合要求的数指的是从左而右扫描,出现0的累计数超过1的累计数的数。

不合要求的数的特征是从左而右扫描时,必然在某一奇数2m+1位上首先出现m+1个0的累计数,和m个1的累计数。

此 后有n-m个1,n-m-1个0。如若把后面这部分0与1交换,使之成为n-m个0,n-m-1个1,结果得 1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n-1个1和n+1个0组成的一个排列。

反过来,任何一个 由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位数,必对应于一个不合要求的数。

用上述方法建立了由n+1个0和n-1个1组成的2n位数,与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。

  • 1 带限制条件的路径总数
  • 2 括号序列计数
  • 3 出栈顺序
  • 4 排队问题
  • 5 二叉树计数
  • 6 机器人回到原点

这篇关于卡特兰数(Catalan)的原理和题目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

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太大了,所以要用到逆元,

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

寻迹模块TCRT5000的应用原理和功能实现(基于STM32)

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理,包括该模块的硬件实现方式,电路实现原理,还使用STM32类

TL-Tomcat中长连接的底层源码原理实现

长连接:浏览器告诉tomcat不要将请求关掉。  如果不是长连接,tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(