精选文章 【阶段1】卡特兰数的学习(Catalan)

【阶段1】卡特兰数的学习(Catalan)

作者:小龚主 时间: 2020-08-04 10:01:28
小龚主 2020-08-04 10:01:28

申明:本文版权应该是中山一中的万杰老师(此处悄悄引用他四年前的课件)

一、基础知识储备:

排列:p(n,m)=n!/(n-m)!

原因:排列公式是建立一个模型,从n个不相同元素中取出m个排成一列(有序),第一个位置可以有n个选择,第二个位置可以有n-1个选择(已经有1个放在前一个位置),则同理可知第三个位置可以有n-2个选择,以此类推第m个位置可以有n-m+1个选择,则排列数为 n*(n-1)……(n-m+1)。

公式推导:p(n,m)=n*(n-1)……(n-m+1)=n!/(n-m)! (把1至m-1的各数的阶乘的积去除)

举例:p(5,3)=5!/2!=5*4*3

 

组合: c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)

原因:组合公式对应另一个模型,从n个不同的元素中取出m个成为一组(无序),由于m个元素组成的一组可以有m!种不同的排列(全排列)p(m,m)),组合的总数就是 c(n,m)=A(n,m)/m!=n!/((n-m)!*m!)(,m个元素组成的一组可以有m!种不同的排列,但都属于同一组,所以所有的排列方案除以m!就表示能够分成多少组)

 

二、卡特兰数:

卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名,其前几项为: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,

有何规律?

令h(0)=1,h(1)=1,catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)

例如:

h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

 

卡特兰数的模型Af(n)=f(k-1)×f(n-k)。而k可以选1到n

一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

首先,我们设f(n)=序列个数为n的出栈序列种数。(我们假定,最后出栈的元素为k,显然,k取不同值时的情况是相互独立的,也就是求出每种k最后出栈的情况数后可用加法原则,由于k最后出栈,因此,在k入栈之前,比k小的值均出栈,此处情况有f(k-1)种,而之后比k大的值入栈,且都在k之前出栈,因此有f(n-k)种方式,由于比k小和比k大的值入栈出栈情况是相互独立的,此处可用乘法原则,f(n-k)*f(k-1)种,求和便是Catalan递归式。

首次出空之前第一个出栈的序数k将1~n的序列分成两个序列,其中一个是1~k-1,序列个数为k-1,另外一个是k+1~n,序列个数是n-k。

此时,我们若把k视为确定一个序数,那么根据乘法原理,f(n)的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数,即选择k这个序数的f(n)=f(k-1)×f(n-k)。而k可以选1到n,所以再根据加法原理,将k取不同值的序列种数相加,得到的总序列种数为:f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。

看到此处,再看看卡特兰数的递推式,f(n) 就是n的卡特兰数。最后,令f(0)=1,f(1)=1。

 

卡特兰数的模型Bc(2n,n)-c(2n,n+1)或c(2n,n)-c(2n,n-1)

对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态’1’,出栈设为状态’0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。

证明1(数字理解)

1

1

0

0

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,结果得一个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

1

1

0

0

0

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-1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)或c(2n,n)-c(2n,n-1)

证明2(图像理解)

大佬写得更详细,我就直接放链接了。

点击此处阅读大佬文章,写得超棒!!!

 

举例1n对括号正确匹配数目

给定n对括号,求括号正确配对的字符串数,例如:

1对括号:() 1种可能

2对括号:()() (()) 2种可能

3对括号:((())) ()(()) ()()() (())() (()()) 5种可能

那么问题来了,n对括号有多少种正确配对的可能呢?

思路:卡特兰数模型B解决问题。

 

三、卡特兰数的模型B的化简:c(2n,n)-c(2n,n+1)或c(2n,n)-c(2n,n-1)

 

【阶段1】卡特兰数的学习(Catalan)1

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:论文|从DSSM语义匹配到Google的双塔深度模型召回和广告场景中的双塔模型思考...

下一篇:网络层次结构基础知识

