卡特朗數

一個凸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.