三角剖分公式

20世纪初,数学家乌拉班发现并证明了下面的公式,(Dn表示凸n边形的三角剖分数).D(n+1)/Dn=（4n-6）/n.

1.问题之假设 所得三角形必须以原凸N 边形之顶点为顶点。

2.问题之解决

(1).

首先，将一任意凸N 边形顶点依逆时针顺序标好A1,A2...An,我们考虑边A1A2，它在任意一种分法中必与A3,...,An中某一点构成三角形，不妨设为Ai,此时{A2,A3,...,Ai}和{Ai,Ai+1,...,An,A1}构成一个凸i-1边形和凸N-i+2边形，这两个凸多边形再各自独立的分割为三角形，分别是a(i-1)和a(N-i+2)种分法，于是当A1,A2,Ai构成一个三角形时，有a(i-1)*a(N-i+2)种分法，再令i=3,4,...,N遍历其余顶点，就得到我所说的递推公式:

a(n)=a(2)*a(N-1)+a(3)*a(N-2)+...+a(N-1)*a(2)

其中a(2)=1, 纯粹是为了形式整齐所引进的。

(2).

剩下的工作就是求解数列a(n),使其满足所得通项公式,为此，我们构造无穷级数F(x)=a(2)x^2+a(3)x^3+...+a(n)x^n+...考察W(x)=F(x)*F(x)，显然，W(x)中对x^n合并同类项为a(2)x^2*a(n-2)x^(n-2)+...+a(2)x^2*a(n-2)x^(n-2)，对照递推公式，此即为a(n-1)x^(n-1),于是有

W(x)=a(3)x^4+a(4)x^5+...+a(n-1)x^n+...=x*[a(3)x^3+a(4)x^4+...+a(n)x^n+...]=x*[F(x)-x^2]

即有F(x)*F(x)-x*F(x)+x^3=0，由二次方程求根公式可得：

F(x)=(x/2)*[1-(1-4x)^(1/2)]

对上式右边作泰勒展开，就得到a(n)通项公式，为

a(n)=2^(n-2)*1*3*...*(2n-5)/(n-1)! (n>2)