📄 2_11.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.11 Catalan 数 </h1><p> 这一节讨论Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.本节将举出一些,后面还将见到. </p><p> 一个凸n边形,通过不相交于n边形的对角线,把n边形拆分成若干三角形,不同拆分的数目用h<sub>n</sub>表示.例如五边形有如下五种拆分方案，故h<sub>n</sub>=5</p><p> <img border="0" src="2_11.pic/image005.gif" width="361" height="128"></p><p> 图 2-11-1 </p><p> 1.递推关系 </p><p> 定理： </p><p> <img border="0" src="2_11.pic/image007.gif" width="304" height="91"></p><p> </p><p> 证明：</p><p> （a）的证明： 如图2－11－1所示， 以v<sub>1</sub>v<sub>n+1</sub>作为一个边 的三角形 ， 将凸n+1边形分割 成两部分，一部分是 k边形， 另一部分是n-k+2边形，k=2,3,<sup>...</sup>,n即v<sub>k</sub>点可以是v<sub>2</sub>,v<sub>3</sub>,<sup>...</sup>,v<sub>n</sub>点中任意一点。依据加法法则有 </p><p> </p><p> <img border="0" src="2_11.pic/image030.gif" width="235" height="69"></p><p> <img border="0" src="2_11.pic/image016.gif" width="288" height="304"></p><p> 图 2－11－3 </p><p> (b) 的证明： 如图2－11－3所示， 从v<sub>1</sub>点向其它n-3个顶点(v<sub>3</sub>,v<sub>4</sub>,<sup>...</sup>,v<sub>n-1</sub>)可引出n-3条对角线。对角线v<sub>1</sub>v<sub>k</sub>把n边形 分割成两个部分，因此 以v<sub>1</sub>v<sub>k</sub>对角线作为拆分线的方案数为h<sub>k</sub>h<sub>n-k+2</sub><sub>。</sub></p><p> <sub> <img border="0" src="2_11.pic/image032.gif" width="272" height="238"></sub></p><p> <sub> </sub>v<sub>k</sub>可以是v<sub>3</sub>,v<sub>4</sub>,<sup>...</sup>,v<sub>n-1</sub>中任一点，对所有这些点求和得h<sub>3</sub>h<sub>n-1</sub>+h<sub>4</sub>h<sub>n-2</sub>+<sup>...</sup>+h<sub>n-2</sub>h<sub>4</sub>+h<sub>n-1</sub>h<sub>3</sub></p><p> <sub> </sub>以v<sub>2</sub>,v<sub>3</sub>,<sup>...</sup>,v<sub>n</sub>取代 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，作 </p><p> <img border="0" src="2_11.pic/image051.gif" width="319" height="41"></p><p>（2－11－3）式并不就给出剖分数，无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次即（2－11－3）式给出的结果是h<sub>n</sub>的n-3倍。 </p><p> <img border="0" src="2_11.pic/image054.gif" width="229" height="67"></p><p>（2－11－1）式和（2－11－2）式都是非线性的递推关系。 </p><p> 2.Catalan 数计算公式 </p><p> 由（2－11－1）式及h<sub>2</sub>=1故得 </p><p> <img border="0" src="2_11.pic/image058.gif" width="300" height="109"></p><p>由 </p><p> <img border="0" src="2_11.pic/image060.gif" width="163" height="41"></p><p>整理得 </p><p> <img border="0" src="2_11.pic/image062.gif" width="161" height="24"></p><p> <img border="0" src="2_11.pic/image064.gif" width="139" height="24"></p><p>令 </p><p> <img border="0" src="2_11.pic/image066.gif" width="80" height="24"></p><p> <img border="0" src="2_11.pic/image068.gif" width="225" height="88"></p><p>即 </p><p> <img border="0" src="2_11.pic/image070.gif" width="225" height="45"></p><p> <img border="0" src="2_11.pic/image072.gif" width="247" height="135"></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -