特殊计数序列Catalan数.ppt

第八章第八章   特殊计数序列特殊计数序列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个著名的计数序列个著名的计数序列18.1  Catalan数数          Catalan(卡特朗卡特朗)序列其递推关系是序列其递推关系是非线性非线性的的,许多有意义的计数问题都导致这样的递推许多有意义的计数问题都导致这样的递推关系本次课将举出一些关系本次课将举出一些,后面还将见到后面还将见到         通过下面的例题我们来引入通过下面的例题我们来引入Catalan(卡特朗卡特朗)序列例例 ：：  二叉树（或二元树）的计数问题二叉树（或二元树）的计数问题如如 3个结点可有个结点可有5棵不同的二叉树棵不同的二叉树, 如下图所示。

如下图所示2        一一般般地地，，设设cn为为n个个结结点点的的不不同同的的二二叉叉树树的的个个数数，，定定义义c0=1在在n＞＞0的的情情形形下下，，二二叉叉树树有有一一个个根根结结点点及及n-1个个非非根根结结点点，，设设左左子子树树Tl有有k个个结结点点，，则则右右子子树树Tr有有n-1-k个个结结点点，，于于是是每每个个不不同同的的左左子子树树有有ck种种时时，，右右子子树树有有cn-1-k种种，，由由计计数数原理：原理：3令令由序列由序列{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+………4根据我们在第十九讲中补充的关于生成函数有根据我们在第十九讲中补充的关于生成函数有 关结论可知：关结论可知：5再由于序列再由于序列{cn}构成的生成函数可以表示为构成的生成函数可以表示为:B(x)与与B2(x)在第在第n项的系数只相差一项项的系数只相差一项6由于它们的首项都是由于它们的首项都是1,将将B(x)减去常数减去常数1后使得和后使得和式的每个单项式的幂大于等于式的每个单项式的幂大于等于1.再除以再除以x后就得后就得到生成函数为：到生成函数为：            与与B2(x) 的序列的生成函数化成一致。

的序列的生成函数化成一致   那么我们得到生成函数那么我们得到生成函数B(x)满足的方程：满足的方程： 其中其中B(0) =c0 =1 7解此二次方程，并应用牛顿二项式定理解此二次方程，并应用牛顿二项式定理(P95)得得:8作换元作换元9这个数这个数Cn常称为常称为Catalan( (卡特朗卡特朗) )数数, ,序列序列{Cn}常称为常称为Catalan( (卡特朗卡特朗) )序列序列常用第一个字常用第一个字母母C表示，记为：表示，记为：C0,C1,C2,C3,…..Cn,…… 其其中，通项：中，通项：10定理定理8.1.1     n 个个+1 和和 n个个 –1 构成的构成的 2n 项数列项数列           a1, a2, …, a2n若其部分和满足若其部分和满足                a1＋＋a2＋＋…＋＋ ak≥ 0      k＝＝1,2,…,2n的数列的数列a1, a2... ak的个数等于第的个数等于第n个个Catalan数，数，即即证明：证明：n 个个+1 和和 n个个 –1 构成的构成的 2n 项数列若其项数列若其部分和满足部分和满足      a1＋＋a2＋＋…＋＋ ak≥ 011则称该数列是则称该数列是可接受可接受的数列，否则是的数列，否则是不可接受不可接受的的            数列。

令数列令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 =-112例例:  -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+1……..注意有注意有两个两个1 1连加连加   反反之之，，对对任任一一由由n+1个个+1和和n-1个个-1构构成成的的序序列列，，从从左左到到右右扫扫描描，，当当+1的的个个数数第第一一次次比比-1的的个个数数多多1时就把这些扫描到的项全部取反号，其余时就把这些扫描到的项全部取反号，其余13项不变，结果又得到项不变，结果又得到n个个+1和和n个个-1构成的不可接构成的不可接       受受序序列列。

从从而而，，易易知知不不可可接接受受序序列列的的数数目目Un就就与与n+1个个+1和和n-1个个-1所所成成的的序序列列的的数数目目相相等等由于后者的数目为：由于后者的数目为：  14         Catalan数的组合学意义可罗列如下：数的组合学意义可罗列如下：        （（1））从从(0，，0)点点沿沿第第一一象象限限的的格格线线到到(n, n)点的不穿越方格对角线的最短路径数；点的不穿越方格对角线的最短路径数；        （（2）） 序序列列a1a2…ak的的元元素素顺顺序序保保持持不不变变，， 按不同结合方式插入合法圆括号对的方案数；按不同结合方式插入合法圆括号对的方案数；      （（3）） 用用n-1条互不交叉的对角线把条互不交叉的对角线把n+2条边条边(n≥1)的凸多边形拆分三角形化的方法数；的凸多边形拆分三角形化的方法数； 15（（4）） 2n个人排队上车，车票费为个人排队上车，车票费为5角，角，2n个人个人        中中有有一一半半人人持持有有一一元元面面值值钞钞票票，，一一半半人人持持有有5角角钞钞票票，，求求不不同同的的上上车车方方案案数数，，使使得得在在这这些些方方案案中中售售票票员员总总能能用用先先上上车车的的购购票票钱钱给给后后上上车车者找零；者找零；      （（5）） 甲甲、、乙乙二二人人比比赛赛乒乒乓乓球球，， 最最后后结结果果为为n∶ ∶n，，比比赛赛过过程程中中甲甲始始终终不不落落后后于于乙乙的的计计分分种种数；数；16       （（6）） n个点的有序二叉树的个数；个点的有序二叉树的个数；        （（7）） n个叶子的完全二叉数的个数；个叶子的完全二叉数的个数；        （（8）） 圆圆周周上上2n个个点点连连接接成成的的n条条两两两两互互不不相交的弦分割圆的方案数。

相交的弦分割圆的方案数           以以上上8种种类类型型的的计计数数问问题题,  是是典典型型的的Catalan数数组组合合问问题题，，我我们们仅仅仅仅对对其其中中的的部部分分问题进行讨论；问题进行讨论；17   (1)从从O(0,0)点沿第一象限的格线到点沿第一象限的格线到N(n,n)点的点的             不穿越方格对角线不穿越方格对角线ON的最短路径数；的最短路径数；  沿格线前进不穿越对角线沿格线前进不穿越对角线(但可接触对角线上的但可接触对角线上的          格点格点)的路线分为走对角线上方或走对角线下方的路线分为走对角线上方或走对角线下方两种情形，由对称性，易知两种路线数相等两种情形，由对称性，易知两种路线数相等 因此，只需计算走一方的路线数因此，只需计算走一方的路线数(不妨计算对角不妨计算对角线下方的路线数线下方的路线数)       设符合题意的路线为设符合题意的路线为好路线好路线，其总数记为，其总数记为gn；；18即即:遇到对角线就向右遇到对角线就向右; 穿越对角线的路线记为穿越对角线的路线记为         坏坏路路线线，，其其总总数数记记为为bn。

 (a)图图是是4×4方方格格中中的的坏坏路路线线，，(b)图图是是4×4方方格格变变为为5×3方方格格的的后的路线后的路线ONNO19易知易知n×n方格上从左下角到右上角的每一条路方格上从左下角到右上角的每一条路          线线可可用用一一个个包包含含n个个R(右右) 和和n个个U(上上)的的字字符符串串来来描描述述例例如如下下图图所所示示的的路路线线可可用用字字符符串串RUURRURU共共8个个字字符符来来表表示示，，可可以以看看出出，，R和和U的的数数量量各各占占一一半半这这样样的的字字符符串串可可以以由由在在给定的给定的2n个位置中为个位置中为R选择选择n个位置而不考虑顺序，个位置而不考虑顺序，其余其余n个位置填入个位置填入U于是，20有有C(2n,n)种可能的路线且有种可能的路线且有gn+bn=C(2n, n)，，        即：即：gn=C(2n, n)-bn, 故只需计算坏路线数故只需计算坏路线数bn         对对任任一一坏坏路路线线，，选选定定最最初初穿穿越越对对角角线线后后的的第第一一次次移移动动，，并并将将此此移移动动之之后后的的右右行行改改为为上上行行，，上上行行改改为为右右行行，，这这样样的的变变化化使使得得向向上上移移动动增增加加一一个个而而向向右右移移动动减减少少一一个个,即即可可得得到到一一条条(n+1)×(n-1)方方格格上上从从左左下下角角走走到到右右上上角角不不加加限制的路线；反之，限制的路线；反之， 对任一对任一(n+1)×(n-1)方格方格21上从左下角走到右上角不加限制的路线，从最上从左下角走到右上角不加限制的路线，从最        初初位位于于对对角角线线上上方方的的第第一一点点起起，，改改上上移移为为右右移移，，改改右右移移为为上上移移，，即即可可得得到到一一条条n×n方方格格上上(从从(0,0)点点到到(n,n)点点)的的坏坏路路线线。

亦亦即即, n×n方方格格上上的的坏坏路路线线与与(n+1)×(n-1)方方格格上上的的路路线线之之间间存存在在一一一一对对应应由由于于(n+1)×(n-1)方方格格的的路路线线为为:   C(2n, n+1)或或C(2n, n-1)，，两两者者相等相等, 故取故取bn=C(2n, n-1)从而有：从而有：22 注注意意，，在在求求对对角角线线下下方方的的好好路路线线数数时时，，每每条条走走过过对对角角线线上上方方的的路路线线都都作作为为坏坏路路线线计计入入了了bn进进而而，，仅仅走走对对角角线线一一侧侧且且不不穿穿越越对对角角线线         的的总路径数为总路径数为Catalan数：数：23（（3）用互不交叉的对角线把）用互不交叉的对角线把n+1条边条边(n≥2) 的的         凸多边形三角形化分的方法数；凸多边形三角形化分的方法数；余点依次相邻标记余点依次相邻标记24          令令hn表示将表示将n+1(n≥2)边凸多边形进行三角边凸多边形进行三角              形拆分的方案数，则当形拆分的方案数，则当n=1时，时，h1=1，当，当n≥3时，任取多边形一边为时，任取多边形一边为基边基边记作记作e，其两端，其两端点一端记为点一端记为v1，一端记为，一端记为vn+1，余点依次相邻标，余点依次相邻标记如图所示。

现以记如图所示现以v1，，vn+1及任意顶点及任意顶点vk+1(k=1,2,…,n-1)构作一个三角形，该三角形构作一个三角形，该三角形将凸多边形分为将凸多边形分为F1, F2两个区域两个区域25其中，其中，F1由由k+1边凸多边形围成，其三角形拆分边凸多边形围成，其三角形拆分      方案数为方案数为hk，，F2由由n-k+1边凸多边形围成，边凸多边形围成，其三角形剖分方案数为其三角形剖分方案数为hn-k，， F1与与F2的边数关的边数关系是系是:    [(k+1)+(n-k+1)+1]-2 = n+1(总边数总边数)26由乘法原理知由乘法原理知                              易证易证 对于六边形时对于六边形时,即当即当n=5时时,可求得分拆三角形数可求得分拆三角形数:27 凸凸6边形边形(n=5)的的14个拆分方案个拆分方案       其中从同一顶点引出其中从同一顶点引出3条对角线的有条对角线的有6种种；从；从两个顶点各引出两个顶点各引出2条对角线的又有条对角线的又有6种种；从；从3个互个互不相邻点连接的有不相邻点连接的有2种种，共，共14种。

种28   下面证明下面证明Catalan数满足数满足1阶齐次递推关系；阶齐次递推关系；                由于由于  所以有：所以有：29   我们可义求出前几项的我们可义求出前几项的Catalan数的数值：数的数值：             C0 = 1 ,      C1 = 1 ,     C2 = 2 ,    C3 = 5  C4 = 14 ,    C5 =42 ,    C6 = 132, C7 =429  C8 =1430,  C9 = 4862  ,…………….    现在我们定义一个新的数列：现在我们定义一个新的数列：为了方便给它取名叫做为了方便给它取名叫做拟拟- - Catalan数数令：30            将将Catalan数数的的递递推推关关系系代代入入得得到到拟拟-Catalan数的递推关系：数的递推关系：这样，拟这样，拟-Catalan数的递推关系和初值如下：数的递推关系和初值如下：31            利用这个递推关系，可以计算前几个利用这个递推关系，可以计算前几个       拟拟-Catalan数：数：    我们还可以求出拟我们还可以求出拟-Catalan数的计算公式：数的计算公式：32例：设例：设a1,a2,…,an是是n个数个数 。

定义这些数的一种定义这些数的一种       乘法格式乘法格式是指是指a1,a2,…,an任意两个或者它们任意两个或者它们部分积之间的部分积之间的n-1种乘法运算的方案计算种乘法运算的方案计算n个个数的不同乘法格式的个数数的不同乘法格式的个数分析：设分析：设hn是是n个数的不同乘法格式的个数个数的不同乘法格式的个数  那么那么:    h1 = 1  ,  一个数的乘法格式一个数的乘法格式; h2 = 2  ,  两个数的乘法格式两个数的乘法格式; (a1×a2) 和和(a2×a1) 33           h3 = 12  ,  三个数的乘法格式三个数的乘法格式;       (a1×(a2×a3)), (a2×(a1×a3)),(a3×(a1×a2))        (a1×(a3×a2)), (a2×(a3×a1)),(a3×(a2×a1))        ((a2×a3)×a1), ((a1×a3)×a2), ((a1×a2)×a3)       ((a3×a2)×a1), ((a3×a1)×a2), ((a2×a1)×a3)      看得出看得出, 三个数的乘法格式都需要两次乘法三个数的乘法格式都需要两次乘法,两组括号因子两组括号因子,每种格式的乘法就对应一括号每种格式的乘法就对应一括号34内的因子内的因子, ,一般说来每个乘法格式都可以通过以一般说来每个乘法格式都可以通过以           看成是由某种看成是由某种规定顺序规定顺序列出：列出：a1,a2,a3, ….an而后插入而后插入 n-1对括号和对括号和n-1个个×号使得每对号使得每对括号都指定两个因子的乘积括号都指定两个因子的乘积,例如其中就有例如其中就有:           (a1×(a2×(a3×(a4×(a5×(a6 ×….)))…..))       一种乘法格式。

一种乘法格式      我们利用归纳法来验证递推关系：我们利用归纳法来验证递推关系：    35 i) 取取a1,a2, a3,….an-1的一种乘法格式的一种乘法格式(它有它有n-2次次乘乘        法和法和n-2组括号组括号), 将将an插入到插入到n-2个乘法运算个乘法运算中任一个中任一个×号两侧的任一侧，有：号两侧的任一侧，有：2×(n-2)种；种；对于任一个乘法因子对于任一个乘法因子(括号括号)由分左右两侧，所由分左右两侧，所以共有以共有:       2×2×(n-2)种种  ii)取取a1,a2, a3,….an-1的一种乘法格式的一种乘法格式, 将将an放到放到整个表达式两侧的任一侧又有整个表达式两侧的任一侧又有2倍种36由由h3 = 12 ，分析任一中乘法格式，分析任一中乘法格式(a1×(a2×a3)), 可以有可以有10个位置插入个位置插入a4  故故h4 = (4*4－－6)*12=120由此可见，序列由此可见，序列{ hn}与拟与拟-Catalan数有相同的数有相同的递推关系，故有：递推关系，故有：则：则：hn=2×2× (n-2) ×hn-1+2×hn-1         从而从而   hn= (4n-6) hn-1                n≥ 2     37 上例中我们只考虑了对以上例中我们只考虑了对以规定顺序规定顺序a1,a2, a3,….an列成的列成的n个数的那些乘法格式进行计数个数的那些乘法格式进行计数,例如统计例如统计了：了： a1,a2, a3而没有考虑而没有考虑 a2,a3, a1;令令gn是表示是表示带有这种附加限制的乘法格式数带有这种附加限制的乘法格式数,将这将这n个数全排：个数全排：      hn= n! gn, 因此，我们有：因此，我们有：38这个序列关系与凸这个序列关系与凸(n+1)边形区域通过在区域内插边形区域通过在区域内插           入入n个不相交的对角线而分成三角形区域的个不相交的对角线而分成三角形区域的方法数相同。

