這是Catalan數(shù)
歐拉多邊形分割問(wèn)題：
設(shè)有一個(gè)正凸n邊形,可以用n-3條不相交的對(duì)角線將n邊形分成n-2個(gè)互相沒(méi)有重疊的三角形, 例如n=5,共有下圖所示5種方法.
對(duì)任意給定的一個(gè)N邊形,任意選定一條邊,則該邊必是某一組成分割的三角形的一邊,它的兩個(gè)端點(diǎn)也是該三角形的兩個(gè)端點(diǎn),另一個(gè)端點(diǎn)可以來(lái)自于另外N-2個(gè)頂點(diǎn),這個(gè)三角形將N邊形分成二個(gè)多邊形,下圖是對(duì)一個(gè)六邊形選定底邊時(shí)的分割情況情況.
根據(jù)加法原理和乘法原理有：Hn=Hn-1+H3Hn-2+···+Hn-2H3+Hn-1 （1）
另外任取一條對(duì)角線Pij,將N邊形一分為二,二部分分別為多邊形,它們的邊數(shù)之和為n+2,從一個(gè)頂點(diǎn)出發(fā)的n-3條對(duì)角線形成的n邊形分割數(shù)為：H3Hn-1+H4Hn-2+…+Hn-2H4+Hn-1H3,從n個(gè)頂點(diǎn)出發(fā)的所有對(duì)角線形成的n邊形分割數(shù)為n(H3Hn-1+H4Hn-2+…+Hn-2H4+Hn-1H3),由于一條對(duì)角線有兩個(gè)端點(diǎn),所以在上面的統(tǒng)計(jì)中,每條對(duì)角線出現(xiàn)了兩遍,從所有的對(duì)角線出發(fā)形成的n邊形分割數(shù)為：n(H3Hn-1+H4Hn-2+…+Hn-2H4+Hn-1H3)/2,任何一個(gè)分割是由n-3條對(duì)角線組成的,每個(gè)分割在上式中被重復(fù)統(tǒng)計(jì)了n-3遍,所以(n-3)Hn=n(H3Hn-1+H4Hn-2+…+Hn-2H4+Hn-1H3)/2, （2）
將（1）式寫(xiě)成n+1的情況有：Hn+1=Hn+H3Hn-1+···+Hn-1H3+Hn=(2+2(n-3)/n)Hn=((4n-6)/n)Hn
數(shù)學(xué)上將下列數(shù)列稱為Catalan數(shù),C0=1,C1=1,Cn=C0Cn-1+C1Cn-2+…Cn-2C1+Cn-1C0,下表給出了前16個(gè)Catalan數(shù).
Catalan數(shù)字
0、1
1、1
2、2
3、5
4、14
5、42
6、132
7、429
8、1430
9、4862
10、16796
11、58786
12、208012
13、742900
14、2674440
15、9694845
顯然,n邊形的分割總數(shù)Hn=Cn-2.（只要設(shè)H2=1即可）