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

解名题，学数学！...

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

本节要证明对任意多边形都能进行三角形剖分。证明时利用了极端原理，并抛弃了过于严谨的叙述（强归纳法），这样初中生理解起来更容易一些。

可剖分的证明

首先，找到多边形 “最下方” 的一点，如果同时有几个在 “最下方” 的点，则挑出最右侧的点，记这个点为 P，与点 P 相邻的两个多边形顶点为 Q 和 R。联结 QR，并考虑 △PQR，有以下两种可能：

（1）线段 QR 在多边形的内部，则线段 QR 就是多边形的对角线，它把多边形分割成 △PQR 和另外一个多边形，但它比原来的多边形少一条边；

（2）线段 QR 不在多边形的内部，即 △PQR 内部或边 QR上有多边形的顶点，再从这些顶点中找到一个最“下方”的点 S —— 这总能做到，联结 PS，则线段 PS 是多边形的对角线，它也将多边形分割成两个边数更少的多边形.

由以上讨论可知，任何多边形都是可剖分的，总可以通过找到对角线（在多边形内部），并沿对角线将多边形剖分成两个边数较小的多边形。

如此不断进行下去，一直到将所有新得到多边形都剖分成三角形为止。这是因为：得到的新多边形边数总是不断减小，而边数又是有限的，所以总会剖分到三角形。这就证明了，任意多边形都是可以进行三角形剖分的。

三角形的数量

既然多边形都能被三角形剖分，那么 n 边的多边形能切割成几个三角形呢？对凸 n 边形，容易知道三角形的数量是（n-2）个。对于一般的多边形，是否也是如此呢？

我们可以通过算两次 来求剖分所得三角形个数。假定多边形一共进行过 x 次剖分，由于每剖分一次都增加一个多边形，故最后的三角形数为（x+1）个，一共有 3（x+1）条边。

另一方面，每次剖分，会增加 2 条边，原有 n 条边，剖分完毕后共有（n+2x）条边，故有等式：