特殊计数序列81Catalan数.ppt

该【特殊计数序列81Catalan数 】是由【tieruogong】上传分享，文档一共【43】页，该文档可以免费在线阅读，需要了解更多关于【特殊计数序列81Catalan数 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
前面我们已经讨论过一些特殊计数序列的例子。如：斐波那契序列： f n = f n-1 + f n-2 (n ≥3)
翰若塔问题序列： hn = 2hn-1+ 1 (n ≥1)
错位排列数序列：D0, D1, D2, D3,… Dn, ……等
本节我们将继续研究4个著名的计数序列
添加标题
添加标题
添加标题
添加标题
第八章 特殊计数序列 Catalan数
2
Catalan数
Catalan(卡特朗)序列其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系。本次课将举出一些,后面还将见到。
通过下面的例题我们来引入Catalan(卡特朗)序列。
例 ： 二叉树（或二元树）的计数问题。
如 3个结点可有5棵不同的二叉树, 如下图所示。
3
一般地，设cn为n个结点的不同的二叉树的个数，定义c0=1。在n＞0的情形下，二叉树有一个根结点及n-1个非根结点，设左子树Tl有k个结点，则右子树Tr有n-1-k个结点，于是每个不同的左子树有ck种时，右子树有cn-1-k种，由计数原理：
4
令由序列{cn}构成的生成函数为：
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+………
5
根据我们在第十九讲中补充的关于生成函数有
关结论可知：
6
B(x)与B2(x)在第n项的系数只相差一项
再由于序列{cn}构成的生成函数可以表示为:
7
由于它们的首项都是1,将B(x)：
与B2(x) 的序列的生成函数化成一致。
那么我们得到生成函数B(x)满足的方程：
其中B(0) =c0 =1
8
解此二次方程，并应用牛顿二项式定理(P95)得:
9
作换元
10
这个数Cn常称为Catalan(卡特朗)数,序列{Cn}常称为Catalan(卡特朗)序列。常用第一个字母C表示，记为：C0,C1,C2,C3,…..Cn,…… 其中，通项：