卡特兰数 -Catalan

卡特兰数又称卡塔兰数,英文名 Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁 · 查理 · 卡塔兰 (1814–1894) 的名字来命名。

计算

出栈次序

按序进栈,随意出栈,则出栈序列有多少种?(LuoguP1044)

计数类的问题一般要抽象出一定的数学模型

定义 表示 按序进栈,随意出栈,出栈序列的种数

那么我们考虑最后一个出栈的元素

  • 进栈以前, 显然要全部出栈,方案数为 .
  • 出栈以前, 显然要全部出栈,方案数为 .

则根据乘法原理,以 结尾的出栈序列的方案数为 .

可以取 ,于是总方案数为

显然就是卡特兰数的模型,则公式计算即可

凸多边形三角划分

因为凸多边形的任意一条边必定属于某一个三角形,所以我们以某一条边为基准,以这条边的两个顶点为起点 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(2)=1,f(3)=1。

组成二叉搜索树

给定 n 个结点,能构成多少种不同的二叉搜索树?

f(k) 表示 1-k 个结点构成的二叉搜索树的个数
则可令 1-k 中的任意结点 m 作为根结点,于是有:

f(k)=sum{f(m-1)*f(k-m-1):1<=m<=k}

即为卡特兰数

n 对括号正确匹配数目

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

  • 0 对括号:[空序列] 1 种可能
  • 1 对括号:() 1 种可能
  • 2 对括号:()(),(()) 2 种可能
  • 3 对括号:((())),()(()),()()(),(())(),(()()) 5 种可能

那么 n 对括号有多少种正确配对的可能?


  转载请注明: Sshwy's Blog 卡特兰数 -Catalan

 上一篇
组合数漫谈 组合数漫谈
排列与组合在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。 排列数从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有
2018.12.21
下一篇 
[LuoguP2756] 飞行员配对方案问题 [LuoguP2756] 飞行员配对方案问题
分析二分图匹配,直接网络流模板 输出方案的时候,判断每条边是否图上剩余容量为 0 的边即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
  目录