方法数相同a1a2a3a4a5a6a7(((a1a2)(a3(a4a5)))(a6a7))(a4a5)(a1a2)(a3(a4a5))(a6a7)((a1a2)(a3(a4a5)))这是这是n=7的情况的情况因为构造三角因为构造三角形的三个顶点形的三个顶点没有次序区分没有次序区分.39总总        结结                    本次课我们介绍了本次课我们介绍了Catalan数序列和数序列和    拟拟-Catalan数序列等知识由于它们的递推关数序列等知识由于它们的递推关系是非线性的，生成函数和序列通项显的比较系是非线性的，生成函数和序列通项显的比较特殊可以牢记特殊可以牢记Catalan数序列和拟数序列和拟-Catalan数数序列的固定公式序列的固定公式40本次授课到此结束本次授课到此结束作业如下作业如下:    P193    1,  3,  41.设在圆上选择设在圆上选择2n个（等间隔的）点个（等间隔的）点 证证明将这些点成对连接起来使所得到的明将这些点成对连接起来使所得到的n条条线段不相交的方法数等于第线段不相交的方法数等于第n个个Catalan数数Cn。

413.写出四个数的所有乘法格式并对应它们的写出四个数的所有乘法格式并对应它们的凸五边形的三角形分拆凸五边形的三角形分拆4.确定对应下列乘法格式的凸多边形区域的确定对应下列乘法格式的凸多边形区域的三角形划分三角形划分 i) (a1×(((a2×a3)×(a4×a5) )×a6))ii) (((a1×a2)×(a3×(a4×a5))×((a6×a7) ×a8))42下次上课内容：下次上课内容：                      8.2  差分序列和差分序列和Stirling 数数                                       （一）（一）43。