您可能感兴趣

  • 新职业教育的三节课,凭什么做到今天这样

    历时7天、翻遍15个平台渠道、访谈25位参与课程的从业者、挖掘了136条推文的标题和内容,我们得到了12500字的拆解。可以点击右上角☝:收藏、分享、在看,不用担心看一半,找不到文章。 本文信息公开来源:三节课官方公众号、虎嗅网、36氪、深网、东方财富网、新榜、知乎、简书、增长黑盒、短书··· 我们认为,这可能比任何官方复盘更能诠释:「三节课」是如何在3年内,做到互联网职业教育(Almost...

  • OpenGL学习笔记8-Coordinate Systems

    Coordinate Systems(坐标系) Getting-started/Coordinate-Systems(开始/坐标系统) 在上一章中,我们学习了如何利用矩阵来转换所有的顶点。OpenGL期望在每个顶点着色器运行后,我们想要变得可见的所有顶点都在规范化的设备坐标中。也就是说,每个顶点的x、y、z坐标应该在-1.0到1.0之间;超出此范围的坐标将不可见。我们通常做的是,指定我们自己...

  • 为什么苏联打下了如此强的数学基础,俄罗斯却至今无法成为AI强国?

    作者:俄罗斯小笨笨 链接:https://www.zhihu.com/question/395842406/answer/1243718056 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 数学实力有多强我不清楚,我也对数学的了解也不专业。但是让俄罗斯无法成为AI强国的最大问题之一,肯定包含了人才外流这一原因。 或者往大了说,是俄罗斯各个行业一直面临的一个...

  • 2020,我不想奋斗了

    导读:奋斗狗和咸鱼,你会怎么选? 作者:黎明 唐亚华 周继凤 孟亚娜 金玙璠 赵磊 苏琦 编辑:黎明 来源:燃财经(ID:rancaijing) 对于很多人而言,2020年是极其特殊甚至荒诞的一年。 年初爆发的新冠肺炎疫情,影响了经济形势,改变了很多人的生活。2020年已经过半,最近,有这样一种声音:有人说不想奋斗了,有人说鸡汤喝够了,有人说要及时行乐,还有人一边喊着不想奋斗,一边用实际行动...

  • 后端,还是大数据?

    最近到了招聘旺季,发现一些朋友很纠结一个问题:做后端开发和做大数据开发?这个问题还是比较普遍的。 其实,后端开发,更专注于一种技术栈的开发,对于成熟的开发框架而言,的确市面上的竞争压力会比较大,竞聘者除了技术功底够硬,更多的是要对业务充分的熟悉。而大数据开发,由于兴起时间较晚,再加上国家政策的扶持,人才需求远远没有饱和,相比较起来,竞争的确要小一些,薪资和前景更有吸引力。 但这并不意味着面试...

  • 《PTMs for NLP: A Survey》笔记

    Pre-trained Models for Natural Language Processing: A Survey Xipeng Qiu*, Tianxiang Sun, Yige Xu, Yunfan Shao, Ning Dai & Xuanjing Huang 最后,我们概述了PTMs未来研究的一些可能的方向。本调查旨在为理解、使用和开发用于各种NLP任务的PTMs提供动手指导。...

  • 大数据内推就一定能进?

    最近到了招聘旺季,发现一些朋友很纠结一个问题:做后端开发和做大数据开发?这个问题还是比较普遍的。 其实,后端开发,更专注于一种技术栈的开发,对于成熟的开发框架而言,的确市面上的竞争压力会比较大,竞聘者除了技术功底够硬,更多的是要对业务充分的熟悉。而大数据开发,由于兴起时间较晚,再加上国家政策的扶持,人才需求远远没有饱和,相比较起来,竞争的确要小一些,薪资和前景更有吸引力。 但这并不意味着面试...

  • 量化策略更新换代 五大私募机构演绎“快”字诀

    2010年以来,伴随着IT技术和金融衍生品市场的发展,量化投资作为一大投资类别在国内生根发芽并快速成长。量化私募界是量化投资的主战场,这是一个由海归顶尖基金经理和80后学霸主导的江湖。 证券时报记者 沈宁 许孝如 据证券时报记者了解,国内量化私募的最新管理规模已超2000亿元,以明汯、幻方、灵均、金锝和九坤等为代表的头部格局正在逐步形成,海归和本土基金经理各领风骚。经过10年发展,量化策略从...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。