吉林大学软件学院组合数学课程报告
需积分: 10 97 浏览量
2019-10-21
21:54:22
上传
评论 2
收藏 358KB PDF 举报
《组合数学》课程学习体会和扩展学习报告
组合数学领域 Catalan数的应用研究
吉林大学软件学院
1.卡特兰数简介
卡特兰数（Catalan Number）是组合数学中应用广泛的重要计数函数，以比
利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名，其前几项为（从
第零项开始）:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,
2674440,9694845,35357670,129644790,477638700,1767263190……
令 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.卡特兰数的经典组合模型
2.1 凸多边形的三角剖分问题
【问题描述】
一个凸 n+1 边形中可以最多画出 n-2 条两两不相交的对角线,这些对角线可
将多边形分割成 n-1 个三角形区域,称此为多边形的一种三角剖分。可能的三角
剖分方法数 A
n
称为 Catalan 数。
【问题分析】
显然 A
2
=1,A
3
=2,A
4
=5。对于一般的 n,作图 1 所示的 n+1 边形,以 v
1
v
n+1
作为三
角形的一条边,三角形的另一个顶点 v
k+1
(k=1,2,…,n-1),三角形 v
1
v
n+1
v
k+1
将 n+1
边形分割成一侧为 k+1 边形,另一侧为 n-k+1 边形。根据乘法原理,以 v
1
v
n+1
v
k+1
为
一剖分三角形的剖分数为 A
k
A
n-k
。由于 k=1,2,…,n-1 所得剖分各不相同,根据加
法原理,有
=
。
因为 A
2
=1,补充定义 A
1
=1,可得 Catalan 数列{A
n
}
n≥1
。另 外 ,作图 2 所示的 n 边
形 , 从 v
1
分别到 n-3 个顶点{v
3
,v
4
, … ,v
n-1
} 引出 n-3 条对角线, 以
v
1
v
k+1
(k=2,3,…,n-2)对角线为例,将 n 边形分解为一侧为 k+1 边形,另一侧为 n-
k+1 边形。因此以 v
1
v
k+1
为剖分线的 n 边形的剖分数目应为 A
k
A
n-k
(k=2,3,…,n-2)。
对 k 的取值求和得:
。v
1
点改为 v
2
,v
3
,…,v
n
也有类似的结果。
由于每一条对角线有 2 个端点,而且每个剖分总有 n-3 条对角线,对每条对角
线都计算一次得
。注意到每个 n 边形的剖分都通过 n-3 条对角线
完成,所以上述的计算,将剖分方案数重复计算了 n-3 次,故有:
评论0
最新资源