凸n角形の対角線によって分けられる領域の数

n≧4とする。凸n角形の内部をn個の頂点から任意の2点を選んで出来る線分すべてを描くことで仕切る。どの3本の線分もn個の頂点以外では1点で交わらないとき、仕切られた領域の個数A_nを求めよ。（例：A_4=4，A_5=11）（nyoki1007様）

n 角形で m 個となりの点との対角線は別の (m-1)(n-m-1) 個の対角線と交わる。
よってこれをひくと (m-1)(n-m-1)+1 個の領域が増える。

n-1 角形のどこかの辺に三角形をくっつけてから対角線を n-3 本引くことを考えると、
n≧4 に対し、A_n = A_(n-1) + 1 + Σ[m=2..n-2] (m-1)(n-m-1)+1
（A_3 は線分を 1 本もひかないので A_3 = 1 と考える）

1 + Σ[m=2..n-2] (m-1)(n-m-1)+1
　= n-2 + Σ[m=1..n-1] (m-1)(n-m-1)
　= n-2 + Σ[m=1..n-1] - m^2 + nm - (n-1)
　= n-2 - 1/6 n(n-1)(2n-1) + 1/2 n^2(n-1) - (n-1)^2
　= 1/6 n^3 - n^2 + 17/6 n - 3

これは n=1, 2, 3 を形式的に代入するとそれぞれ -1, 0, 1 である

したがって、n≧4 のとき、
A_n = 1 + Σ[m=4..n] 1/6 m^3 - m^2 + 17/6 m - 3
　　　= 1 + Σ[m=1..n] 1/6 m^3 - m^2 + 17/6 m - 3
　　　= 1 + 1/24 n^2(n+1)^2 - 1/6 n(n+1)(2n+1) + 17/12 n(n+1) - 3n
　　　= (n^4 - 6n^3 + 23^2 -42n +24)/24
　　　= (n-1)(n-2)(n^2-3n+12)/24