1、设在圆上选择2n个(等间隔的)点。证明将这些点成对连接起来所得到的n条线段不相交的方法数等于第n个Catalan数Cn。
证明 设hn为将圆上的2n个点成对连接起来得到的n条不相交线段的方法数。我们证明序列h0,h1,h2,…与Catalan数序列C0,C1,C2,…满足同样的递推关系和初始条件。
设圆上的2n个点顺时针依次排列为a0,a1,a2,…a2n−1,若连接线段a0 ak,则其左边和右边的点不能相互连接,那样会与a0 ak相交。a0 ak左边的点的数目和它右边的点的数目都应当是偶数,即k是奇数。若a0 ak左边的点的数目是2i,则a0 ak右边的点的数目就是2(n-1-i)。随着k从1变到2n-1,i从0变到n-1。因此,序列h0,h1,h2,…满足递推关系
hn=h0hn−1+h1hn−2+\"+hn−1h0
令gn=Cn−1 ,则gn=
1⎛2n−2⎞
⎜⎟。由定理7.6.1知道序列g1,g2,g3,…满足递推关系 ⎜⎟n⎝n−1⎠
gn=g1gn−1+g2gn−2+\"+gn−1g1
因此,
Cn=gn+1=g1gn+g2gn−1+\"gng1=C0Cn−1+C1Cn−2+\"+Cn−1C0
又有h0=1=C0,序列h0,h1,h2,…与Catalan数序列C0,C1,C2,…满足同样的递推关系和初始条件。
2、证明,能够由数1,2,……,2n构造且满足
x11 x11 ⎥ ⎣x21,x22,\"x2n⎦ 的个数等于第n 个Catalan数Cn 证明:第一行对应一个n个−1的序列 第二行对应一个n个+1的序列 a1,a2,\"a2n 为保证x11 i=1 k i ≥0,(k=1,2,\",2n) 1⎛2n⎞ ⎟⎜ ⎟⎜n+1⎝n⎠ 由定理知,可得2行n列数组个数为第n个Catalan数Cn= 4、确定对应下列乘法格式的凸多边形区域的三角形划分: (1)(a1×(((a2×a3)×(a4×a5))×a6)) (2)(((a1×a2)×(a3×(a4×a5))×((a6×a7)×a8))) 解:(1) (2) 因篇幅问题不能全部显示,请点此查看更多更全内容