1、2.11 Catalan 数这一节讨论 Catalan数 ,其递推关系是非线性的 ,许多有意义的计数问题都导致这样的递推关系 .本节将举出一些 ,后面还将见到.一个凸 n边形 ,通过不相交于 n边形的对角线 ,把 n边形拆分成若干三角形 ,不同拆分的数目用 表之 .2.11 Catalan 数例如五边形有如下五种拆分方案，故图 2-11-12.11 Catalan 数1.递推关系定理：2.11 Catalan 数证明： 的证明：如图 所示，以 作为一个边的三角形 ，将凸 边形分割成两部分，一部分是边形， 图 2-11-22.11 Catalan 数另一部分是 边形， 即点可以是 点中任意一点。
2、依据加法法则有2.11 Catalan 数的证明：如图 所示，从 点向其它 个顶点可引出 条对角线。对角线 把 边形分割成两个部分，因此 图 2-11-32.11 Catalan 数以 对角线作为拆分线的方案数为可以是 中任一点，对所有这些点求和得以 取代 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，2.11 Catalan 数作式并不就给出剖分数，无疑其中是有重复的。其重复度是由于一个凸 边形的剖分有 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了次即 式给出的结果是 的 倍。2.11 Catalan 数式和 式都是非线性的递推关系。2.11 Catalan 数2.Catalan 数计算公式由 式及 ,故得
