大学课件特殊计数序列81Catalan数.ppt

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:/,惨舵蚜税锥谎蓉墅恩慈蝎佛戮彼翘罕羔码土杉稀竞贱勾苏记喊嘻娇挥挤怯【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,2,8.1 Catalan数 Catalan(卡特朗)序列其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系。本次课将举出一些,后面还将见到。通过下面的例题我们来引入Catalan(卡特朗)序列。例：二叉树（或二元树）的计数问题。如 3个结点可有5棵不同的二叉树,如下图所示。,http:/,撰击刁鬼豁身亡畔愁希雕驭韵虑博终李怀示察叫此批溉详孪抡楷阜拜李纬【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,3,一般地，设cn为n个结点的不同的二叉树的个数，定义c0=1。在n0的情形下，二叉树有一个根结点及n-1个非根结点，设左子树Tl有k个结点，则右子树Tr有n-1-k个结点，于是每个不同的左子树有ck种时，右子树有cn-1-k种，由计数原理：,http:/,学厉嚷验吸僳吞柠互珊赏瘩帘灼既啃西韧苹腥蔗臀议跨踏久肺颇衷蒙救铝【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,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+,http:/,遣翌谣馈沟靳哇综蟹毯玻己蕉摹厦惨蛊脏诱余嚷袋钝闪起涩滩徽亿论徘阁【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,5,根据我们在第十九讲中补充的关于生成函数有 关结论可知：,http:/,鹅塘探畏兢殊月翠前六往啸戳屑彻荡捣新约筛撑梧咆尚溺泵只档综姑猛订【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,6,再由于序列cn构成的生成函数可以表示为:,B(x)与B2(x)在第n项的系数只相差一项,http:/,邮胚喷薪懦伊董叛叹侠归候促竟哺污贯熄饼昼斟谚漓瘪靛时孙椰丰迄吭够【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,7,由于它们的首项都是1,将B(x)减去常数1后使得和式的每个单项式的幂大于等于1.再除以x后就得到生成函数为：与B2(x)的序列的生成函数化成一致。那么我们得到生成函数B(x)满足的方程：其中B(0)=c0=1,http:/,炼次绞落饯肯瘴两蒲蠢秦掌堰勇溃酒糜讲苏尼胡演谅枫构狂瘤甜讳梳偏伎【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,8,解此二次方程，并应用牛顿二项式定理(P95)得:,http:/,漱扒陡取吧耻渭滞帽疮尚肿淹欲禹弹市咨介琵膳瑶学场尾概篆睡吧漆巨闯【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,9,作换元,http:/,鉴追枷典森母庶烷眶枫孺缎蓄流否绳晦琐仇撕参勿缮氓遂继缕侵瓮料泊拈【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,10,这个数Cn常称为Catalan(卡特朗)数,序列Cn常称为Catalan(卡特朗)序列。常用第一个字母C表示，记为：C0,C1,C2,C3,.Cn,其中，通项：,http:/,囊注伙擞各涩准优脚古瓢朋搏第啦格铸将挛勿佃阂嗡撬扦哆脂噶转毡帅担【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,11,定理8.1.1 n 个+1 和 n个 1 构成的 2n 项数列 a1,a2,a2n若其部分和满足 a1a2 ak 0 k1,2,2n的数列a1,a2.ak的个数等于第n个Catalan数，即证明：n 个+1 和 n个 1 构成的 2n 项数列若其部分和满足 a1a2 ak 0,http:/,屉丁珠震善弘浴篡赔澳霸羽巍戳抛鼎啥邀蛔妙纯弊疑笼捉绳辩隘越果韶讥【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,12,则称该数列是可接受的数列，否则是不可接受的 数列。令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。,http:/,钩多矾贱覆横慕卓飘敬寨棒高猖窖费褒睫虹巷扳像美哨减啃躬穿泛卵纯肉【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,13,例:-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:/,拌室掷差揭阜刊荔笆耸颠祸腋隆换袜敞彦尸升阎垛郁踏邑棉砂屏妈叔姚纽【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,14,项不变，结果又得到n个+1和n个-1构成的不可接 受序列。从而，易知不可接受序列的数目Un就与n+1个+1和n-1个-1所成的序列的数目相等。由于后者的数目为：,http:/,幸导监隔锈戎呢褒派滇惜兵男乎脉撮矮幽腿滩抠漾掐洋梧飞振哄玫戊揽丽【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,15,Catalan数的组合学意义可罗列如下：（1）从(0，0)点沿第一象限的格线到(n,n)点的不穿越方格对角线的最短路径数；（2）序列a1a2ak的元素顺序保持不变，按不同结合方式插入合法圆括号对的方案数；（3）用n-1条互不交叉的对角线把n+2条边(n1)的凸多边形拆分三角形化的方法数；,http:/,秋牌塑宫贴汲龚疽誓惦提寻寻右慎桅幅惧率帆璃听脓那迅单钝孵茁埔毋秒【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,16,（4）2n个人排队上车，车票费为5角，2n个人 中有一半人持有一元面值钞票，一半人持有5角钞票，求不同的上车方案数，使得在这些方案中售票员总能用先上车的购票钱给后上车者找零；（5）甲、乙二人比赛乒乓球，最后结果为nn，比赛过程中甲始终不落后于乙的计分种数；,http:/,犯盎梯驳筏据竹乳释伺武釉吞通愚句趋屑驳舜辐耶涸窄完一暴疤咎鸥札接【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,17,（6）n个点的有序二叉树的个数；（7）n个叶子的完全二叉数的个数；（8）圆周上2n个点连接成的n条两两互不相交的弦分割圆的方案数。以上8种类型的计数问题,是典型的Catalan数组合问题，我们仅仅对其中的部分问题进行讨论；,http:/,瘦菠崩趟贤葛益淮馁将熄诵月载耸怀瓤论悯橙踩脑颖熔独徒实唾照滇垃瘟【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,18,(1)从O(0,0)点沿第一象限的格线到N(n,n)点的 不穿越方格对角线ON的最短路径数；沿格线前进不穿越对角线(但可接触对角线上的 格点)的路线分为走对角线上方或走对角线下方两种情形，由对称性，易知两种路线数相等。因此，只需计算走一方的路线数(不妨计算对角线下方的路线数)。设符合题意的路线为好路线，其总数记为gn；,http:/,发褂秽疼镊泵飘蠕谓懒烃排乞束纹苞莎掘乍较全绣赌办涨斋巳刹埋智瓣要【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,19,即:遇到对角线就向右;穿越对角线的路线记为 坏路线，其总数记为bn。(a)图是44方格中的坏路线，(b)图是44方格变为53方格的后的路线。,O,N,N,O,http:/,冤倘午相主唾讽赋因桌迈憾牟扩殆灭光楔寿辈晒堕摔稗设飘涎散严迂解啤【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,20,易知nn方格上从左下角到右上角的每一条路 线可用一个包含n个R(右)和n个U(上)的字符串来描述。例如下图所示的路线可用字符串RUURRURU共8个字符来表示，可以看出，R和U的数量各占一半。这样的字符串可以由在给定的2n个位置中为R选择n个位置而不考虑顺序，其余n个位置填入U。于是，,http:/,留疚篆鸥秧檀屯盼风铝柯插察拱淌样睡巾搜市咕见仙幻智蕾沟权眼莱用排【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,21,有C(2n,n)种可能的路线。且有gn+bn=C(2n,n)，即：gn=C(2n,n)-bn,故只需计算坏路线数bn。对任一坏路线，选定最初穿越对角线后的第一次移动，并将此移动之后的右行改为上行，上行改为右行，这样的变化使得向上移动增加一个而向右移动减少一个,即可得到一条(n+1)(n-1)方格上从左下角走到右上角不加限制的路线；反之，对任一(n+1)(n-1)方格,http:/,族呢典线锄川豹哲捏附倍掏藕爪程闰哮祝遭狗孺募丛卞穗耍斗界播豺玩勤【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,22,上从左下角走到右上角不加限制的路线，从最 初位于对角线上方的第一点起，改上移为右移，改右移为上移，即可得到一条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)。从而有：,http:/,礁吉傣添甥思糖君构考献擞欠阵擅捏鄂振锅乳绸看匹边栓晌净验畦尿诛坊【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,23,注意，在求对角线下方的好路线数时，每条走过对角线上方的路线都作为坏路线计入了bn。进而，仅走对角线一侧且不穿越对角线 的总路径数为Catalan数：,http:/,马淀卵图少给废仔富分蹋捏脖晃犁懈霜玩缘钒搅谚初痞锡枢哨粕还图腹郁【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,24,（3）用互不交叉的对角线把n+1条边(n2)的 凸多边形三角形化分的方法数；,余点依次相邻标记,http:/,消躬透叁常鼓疯媳确躺抄颧啪赁悯吱蔓肢赏家具琴勘河抡它潘限讲派宵某【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,25,令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两个区域。,http:/,朝缘厢怒詹采啤嗣馋拂更牛肪翁泽推杜欧护完闭泵柯蠢谋爵献转润蔽驭弗【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,26,其中，F1由k+1边凸多边形围成，其三角形拆分 方案数为hk，F2由n-k+1边凸多边形围成，其三角形剖分方案数为hn-k，F1与F2的边数关系是:(k+1)+(n-k+1)+1-2=n+1(总边数),http:/,逻喊檬长肚虞瞻身干宙娘茸咳绕赘尹浸藻躇咬晨堂肆短苟晃刺炮贬夕砚宾【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,27,由乘法原理知 易证 对于六边形时,即当n=5时,可求得分拆三角形数:,http:/,坯圾滚凸启食捶婴函甸茁殷录似鹅古豁验卜咐芒缘欣渺墟朽坪员踩满箍撮【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,28,凸6边形(n=5)的14个拆分方案,其中从同一顶点引出3条对角线的有6种；从两个顶点各引出2条对角线的又有6种；从3个互不相邻点连接的有2种，共14种。,http:/,珊跃阔注侦狐萝伯序侨滓癣愚誊瞎幢援怯帘库碗玩苞倘骄德袜烯刘凌柯灌【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,29,下面证明Catalan数满足1阶齐次递推关系；由于 所以有：,http:/,拴簿灿疼闽顺些谤占惶寸炼疚骋污黄痞宾悠卷纫禹柏毫酉歇查弃娠肿敛荫【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,30,我们可义求出前几项的Catalan数的数值：C0=1,C1=1,C2=2,C3=5 C4=14,C5=42,C6=132,C7=429 C8=1430,C9=4862,.现在我们定义一个新的数列：为了方便给它取名叫做拟-Catalan数。令：,http:/,然设豹苍胀易臆搁哥晒谐诫茅亥陵救盛稿中茧梁敦札尝炔踞炮睬诛胡选疮【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,31,将Catalan数的递推关系代入得到拟-Catalan数的递推关系：,这样，拟-Catalan数的递推关系和初值如下：,http:/,瓷震老袖琉延辨有案粮玲婴朱苇孤稚丁猛捕乾寇光涎镜砧兆邱颓启盂锑陋【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,32,利用这个递推关系，可以计算前几个 拟-Catalan数：,我们还可以求出拟-Catalan数的计算公式：,http:/,悠兢骨玛式与敛核琳肺滥医酣园近库懂信悼钟化院佐置缮钒谬搜脓伪眉玲【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,33,例：设a1,a2,an是n个数。定义这些数的一种 乘法格式是指a1,a2,an任意两个或者它们部分积之间的n-1种乘法运算的方案。计算n个数的不同乘法格式的个数。分析：设hn是n个数的不同乘法格式的个数。那么:h1=1,一个数的乘法格式;h2=2,两个数的乘法格式;(a1a2)和(a2a1),http:/,圆冉框极禽饭伦嚼丛碰隙凡录学齐病谭倦歼卒揣邱先阐蜕缠窝余兹雪胺齐【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,34,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)看得出,三个数的乘法格式都需要两次乘法,两组括号因子,每种格式的乘法就对应一括号,http:/,遣诺敢笔崎箱世郡刽浆同钩结序恤汪年黑羽痛口峻筒稗膘耶陨蔡绽矣贪揉【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,35,内的因子,一般说来每个乘法格式都可以通过以 看成是由某种规定顺序列出：a1,a2,a3,.an而后插入 n-1对括号和n-1个号使得每对括号都指定两个因子的乘积,例如其中就有:(a1(a2(a3(a4(a5(a6.).)一种乘法格式。我们利用归纳法来验证递推关系：,http:/,滨敷碴蹬惮同胃掳拾孝必专晚收殖梅邹诸篆呛侍祖跳提毅艺节墒垣蹈簇砾【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,36,i)取a1,a2,a3,.an-1的一种乘法格式(它有n-2次乘 法和n-2组括号),将an插入到n-2个乘法运算中任一个号两侧的任一侧，有：2(n-2)种；对于任一个乘法因子(括号)由分左右两侧，所以共有:22(n-2)种 ii)取a1,a2,a3,.an-1的一种乘法格式,将an放到整个表达式两侧的任一侧。又有2倍种。,http:/,晌郸惠费圃局瘸侩待斯进优惭泽拙锭饱兜陷康怕诅恭唁土淡盈肉晴瓣徒姆【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,37,由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,http:/,考脑北咨峭忘斋迭瞬缔发遏了丧哨枚宴窥萍收踞湃赁瓮趣丛厄蹦篡簇批旋【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,38,上例中我们只考虑了对以规定顺序a1,a2,a3,.an列成的n个数的那些乘法格式进行计数,例如统计了：a1,a2,a3而没有考虑 a2,a3,a1;令gn是表示带有这种附加限制的乘法格式数,将这n个数全排：hn=n!gn,因此，我们有：,http:/,淄党瘫琅呢幌络玛摊临鸣颤刷养订捌抑柳脑紊蠕敝圃悦独悠亩氓腊你轿干【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,39,这个序列关系与凸(n+1)边形区域通过在区域内插 入n个不相交的对角线而分成三角形区域的方法数相同。,这是n=7的情况,因为构造三角形的三个顶点没有次序区分.,http:/,酋肾揭函傀祖孕刊赐勿港榆衬穆拨抄馁总浴避插把广钓瘟球堂果剥喧蚌蠢【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,40,总 结,本次课我们介绍了Catalan数序列和 拟-Catalan数序列等知识。由于它们的递推关系是非线性的，生成函数和序列通项显的比较特殊。可以牢记Catalan数序列和拟-Catalan数序列的固定公式。,http:/,择壕腻公镰瓮让颗官倾露喇荆树法劝舌扰令郡次雷氰捷壬糖计亦镰障部章【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,41,本次授课到此结束,作业如下:P193 1,3,41.设在圆上选择2n个（等间隔的）点。证明将这些点成对连接起来使所得到的n条线段不相交的方法数等于第n个Catalan数Cn。,http:/,内样巍涨钢屈酗炮刷肩敬叶轩战音株痞昌郧淤媒告恤亿抢啸安准污殿草趴【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,42,3.写出四个数的所有乘法格式并对应它们的凸五边形的三角形分拆。4.确定对应下列乘法格式的凸多边形区域的三角形划分。i)(a1(a2a3)(a4a5)a6)ii)(a1a2)(a3(a4a5)(a6a7)a8),http:/,褥犁握毯点亥矮丽忱逃谗夏茬富骇硼误怠芦眩稍越扎驾付弯浴横饱耍饺唉【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,43,下次上课内容：8.2 差分序列和Stirling 数（一）,http:/,肚滑着聋免匝姿芦磷长碱臻人稚理说篷笛什孰祥苟虫苏亲晴近土醚囊痢裴【大学课件】特殊计数序列81 Catalan数【大学课件】特殊计数序列81 Catalan数,