您好,欢迎来到爱go旅游网。
搜索
您的当前位置:首页liweiguo_组合数学第八章习题答案

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

来源:爱go旅游网
第八章 特殊计数序列

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)

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- igat.cn 版权所有

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务