特殊计数序列81 Catalan数ppt课件

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个著名的计数序列个著名的计数序列docin/sundae_meng28.1 Catalan数数 Catalan(卡特朗卡特朗)序列其递推关系是非线性序列其递推关系是非线性

2、的的,许多有意义的计数问题都导致这样的递推许多有意义的计数问题都导致这样的递推关系。本次课将举出一些关系。本次课将举出一些,后面还将见到。后面还将见到。 通过下面的例题我们来引入通过下面的例题我们来引入Catalan(卡特卡特朗朗)序列。序列。例例 ： 二叉树或二元树的计数问题。二叉树或二元树的计数问题。如如 3个结点可有个结点可有5棵不同的二叉树棵不同的二叉树, 如下图所示。如下图所示。docin/sundae_meng3 一般地，设一般地，设cn为为n个结点的不同的二叉树的个结点的不同的二叉树的个数，定义个数，定义c0=1。在。在n0的情形下，二叉树有的情形下，二叉树有一个根结点及一个根结

3、点及n-1个非根结点，设左子树个非根结点，设左子树Tl有有k个结点，则右子树个结点，则右子树Tr有有n-1-k个结点，于是每个个结点，于是每个不同的左子树有不同的左子树有ck种时，右子树有种时，右子树有cn-1-k种，种，由计数原理：由计数原理：docin/sundae_meng4)0(,101ncccnkknkn令由序列令由序列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 +

4、 (c0 c2+c1 c1 +c2 c0)x2+ (c0 c3+c1 c2 +c2 c1+c3 c0 )x3+docin/sundae_meng5nnkknknkkkkkkkkkxccxccxccxccccxB.)()(0033032202101002根据我们在第十九讲中补充的关于生成函数有根据我们在第十九讲中补充的关于生成函数有 关结论可知：关结论可知：)0(.01322110101ncccccccccccnnnnnkknkndocin/sundae_meng6再由于序列再由于序列cn构成的生成函数可以表示为构成的生成函数可以表示为:比较发现与nnkknknnnnnnnnnkknknnnnx

5、ccxBxccccccccxccxcxB)(.)(00201322110010110B(x)与与B2(x)在第在第n项的系数只相差一项项的系数只相差一项nknknknnknknknxccxcc001010与docin/sundae_meng7由于它们的首项都是由于它们的首项都是1,将将B(x)减去常数减去常数1后使得后使得和式的每个单项式的幂大于等于和式的每个单项式的幂大于等于1.再除以再除以x后后就得到生成函数为：就得到生成函数为： 与与B2(x) 的序列的生成函数化成一致。的序列的生成函数化成一致。 那么我们得到生成函数那么我们得到生成函数B(x)满足的方程：满足的方程： 其中其中B(0)

6、 =c0 =1 1)(10010111nknknknnknknknxccxccxxB)(1)(2xBxxBdocin/sundae_meng8解此二次方程，并应用牛顿二项式定理解此二次方程，并应用牛顿二项式定理(P95)得得: )4(211 (1 21)4(21)4(021(1 21)4(211 212)41 (12411)(110021nnnnnnnxnxxnxxxnxxxxxxBdocin/sundae_meng9)(2)1(1)1(2)1(22)1()1(2)1(121:2)1(1212)1(21)4(2121)(95121)1(21)1(120122111211Pnnnncxnxnxn

7、xxBnnnnnnnnnnnnnnnnnn见因此作换元作换元docin/sundae_meng10nnnnnncnnnnn2) 1(12) 1(22) 1() 1(1212这个数这个数Cn常称为常称为Catalan(卡特朗卡特朗)数数,序列序列Cn常称为常称为Catalan(卡特朗卡特朗)序列。常用第一个字母序列。常用第一个字母C表示，记为：表示，记为：C0,C1,C2,C3,.Cn, 其中，其中，通项：通项：.)2, 1 ,0(211nnnnCndocin/sundae_meng11定理定理8.1.1 n 个个+1 和和 n个个 1 构成的构成的 2n 项数列项数列 a1, a2, , a2

8、n若其部分和满足若其部分和满足 a1a2 ak 0 k1,2,2n的数列的数列a1, a2. ak的个数等于第的个数等于第n个个Catalan数，数，即即证明：证明：n 个个+1 和和 n个个 1 构成的构成的 2n 项数列若其项数列若其部分和满足部分和满足 a1a2 ak 0.)2, 1 ,0(211nnnnCndocin/sundae_meng12则称该数列是可接受的数列，否则是不可接受的则称该数列是可接受的数列，否则是不可接受的 数列。令数列。令Sn是由是由n个个 +1 和和 n个个 1 构成的构成的2n项数列的全体，项数列的全体，An是其中可接受的部分，是其中可接受的部分，Un是其中不

9、可接受的部分是其中不可接受的部分.于是于是: |Sn|An|Un| 而而: 可见，通过计算可见，通过计算|Un|进而计进而计算出算出|An|; 对每个不可接受序列，总可以找到对每个不可接受序列，总可以找到最小的正奇数最小的正奇数k，使得，使得ak=-1且且ak之前的之前的+1与与-1的个数相等，即有的个数相等，即有a1+a2+ak-1=0, ak =-1。nnSn2docin/sundae_meng13例例: -1+1-1+1-1+1-1+1-1+1.其中其中a7 = -1 现将这个不可接受序列中前现将这个不可接受序列中前k项的每一项取项的每一项取反号，反号， 其余部分保持不变，其余部分保持不

10、变， 得到新序列变为得到新序列变为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时就把这些扫描到的项全部取反号，其他时就把这些扫描到的项全部取反号，其他,.,221naaadocin/sundae_meng14项不变，结果又得到项不变，结果又得到n个个+1和和n个个-1构成的不可接构成的不可接 受序列。从而，易知不可接受序列的数目受序列

11、。从而，易知不可接受序列的数目Un就与就与n+1个个+1和和n-1个个-1所成的序列的数目相等。所成的序列的数目相等。由于后者的数目为：由于后者的数目为： nnnnnnnnnnnnnnnnnnnnnnnnnnnnUSAnnnUnnnn21111!)!2()1(1()!1(!)!2()111()!1(!)!2()!1()!1()!2(!)!2()!1()!1()!2(2)!1()!1()!2(那么docin/sundae_meng15 Catalan数的组合学意义可罗列如下：数的组合学意义可罗列如下： （1从从(0，0)点沿第一象限的格线到点沿第一象限的格线到(n, n)点的不穿越方格对角线的最

12、短路径数；点的不穿越方格对角线的最短路径数； （2） 序列序列a1a2ak的元素顺序保持不变，的元素顺序保持不变， 按不同结合方式插入合法圆括号对的方案数；按不同结合方式插入合法圆括号对的方案数； （3） 用用n-1条互不交叉的对角线把条互不交叉的对角线把n+2条边条边(n1)的凸多边形拆分三角形化的方法数；的凸多边形拆分三角形化的方法数； docin/sundae_meng16（4） 2n个人排队上车，车票费为个人排队上车，车票费为5角，角，2n个人个人 中有一半人持有一元面值钞票，一半人持中有一半人持有一元面值钞票，一半人持有有5角钞票，求不同的上车方案数，使得在这角钞票，求不同的上车方案

13、数，使得在这些方案中售票员总能用先上车的购票钱给后上些方案中售票员总能用先上车的购票钱给后上车者找零；车者找零； （5） 甲、乙二人比赛乒乓球，甲、乙二人比赛乒乓球， 最后结果为最后结果为n n，比赛过程中甲始终不落后于乙的计分，比赛过程中甲始终不落后于乙的计分种数；种数；docin/sundae_meng17 （6） n个点的有序二叉树的个数；个点的有序二叉树的个数； （7） n个叶子的完全二叉数的个数；个叶子的完全二叉数的个数； （8） 圆周上圆周上2n个点连接成的个点连接成的n条两两互不条两两互不相交的弦分割圆的方案数。相交的弦分割圆的方案数。 以 上以 上 8种 类 型 的 计 数 问

14、 题种 类 型 的 计 数 问 题 , 是 典 型 的是 典 型 的Catalan数组合问题，我们仅仅对其中的部分数组合问题，我们仅仅对其中的部分问题进行讨论；问题进行讨论；docin/sundae_meng18 (1)从从O(0,0)点沿第一象限的格线到点沿第一象限的格线到N(n,n)点的点的 不穿越方格对角线不穿越方格对角线ON的最短路径数；的最短路径数； 沿格线前进不穿越对角线沿格线前进不穿越对角线(但可接触对角线上的但可接触对角线上的 格点格点)的路线分为走对角线上方或走对角线下方的路线分为走对角线上方或走对角线下方两种情形，由对称性，易知两种路线数相等。两种情形，由对称性，易知两种路

15、线数相等。 因此，只需计算走一方的路线数因此，只需计算走一方的路线数(不妨计算对角不妨计算对角线下方的路线数线下方的路线数)。 设符合题意的路线为好路线，其总数记为设符合题意的路线为好路线，其总数记为gn；docin/sundae_meng19即即:遇到对角线就向右遇到对角线就向右; 穿越对角线的路线记为穿越对角线的路线记为 坏路线，其总数记为坏路线，其总数记为bn。 (a)图是图是44方格方格中的坏路线，中的坏路线，(b)图是图是44方格变为方格变为53方格的方格的后的路线。后的路线。(a)(b)ONNOdocin/sundae_meng20易知易知nn方格上从左下角到右上角的每一条路方格上

16、从左下角到右上角的每一条路 线可用一个包含线可用一个包含n个个R(右右) 和和n个个U(上上)的字的字符串来描述。例如下图所示的路线可用字符串符串来描述。例如下图所示的路线可用字符串RUURRURU共共8个字符来表示，可以看出，个字符来表示，可以看出，R和和U的数量各占一半。这样的字符串可以由在的数量各占一半。这样的字符串可以由在给定的给定的2n个位置中为个位置中为R选择选择n个位置而不考虑顺序，个位置而不考虑顺序，其余其余n个位置填入个位置填入U。于是，。于是，docin/sundae_meng21有有C(2n,n)种可能的路线。且有种可能的路线。且有gn+bn=C(2n, n)， 即：即：

17、gn=C(2n, n)-bn, 故只需计算坏路线数故只需计算坏路线数bn。 对任一坏路线，选定最初穿越对角线后的第对任一坏路线，选定最初穿越对角线后的第一次移动，并将此移动之后的右行改为上行，一次移动，并将此移动之后的右行改为上行，上行改为右行，这样的变化使得向上移动增加上行改为右行，这样的变化使得向上移动增加一个而向右移动减少一个一个而向右移动减少一个,即可得到一条即可得到一条(n+1)(n-1)方格上从左下角走到右上角不加限方格上从左下角走到右上角不加限制的路线；反之，制的路线；反之， 对任一对任一(n+1)(n-1)方格方格docin/sundae_meng22上从左下角走到右上角不加限

18、制的路线，从最上从左下角走到右上角不加限制的路线，从最 初位于对角线上方的第一点起，改上移为初位于对角线上方的第一点起，改上移为右移，改右移为上移，即可得到一条右移，改右移为上移，即可得到一条nn方方格上格上(从从(0,0)点到点到(n,n)点点)的坏路线。亦即的坏路线。亦即, nn方格上的坏路线与方格上的坏路线与(n+1)(n-1)方格上的方格上的路线之间存在一一对应。由于路线之间存在一一对应。由于(n+1)(n-1)方方格的路线为格的路线为: C(2n, n+1)或或C(2n, n-1)，两者，两者相等相等, 故取故取bn=C(2n, n-1)。从而有：。从而有：docin/sundae_

19、meng23),2(1111!)!2() 1(1)!1( !)!2(111)!1( !)!2()!1()!1()!2(!)!2() 1,2(),2(),2(nnCnnnnnnnnnnnnnnnnnnnnnnnCnnCbnnCgnn 留意，在求对角线下方的好路线数时，每条走过对角线上方的路线都作为坏路线计入了bn。进而，仅走对角线一侧且不穿越对角线 的总路径数为Catalan数：nnnnnCn211),2(11docin/sundae_meng24（3用互不交叉的对角线把用互不交叉的对角线把n+1条边条边(n2) 的的 凸多边形三角形化分的方法数；凸多边形三角形化分的方法数；vkvk 1vk 1

20、F1v1eF2vk 2vnvn 1余点依次相邻标记余点依次相邻标记docin/sundae_meng25 令令hn表示将表示将n+1(n2)边凸多边形进行三角边凸多边形进行三角 形拆分的方案数，则当形拆分的方案数，则当n=1时，时，h1=1，当，当n3时，任取多边形一边为基边记作时，任取多边形一边为基边记作e，其两端，其两端点一端记为点一端记为v1，一端记为，一端记为vn+1，余点依次相邻，余点依次相邻标记如图所示。现以标记如图所示。现以v1，vn+1及任意顶点及任意顶点vk+1(k=1,2,n-1)构作一个三角形，该三角形构作一个三角形，该三角形将凸多边形分为将凸多边形分为F1, F2两个区

21、域。两个区域。docin/sundae_meng26其中，其中，F1由由k+1边凸多边形围成，其三角形拆边凸多边形围成，其三角形拆分分 方案数为方案数为hk，F2由由n-k+1边凸多边形围成，边凸多边形围成，其三角形剖分方案数为其三角形剖分方案数为hn-k， F1与与F2的边数的边数关系是关系是: (k+1)+(n-k+1)+1-2 = n+1(总边数总边数)vkvk 1vk 1F1v1eF2vk 2vnvn 1docin/sundae_meng27由乘法原理知由乘法原理知 易证易证 对于六边形时对于六边形时,即当即当n=5时时,可求得分拆三角形数可求得分拆三角形数:11nkknknhhhnn

22、nhnnnhnn2111221114485115252515hdocin/sundae_meng28 凸6边形(n=5)的14个拆分方案 其中从同一顶点引出其中从同一顶点引出3条对角线的有条对角线的有6种；从种；从两个顶点各引出两个顶点各引出2条对角线的又有条对角线的又有6种；从种；从3个互个互不相邻点连接的有不相邻点连接的有2种，共种，共14种。种。docin/sundae_meng29 下面证明下面证明Catalan数满足数满足1阶齐次递推关系；阶齐次递推关系； 由于由于 所以有：所以有：1)1(124124)12)(2(11)!1()!1()!22(1!)!2(11011CnCnnCnn

23、nnnnnnnnnnnnCCnnnn所以122(1)1111nnnnCCnnnndocin/sundae_meng30 我们可义求出前几项的我们可义求出前几项的Catalan数的数值：数的数值： C0 = 1 , C1 = 1 , C2 = 2 , C3 = 5 C4 = 14 , C5 =42 , C6 = 132, C7 =429 C8 =1430, C9 = 4862 ,. 现在我们定义一个新的数列：现在我们定义一个新的数列：为了方便给它取名叫做拟为了方便给它取名叫做拟- Catalan数。令：数。令：,.,.,*3*2*1nCCCC,.)3 , 2 , 1(!1*nCnCnndocin

24、/sundae_meng31 将将Catalan数的递推关系代入得到拟数的递推关系代入得到拟-Catalan数的递推关系：数的递推关系：111! 1:0*1CC我们有初值*12221*)64()!1)(64(64!1)1(2)1(4!nnnnnnCnCnnCnnnCnnnCnC这样，拟这样，拟-Catalan数的递推关系和初值如下：数的递推关系和初值如下：1)2()64(*1*1*CnCnCnndocin/sundae_meng32 利用这个递推关系，可以计算前几个利用这个递推关系，可以计算前几个 拟拟-Catalan数：数：3024012168021201*4*3*4*2*4*1CCCCCC

25、 我们还可以求出拟我们还可以求出拟-Catalan数的计算公式：数的计算公式：122)!1(1) 1( 21) 1(1!1*nnnnnnnCnCnndocin/sundae_meng33例：设例：设a1,a2,an是是n个数个数 。定义这些数的一种。定义这些数的一种 乘法格式是指乘法格式是指a1,a2,an任意两个或者它们任意两个或者它们部分积之间的部分积之间的n-1种乘法运算的方案。计算种乘法运算的方案。计算n个个数的不同乘法格式的个数。数的不同乘法格式的个数。分析：设分析：设hn是是n个数的不同乘法格式的个数。个数的不同乘法格式的个数。 那么那么: h1 = 1 , 一个数的乘法格式一个数

26、的乘法格式; h2 = 2 , 两个数的乘法格式两个数的乘法格式; (a1a2) 和和(a2a1) docin/sundae_meng34 h3 = 12 , 三个数的乘法格式三个数的乘法格式; (a1(a2a3), (a2(a1a3),(a3(a1a2) (a1(a3a2), (a2(a3a1),(a3(a2a1) (a2a3)a1), (a1a3)a2), (a1a2)a3) (a3a2)a1), (a3a1)a2), (a2a1)a3) 看得出看得出, 三个数的乘法格式都需要两次乘法三个数的乘法格式都需要两次乘法,两组括号因子两组括号因子,每种格式的乘法就对应一括号每种格式的乘法就对应一

27、括号docin/sundae_meng35内的因子内的因子,一般说来每个乘法格式都可以通过以一般说来每个乘法格式都可以通过以 看成是由某种规定顺序列出：看成是由某种规定顺序列出：a1,a2,a3, .an而后插入而后插入 n-1对括号和对括号和n-1个个号使得每对括号都指定两个因子的乘积号使得每对括号都指定两个因子的乘积,例如例如其中就有其中就有: (a1(a2(a3(a4(a5(a6 .).) 一种乘法格式。一种乘法格式。 我们利用归纳法来验证递推关系：我们利用归纳法来验证递推关系： docin/sundae_meng36 i) 取取a1,a2, a3,.an-1的一种乘法格式的一种乘法格式

28、(它有它有n-2次次乘乘 法和法和n-2组括号组括号), 将将an插入到插入到n-2个乘法运算个乘法运算中任一个号两侧的任一侧，有：中任一个号两侧的任一侧，有：2(n-2)种；种；对于任一个乘法因子对于任一个乘法因子(括号括号)由分左右两侧，所由分左右两侧，所以共有以共有: 22(n-2)种种 ii)取取a1,a2, a3,.an-1的一种乘法格式的一种乘法格式, 将将an放到放到整个表达式两侧的任一侧。又有整个表达式两侧的任一侧。又有2倍种。倍种。docin/sundae_meng37由由h3 = 12 ，分析任一中乘法格式，分析任一中乘法格式(a1(a2a3), 可以有可以有10个位置插入个位置插入a4 故故h4 = (4*46)*12=120由此可见，序列由此可见，序列 hn与拟与拟-Catalan数有相同的数有相同的递推关系，故有：递推关系，故有：那么：那么：hn=22 (n-2) hn-1+2hn-1 从而从而 hn= (4n-6) hn-1 n 2 22(1)!11nnnhCnnndocin/sundae_meng38 上例中我们只考虑了对以规定顺序上例中我们只考虑了对以规定顺序a1,a2, a3,.an列成的列成的n个数的那些乘法格式进行计数个数的那些乘法格式进行计数,例如统计例如统计了：了： a1,a2, a3而没有考虑而没有考虑 a2,a3, a1;令令gn是