【名题赏析】3.4 三角形剖分、画廊问题和卡特兰数（4）

解名题，学数学！...



【名题赏析】3.3  三角形剖分（3）

【名题赏析】3.2  三角形剖分（2）

【名题赏析】3.1  三角形剖分（1）

前三节已经比较完整地解决了画廊问题，今天我们要继续利用多边形的三角形剖分，推导出一个十分有用的数列 —— 卡特兰数列，而推导过程中所使用的递归方法，更是极其强大的武器！

多边形的三角形剖分计数

对一个凸七边形进行三角形剖分，不同的方法一共有几种？

记 凸 n 边形共有

t_n （表示：t 下标 n）种方法。先试算几种简单的情形：例如，三角形只有一种，四边形沿对角线有两种不同的剖分，五边形的剖分仔细通过作图不难得到：也就是说：现在转向六边形：这次并非一口气剖分完毕，而是选择一条边，观察它所在的三角形的位置，可以分以下四类：



这样，第一张图片得到一个五边形，继续对五边形进行剖分，故有t_5 种剖分方法；第二张图片得到左侧一个三角形和右侧一个四边形，继续对它们进行剖分，并由乘法原理，共有t_3 * t_4 种分割方法。继续这个分析，可以得到六边形的剖分方法共有：进入七边形，仿照上面的思路，先选多边形的一边，用它所在的三角形对剖分进行分类：



以上共有五种情形。左侧第一张图，剩下一个六边形，将产生t_6 种剖分方法；第二张图片得到左侧一个三角形和右侧一个五边形，继续对它们进行剖分，并由乘法原理，共有t_3 * t_5 种剖分方法。

第三张图片得到左、右侧各一个四边形，继续对它们进行剖分，并由乘法原理，共有t_4 * t_4 种剖分方法。

继续分析下去，并且这次我们把 “ 退化 ” 的情形也包含进来，也即把第一张和最后一张图的都看成：七边形被剖分为二边形、三角形和六边形，而其中二边形是三角形的退化情形。（真是异想天开啊！）现在定义t_2 =1，从而得到一个更加漂亮的等量关系（为了美观，数学家真是不择手段啊！）：计算可得七边形的剖分方法共有：42 种。事实上，想求出任意边长的凸多边形三角形剖分方法数，都可以利用相同的思想计算下去。现在把前几个答案都列出来：



也就是： 1,1,2,5,14,42,132,429,1430,......  这个首先被欧拉研究而最后被称为卡特兰数列（有不少故事）的一串数字，经常在计数问题中出现。

当然，我们现在只有卡特兰数列各项之间的关系，而要得到卡特兰数列关于 n 的直接表达式，需要一些高中知识，此处只能按下不表。回顾刚才的解题过程，在处理六边形和七边形的剖分计数时，我们并没有直接进行枚举，而是先对剖分进行一个大致分类，而后利用乘法原理对每类进行计数。最后得到的公式虽然看起来复杂，但它确实是基本计数原理的直接应用。

更重要的是，反过来想，为了求七边形的剖分计数，我们先要求六边形的剖分；而求六边形的剖分时，又要先求出五边形的剖分。也即，要解决一个大规模的问题，先要处理一个同样性质的小规模的问题，而要处理这个问题，又要用完全同样的方法去处理一个更小规模的问题，这样一直不停的进行下去，直到最小的问题被解决，不断返回到前一个规模的问题，最后解决整个问题。

说到这里，已经有点抽象了，数学中将这种解决问题的方法称为 “ 递归 ”。递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。卡特兰数就是递归思想的一个经典范例。

作者：李继刚     来源：知乎。

你打开面前这扇门，看到屋里面还有一扇门（这门可能跟前面打开的门一样大小（静），也可能门小了些（动）），你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开，。。。， 若干次之后，你打开面前一扇门，发现只有一间屋子，没有门了。 你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这钥匙开了几扇门。

雾岩注：这个对递归的解释就用了递归！太帅了！

    关注 初中理科班数学