【大学课件】特殊计数序列81 Catalan数.ppt
《【大学课件】特殊计数序列81 Catalan数.ppt》由会员分享,可在线阅读,更多相关《【大学课件】特殊计数序列81 Catalan数.ppt(43页珍藏版)》请在三一文库上搜索。
1、1,第八章 特殊计数序列 8.1 Catalan数,前面我们已经讨论过一些特殊计数序列的例子。如:斐波那契序列: f n = f n-1 + f n-2 (n 3) 翰若塔问题序列: hn = 2hn-1+ 1 (n 1) 错位排列数序列:D0, D1, D2, D3, Dn, 等 本节我们将继续研究4个著名的计数序列,http:/ Catalan数 Catalan(卡特朗)序列其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系。本次课将举出一些,后面还将见到。 通过下面的例题我们来引入Catalan(卡特朗)序列。 例 : 二叉树(或二元树)的计数问题。 如 3个结点可有5棵不同
2、的二叉树, 如下图所示。,http:/ B(x) = c0 + c1x + c2x2+ c3x3+cnxn+那么 B(x)B(x) = (c0 + c1x + ) (c0 + c1x +c2x2+ ) B2(x) = (c0)2+ (c0 c1+c1c0) x + (c0 c2+c1 c1 +c2 c0)x2+ (c0 c3+c1 c2 +c2 c1+c3 c0 )x3+,http:/ 关结论可知:,http:/ 与B2(x) 的序列的生成函数化成一致。 那么我们得到生成函数B(x)满足的方程: 其中B(0) =c0 =1,http:/ 其中,通项:,http:/ n 个+1 和 n个 1 构
3、成的 2n 项数列 a1, a2, , a2n若其部分和满足 a1a2 ak 0 k1,2,2n 的数列a1, a2. ak的个数等于第n个Catalan数,即 证明:n 个+1 和 n个 1 构成的 2n 项数列若其部分和满足 a1a2 ak 0,http:/ 数列。令Sn是由n个 +1 和 n个 1 构成的2n项数列的全体,An是其中可接受的部分,Un是其中不可接受的部分.于是: |Sn|An|Un| 而: 可见,通过计算|Un|进而计算出|An|; 对每个不可接受序列,总可以找到最小的正奇数k,使得ak=-1且ak之前的+1与-1的个数相等,即有a1+a2+ak-1=0, ak =-1。
4、,http:/ -1+1-1+1-1+1-1+1-1+1其中a7 = -1 现将这个不可接受序列中前k项的每一项取反号, 其余部分保持不变, 得到新序列变为m+1个+1和m-1个-1构成的序列。 例: 1-1+1-1+1-1+1+1-1+1注意有两个1连加 反之,对任一由n+1个+1和n-1个-1构成的序列,从左到右扫描,当+1的个数第一次比-1的个数多1时就把这些扫描到的项全部取反号,其余,http:/ 受序列。从而,易知不可接受序列的数目Un就与n+1个+1和n-1个-1所成的序列的数目相等。由于后者的数目为:,http:/ (1)从(0,0)点沿第一象限的格线到(n, n)点的不穿越方格
5、对角线的最短路径数; (2) 序列a1a2ak的元素顺序保持不变, 按不同结合方式插入合法圆括号对的方案数; (3) 用n-1条互不交叉的对角线把n+2条边(n1)的凸多边形拆分三角形化的方法数;,http:/ 2n个人排队上车,车票费为5角,2n个人 中有一半人持有一元面值钞票,一半人持有5角钞票,求不同的上车方案数,使得在这些方案中售票员总能用先上车的购票钱给后上车者找零; (5) 甲、乙二人比赛乒乓球, 最后结果为nn,比赛过程中甲始终不落后于乙的计分种数;,http:/ n个点的有序二叉树的个数; (7) n个叶子的完全二叉数的个数; (8) 圆周上2n个点连接成的n条两两互不相交的弦
6、分割圆的方案数。 以上8种类型的计数问题, 是典型的Catalan数组合问题,我们仅仅对其中的部分问题进行讨论;,http:/ 不穿越方格对角线ON的最短路径数; 沿格线前进不穿越对角线(但可接触对角线上的 格点)的路线分为走对角线上方或走对角线下方两种情形,由对称性,易知两种路线数相等。 因此,只需计算走一方的路线数(不妨计算对角线下方的路线数)。 设符合题意的路线为好路线,其总数记为gn;,http:/ 穿越对角线的路线记为 坏路线,其总数记为bn。 (a)图是44方格中的坏路线,(b)图是44方格变为53方格的后的路线。,O,N,N,O,http:/ 线可用一个包含n个R(右) 和n个U
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学课件 【大学课件】特殊计数序列81 Catalan数 大学 课件 特殊 计数 序列 81 Catalan
链接地址:https://www.31doc.com/p-3024808.html