前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >卡特兰数简介原理性质应用参考:

卡特兰数简介原理性质应用参考:

作者头像
致Great
发布2018-04-11 17:16:21
2K0
发布2018-04-11 17:16:21
举报
文章被收录于专栏:程序生活

简介

卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。 卡塔兰数的一般项公式为:

卡特兰公式

其前20项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190。

原理

  1. 令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
  2. 另类递推式[3]: h(n)=h(n-1)*(4*n-2)/(n+1)
  3. 递推关系的解为: h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
  4. 递推关系的另类解为: h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

性质

  1. 卡特兰数的另一个表达形式为:

表现形式 所以,卡特兰数是一个自然数;这一点在先前的通项公式中并不显而易见。

  1. 递推关系

递推1

递推2

这是一个比较快速的计算卡特兰数的方法。

  1. 卡特兰数的渐进增长

渐进增长

它的含义是当n→ ∞时,左式除以右式的商趋向于1。

  1. 所有的奇卡塔兰数Cn都满足:

奇卡塔兰数 所有其他的卡塔兰数都是偶数。

应用

  • dyck word Cn 表示长度2n的dyck word的个数。Dyck word是一个有n个X 和n 个Y 组成的字串,且所有的前缀字串皆满足X 的个数大于等于Y 的个数。以下为长度为6的dyck words: XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
  • n对括号正确匹配数目 将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数: ((())) ()(()) ()()() (())() (()())

给定n对括号,求括号正确配对的字符串数,例如: 0对括号:[空序列] 1种可能 1对括号:() 1种可能 2对括号:()() (()) 2种可能 3对括号:((())) ()(()) ()()() (())() (()()) 5种可能 那么问题来了,n对括号有多少种正确配对的可能呢? 考虑n对括号时的任意一种配对方案,最后一个右括号有唯一的与之匹配的左括号,于是有唯一的表示A(B),其中A和B也是合法的括号匹配序列 假设S(n)为n对括号的正确配对数目,那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +...+S(n-1)S(0),显然S(n)是卡特兰数。

  • 括号化 矩阵连乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(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)=h(n)= C(2n,n)/(n+1)= c(2n,n)-c(2n,n-1)(n=0,1,2,……)。 最后,令f(0)=1,f(1)=1

相似问题-买票找零

有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)

  • 凸多边形三角划分 Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况:

凸多边形三角划分 分析 :

如果纯粹从f(4)=2,f(5)=5,f(6)=14,……,f(n)=n慢慢去归纳,恐怕很难找到问题的递推式,我们必须从一般情况出发去找规律。 因为凸多边形的任意一条边必定属于某一个三角形,所以我们以某一条边为基准,以这条边的两个顶点为起点P1和终点Pn(P即Point),将该凸多边形的顶点依序标记为P1、P2、……、Pn,再在该凸多边形中找任意一个不属于这两个点的顶点Pk(2<=k<=n-1),来构成一个三角形,用这个三角形把一个凸多边形划分成两个凸多边形,其中一个凸多边形,是由P1,P2,……,Pk构成的凸k边形(顶点数即是边数),另一个凸多边形,是由Pk,Pk+1,……,Pn构成的凸n-k+1边形。 此时,我们若把Pk视为确定一点,那么根据乘法原理,f(n)的问题就等价于——凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数,即选择Pk这个顶点的f(n)=f(k)×f(n-k+1)。而k可以选2到n-1,所以再根据加法原理,将k取不同值的划分方案相加,得到的总方案数为:f(n)=f(2)f(n-2+1)+f(3)f(n-3+1)+……+f(n-1)f(2)。看到此处,再看看卡特兰数的递推式,答案不言而喻,即为f(n)=h(n-2) (n=2,3,4,……)。 最后,令f(2)=1,f(3)=1。

类似问题 :

一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?

在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

  • 给定n个节点组成不同的二叉树个数 Cn表示有n个节点组成不同构二叉树的方案数。下图中,n等于3,圆形表示节点,月牙形表示什么都没有。

二叉树个数

  • Cn表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数:X代表“向右”,Y代表“向上”。下图为n = 4的情况:

单调路径的个数

  • Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为n = 4的情况:

阶梯状图形的方法个数

参考:

卡特兰数-百度百科 卡塔兰数-维基百科 Catalan数计算及应用 杭电1023——Train Problem II 2012腾讯实习笔试中看到的Catalan数

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.08.24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简介
  • 原理
  • 性质
  • 应用
  • 参考:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档