Catalan数
Catalan数
预备知识:
$$
对角线剖分:
设\(A_1 A_2 A_3 ··· A_n\)是凸n边形.用n-3条（除端点外）无公共点的对角线,可以将它剖分为三角形,这样的剖分我们称它为对角线剖分.显然，对角线剖分的方法未必只有一种.例如上图,6边形的对角线剖分共有14种.我们将凸n边形的对角线剖分的种数,记为\(T_n-2\).容易知道,
$$ T_2 =2T_3 =5,T_4 =14 $$
为了能够得到统一的通项公式,通常约定,
$$ T_0 = T_1 =1$$
$ T_n $通常称为Catalan数，由大神Eugene Charles Catalan命名.据考证,Catalan数最早是由L. Eular于1753年在解决凸包划分成三角形问题的时候提出的(也有说法称是蒙古的明安图在1730年提出的).然而Eugen Otto Erwin Netto在他的论文中将该数归功于Catalan.
更多精彩
