凸n边形的对角线最多能将其内部分成几个区域。

----区域数Tn的递推式与通式

金鸣

      凸n边形的对角线最多（即不存在3条对角线交于一点）能将其内部分成几个区域？这一问题虽然有过多种简例与讨论[1]，但无明确的结论。本文将给出完整的递推式，进而获得其通式。

记凸n边形的对角线最多能将其内部分成的区域数为Tn。

显然，可从图形直观可得：T3=1；T4=4；T5=11。

下面先给出从五边形到六边形的递推算法示例，然后再导出对任意n的递推式，进而获得其通用的表达式。

【示例】从T5出发计算T6

记T6=T5+d，下面将一步一步地添加对角线来计算区域数的增加值d。

1,如图1所示有五边形A1A2A3A4A5及其对角线（黑色），在边A5A1外任取一点A6，连接A6A5及A6A1（红色）得六边形。此时区域数增加1，d=1。

2,连结A6A2（棕色）。A6A2与原有的五边形从A1出发的边及对角线有6-3=3个交点。此时区域数增加(6-3)*1+1，d=1+((6-3)*1+1)。

3,连结A6A3（蓝色）。A6A3与原有的五边形从A1出发的边及对角线有6-4=2个交点，与原有的五边形从A2出发的对角线有6-4=2个交点。此时区域数增加(6-4)*2+1，d=1+((6-3)*1+1)+( (6-4)*2+1)。

4,连结A6A4（绿色）。A6A4与原有的五边形从A1出发的边有6-5=1个交点，与原有的五边形从A2出发的对角线有6-5=1个交点，与原有的五边形从A3出发的对角线有6-5=1个交点。此时区域数增加(6-5)*3+1，d=1+((6-3)*1+1)+((6-4)*2+1)+((6-5)*3+1)。

综上，T6=T5+1+((6-3)*1+1)+((6-4)*2+1)+ ((6-5)*3+1)

  =T5+1+{(6-3)*1+(6-4)*2+(6-5)*3}+(6-3)

=11+1+10+3=25。

一般地，有如下结论：

     【定理】凸n边形的对角线最多（即不存在3条对角线交于一点）能将其内部分成的区域数Tn有下列递推式

      Tn=Tn-1 + (n^3-6n^2+17n-18)/6………………………………..(1)

与通式：

      Tn=(n-1)(n-2)(n^2-3n+12)/24………………………………………(2)

    【证明】

记Tn=Tn-1 + d，下面将一步一步地添加对角线来计算区域数的增加值d。

1,在n-1边形A1A2…An-1及其全部对角线的图形（图略）中，在边An-1A1外任取一点An，连接AnAn-1及An A1得n边形。此时区域数增加1，d=1。

2,连结AnA2。AnA2与原有的n-1边形从A1出发的边及对角线有n-3个交点。此时区域数增加(n-3)*1+1，d=1+((n-3)*1+1)。

3,连结AnA3。AnA3与原有的n-1边形从A1出发的边及对角线有n-4个交点，与原有的n-1边形从A2出发的对角线有n-4个交点。此时区域数增加(n-4)*2+1，d=1+((n-3)*1+1)+( (n-4)*2+1)。

4,如此反复连结AnA4, AnA5, …并增加其区域数，最后连结AnAn-2。AnAn-2与原有的n-1边形从A1,A2,…,An-3出发的对角线（或边）各有n-(n-1)=1个交点。此时区域数增加1*(n-3)+1，d=1+((n-3)*1+1)+( (n-4)*2+1)+… + (1*(n-3)+1)。

综上，

Tn=Tn-1+ 1+((n-3)*1+1)+((n-4)*2+1)+…+ (1*(n-3)+1)

=Tn-1+ {(n-3)*1+(n-4)*2+…+1*(n-3)}+(n-2)

为了化简通式，定义“拟似Catalan数”：

C(n)=n*1+(n-1)*2+…+1*n

=∑(i=1,…,n)(n+1-i)*i

=(n+1)∑(i=1,…,n)i -∑(i=1,…,n) i^2

=(n+1)n(n+1)/2– n(n+1)(2n+1)/6

=n(n+1)(n+2)/6。

    于是有

Tn=Tn-1+ C(n-3)+(n-2)

  =Tn-1 + (n-3)(n-2)(n-1)/6+(n-2)

  =Tn-1 + (n-2)(n^2-4n+9)/6

  = Tn-1 + (n^3-6n^2+17n-18)/6。

Tn的递推式证毕。

利用初值T3=1及Tn的递推式可导出Tn的通式。

Tn=1+∑(i=4,…,n)(i^3-6i^3+17i-18)/6 

       =1+∑(i=1,…,n)(i^3-6i^3+17i-18)/6- ∑(i=1.2.3) (i^3-6i^3+17i-18)/6

利用平方数列和∑i^2=n(n+1)(2n+1)/6及立方数列和∑i^3=n^2*(n+1)^2/4等公式化简Tn的通式，并因式分解得

Tn=(n^4-6n^3+23n^2-42n+24)/24

=(n-1)(n-2)(n^2-3n+12)/24。      证毕

于是可得【Tn的简表】

T3=1, T4=4, T5=11, T6=25, T7=50,T8=91,

T9=154, T10=246, T11=375,T12=550。

【参考文献】

[1]  llxph2008 直线划分平面的问题与凸多边形的边线及其对角线划分其内部区域问题的讨论 百度文库2014.11