YLL討論網

凸n邊形的對角線,規定對角線不可在n邊形內部相交
則可以將n邊形分割為全由三角形構成其所有情形數為f(n)
求f(n)的遞迴關係式?

(1)易知f(3)=1，f(4)=2，f(5)=5，f(6)=14
(2)f(n)的遞迴關係式推導
針對一個凸n邊形，作以下的分割(見上圖)
取某一邊為底，以此為三角形的一邊再作三角形的另兩邊(藍色部分)
則n邊形可被分割成一個k邊形，一個三角形，一個n-k+1邊形
而k邊形與n-k+1邊形的分割法各為f(k)、f(n-k+1)合計有f(k)*f(n-k+1)
若規定f(2)=1，則f(n)就是k=2,3,…,n-1時，f(k)*f(n-k+1)的加總
即n≧3時，f(n)=f(2)*f(n-1)+f(3)*f(n-2)+……+f(n-1)*f(2)
（以此來驗證f(6)=f(2)*(5)+f(3)*f(4)+f(4)*f(3)+f(5)*f(2)=14）