liweiguo_组合数学第八章习题答案

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⎡x11,x12,\"x1n⎤

⎥

⎣x21,x22,\"x2n⎦

的个数等于第n 个Catalan数Cn 证明：第一行对应一个n个−1的序列 第二行对应一个n个+1的序列 a1,a2,\"a2n

为保证x11∑a

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）