凸多角形の三角形分割問題（４）の解答例を示します。
問題（４）の解
凸n角形を対角線で三角形に分割する方法(分割数f(n))を考察する。
凸n角形の場合、１辺を固定し他の頂点と結ぶ三角形で分類すると、凸k角形と凸(n-k+1)角形に分割できる。
この場合、凸k角形でf(k)通りの分割方法があり、それぞれの分割に対して、
凸(n-k+1)角形でf(n-k+1)通りの分割方法がある。
したがって、分割方法は、全部で、f(k)×f(n-k+1)通りとなる。
f(2)=1 と定義すると、つぎの漸化式を得る。
f(n)＝f(2)×f(n-1)＋f(3)×f(n-2)＋…＋f(n-2)×f(3)＋f(n-1)×f(2) (n≧3)
n-1
＝Σ f(i)×f(n-i+1)
i=2
f(2)＝1
計算すると、つぎの表を得る。
分割数f(n)はカタラン数と呼ばれている。
