特殊计数序列Catalan数.ppt

*第八章特殊计数序列。如:斐波那契序列:fn=fn-1+fn-2(n≥3)翰若塔问题序列:hn=2hn-1+1(n≥1)错位排列数序列:D0,D1,D2,D3,…Dn,……等本节我们将继续研究4个著名的计数序列*(卡特朗)序列其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系。本次课将举出一些,后面还将见到。通过下面的例题我们来引入Catalan(卡特朗)序列。例:二叉树(或二元树)的计数问题。如3个结点可有5棵不同的二叉树,如下图所示。*一般地,设cn为n个结点的不同的二叉树的个数,定义c0=1。在n>0的情形下,二叉树有一个根结点及n-1个非根结点,设左子树Tl有k个结点,则右子树Tr有n-1-k个结点,于是每个不同的左子树有ck种时,-1-k种,由计数原理:*}构成的生成函数为:B(x)=c0+c1x+c2x2+c3x3+……+cnxn+……那么B(x)×B(x)=(c0+c1x+……)(c0+c1x+c2x2+……)B2(x)=(c0)2+(c0c1+c1c0)x+(c0c2+c1c1+c2c0)x2+(c0c3+c1c2+c2c1+c3c0)x3+………*根据我们在第十九讲中补充的关于生成函数有关结论可知:*}构成的生成函数可以表示为:B(x)与B2(x)在第n项的系数只相差一项*由于它们的首项都是1,将B(x):与B2(x)的序列的生成函数化成一致。那么我们得到生成函数B(x)满足的方程:其中B(0)=c0=1*解此二次方程,并应用牛顿二项式定理(P95)得:*作换元*常称为Catalan(卡特朗)数,}常称为Catalan(卡特朗)序列。常用第一个字母C表示,记为:C0,C1,C2,C3,…..Cn,……其中,通项: