卡特朗数

一个凸n边形通过不相交于n边形内部的对角线把n边形拆分成若干个三角形,不同的拆分数用卡特朗数Cn表示.

Cn同时代表着n-1个数相乘的完成顺序,比如C5=5,则4的数相乘的完成顺序有5种,为:

abcd,a(bc)d,ab(cd),a(b(cd)),a(bcd)

卡特朗数有如下递推关系:

Cn+1=C2Cn+C3Cn-1+C4Cn-2+...+CnC2

(n-3)Cn=n/2(C3Cn-1+C4Cn-2+...+Cn-1C3)

卡特朗数为:Cn=(2n-4,n-2)/n.