05第二章：特殊计数-格子点2014

11组合论第二章特殊计数2组合论第二章特殊计数§2.1格子点§2.2Catalan数23本讲内容1、折线及其性质2、折线法的应用3、增路4、Catalan数4知识点：折线、增路及其性质折线法的应用Catalan数内容及其掌握程度：掌握折线、增路的概念及其基本性质能熟练利用折线法求解相关组合问题能熟练掌握Catalan数及几种组合模型35本讲内容1、折线及其性质2、折线法的应用3、增路4、Catalan数6(无胜负选举问题)在只有两个候选人的竞选中,候选人甲和候选人乙都得了4张选票,问:在对2×4＝8张选票逐一唱票的过程中,甲的得票数始终不少于乙的得票数的点票记录有多少种可能？引例解若不考虑题中对点票记录的约束条件,则所有的点票记录有(8,4)70C＝47将不满足题意约束条件的点票记录分类计算:第1类：形如:乙*******,有个；(7,3)35C＝第2类：形如:甲乙乙*****,有个；(5,2)10C＝第3类：形如:甲乙甲乙乙***,有个；(3,1)3C＝第4类：形如:甲乙甲甲乙乙乙甲,有1个；第5类：形如:甲乙甲乙甲乙乙甲,有1个；第6类：形如:甲甲乙乙乙***,有个；(3,1)3C＝第7类：形如:甲甲乙甲乙乙乙甲,有1个；第8类：形如:甲甲乙乙甲乙乙甲,有1个；第9类：形如:甲甲甲乙乙乙乙甲,有1个；即不满足题意的点票记录有56个。8因此甲的得票数始终不少于乙的得票数的点票记录有：70-56＝1459引例分析一种点票记录也可用一8元有序组x1,x2,…,x8表示:当第i次唱票时若是甲的选票，则取xi=1，若是乙的选票，则取xi=1，i=1,2,…,8。且满足x1＋x2＋…+xi≥0，对任意i。10xyo(0,0)(8,0)不符合题意的折线图符合题意的折线图唱票过程中,甲的得票数始终不少于乙的得票数x1＋x2＋…+xi≥0611yxo(4,4)(2,1)1、折线——基本概念直角坐标系;格子点：每个分量为整数的点(x,y)节：连接两个格子点,斜率为±1且长为21/2单位的线段。端点12折线由节组成的首尾相连的点节交错序列从第一节开始，其他节均在前一节的右边yxo1、折线——基本概念713yxo(a+n,bn)(a,b0)1.两格点间能用折线相连的充要条件定理一两个格点A(a,b0)和B(a+n,bn)是平面上的两个整点，A和B能用折线相连的充要条件是|bn-b0|≤n且n+bn-b0是偶数。①必要性②充分性（构造）2、折线——性质(a+k,bk)142.折线中不同斜率节的个数定理二连接两个格点A(a,b0)和B(a+n,bn)的折线中斜率为1的节的个数是(n+bn-b0)/2。yxo斜率为-1的节的个数为(n+b0-bn)/22、折线——性质815斜率为1的节的个数是(n+bn-b0)/2.3.两点间折线的个数定理三若两个格点A(a,b0)和B(a+n,bn)有折线相连，则折线个数为001(,(-))12(-)2nnnCnnbbnbb2、折线——性质16并与x轴相交,最后到达点B(a+n,bn)的所有折线的集合记为M,从格点C(a,-b0)出发,到达点B(a+n,bn)的所有折线的集合记为N，则|M|=|N|PyxoC(a,-b0)4.反射原理定理四设b00,bn0,从格点A(a,b0)出发,A(a,b0)B(a+n,bn)2、折线——性质ll’917本讲内容1、折线及其性质2、折线法的应用3、增路4、Catalan数18例1（有胜负选举问题)在只有两个候选人的竞选中，候选人甲得了m张选票，候选人乙得了n张选票，mn.问：在对m+n张选票逐一唱票的过程中,甲的得票数始终领先的点票记录有多少种可能？解：利用折线法计数.一种点票记录可表示为一m+n元序组x1,…,xm+n.当第i次唱票时若是甲,则取xi=1,若是乙,则取xi=1,i=1,…,m+n.且满足x1＋x2＋…+xi0，对任意i.1019Pyxo（1,1）（m+n,m-n）（1,-1）即为连接点(1,1)与点(m+n,m-n)在x轴上方的折线.-1-1---1nmnmnmmnmnmmm符合题意的折线图不符合题意的折线图由反射原理不符合题意的是从(1,-1)到(m+n,m-n)的折线数.20在只有两个候选人的竞选中，候选人甲和候选人乙都得了n张选票，问：在对2n张选票逐一唱票的过程中，甲的得票数始终不少于乙的得票数的点票记录有多少种可能？解：利用折线法计数.例2（无胜负选举问题)1121唱票过程中,甲的得票数始终不少于乙的得票数一种点票记录,对应一条具有下列性质的折线：1.折线自左向右,起点为(0,0),终点为(2n,0)；2.符合题意的折线不到达x轴下方,即yi≥0。(2n,0)(0,0)22xyo(0,0)(2n,0)不符合题意的折线图y=-1(0,-2)Pll’而不符合题意的每条折线l,必定在某处纵坐标为-1.设其左起第一个纵坐标为-1的点是P,则将P左边的折线关于y=-1反射,而成为一条起点为(0,-2),终点为(2n,0)的折线l’.折线l与折线l’一一对应.折线l’中斜率为1的线段有n+1条,斜率为-1的线段有n-1条.这样的折线恰有C(2n,n+1)=C(2n,n-1)条.因此，符合题意的折线数有C(2n,n)-C(2n,n-1)=C(2n,n-1)/n=C(2n,n)/(n+1)；1223222111nnnnTnnnn－称Tn是第n个Catalan数。即在对2n张选票逐一唱票的过程中，甲的得票数始终不少于乙的得票数的点票记录为：48114414T＝特别24设n,k1.用折线法证明组合恒等式证从点(0,0)到点整点P=(n+k+1,n+k1)的折线的集合记为A.由定理三，10-1.-1nrnkrnkkk|A|=C(n+k+1,k).下面用另外一种方法求|A|.例31325在A中有两条特殊的折线Pn+1P0则从点(0,0)到点P的每条折线必路过节er,r=0,1,2,…,n+1.er是连接Pr和(n+k-r+1,-n+k+r1)的节.P=(n+k+1,n+k1)yOxP1P2(n1,n1)(k,k)PrPr=(n+kr,-n+k2+r)r=0,1,2,…,n+1把A分成n+2组这是er2610-1.-1nrnkrnkkk故有恒等式：10-||-1.nrnkrAk从点(0,0)出发到达点Pr=(n+kr,-n+k2+r)折线的个数是C(n+kr,k1)，所以由加法原理得：1427本讲内容1、折线及其性质2、折线法的应用3、增路4、Catalan数28CharlesCatalanEugeneCharlesCatalan1814出生于比利时的Bruges作为数学家他在法国度过了他的大半生。成就体现在链分式、数论与组合1529一、Catalan数1、定义n个1和n个-1构成的2n项序列a1,a2,…,a2n其部分和a1＋a2＋…＋ak≥0(k=1,2,…，2n)的序列个数称为第n个Catalan数,记为Tn.211nnTnn{Tn：n0}称为Catalan数列.30一、Catalan数2、组合模型第n个Catalan数为长为2n的无胜负选举序列的个数。p44n个1和n个-1构成的长为2n,其部分和满足:1.a1＋a2＋…＋ak≥0(k=1,2,…,2n-1)2.a1＋a2＋…＋a2n=0的序列a1,a2,…,a2n的个数。1631不定方程x1+x2+…+x2n=n满足下面条件的整数解的个数:1．x1+x2+…+xii/2，i=1,2,…,2n；2．0xi1，i=1,2,…,2n．一、Catalan数2、组合模型第n个Catalan数为32设(y1,y2,…,y2n)是不定方程x1+x2+…+x2n=n满足约束条件的解。则y1,y2,…,y2n是一个由n个0和n个1组成的(0,1)-序列,且在序列y1,y2,…,y2n的前i项中,0的个数不少于1的个数。至于序列y1,y2,…,y2n,则对应一(1,1)-序列a1,a2,…,a2n：ai=1若yi=0，ai=1若yi=1．1733满足下述条件的由n个0和n个1组成的(0,1)-序列的个数。条件：前i项中，1的个数不少于0的个数。一、Catalan数2、组合模型第n个Catalan数为34一、Catalan数3、递推关系1214211nnnnTTnnn＝1(1)!(42)!nnnTnnT记tn=n!Tn-1，称tn为拟－Catalan数。且有1(46)(2)nntntn1835Newton二项式定理的特殊形式⑴令y=1，当α=n时⑵令y=1，x换为-x，当α=-n时01nnkknxxk0011(1)nkkkkknnkxxxkk二、Catalan数和二项式定理36二、Catalan数和二项式定理(14x)1/2的展开式中xn+1的系数是2Tn，这里Tn第n个Catalan数．12=01(1-4)(1)(4)2nnnxxn1212-21(1-4)12-1nnnxxnn1937(14x)1/2的展开式中xn+1的系数是1212-21(1-4)12-1nnnxxnn111(-1)421nnn111(-1)135(2-1)(-1)42(1)!nnnnnn12(2)!-(1)!(2462)nnnn22(2)!2--(1)!!1-2nnnnnnnT111111(-1)(-2)(-)2222(-1)4(1)!nnnn38n位不同数相乘a1·a2·…·an，不允许改变数之间的相对位置，仅依据结合的先后顺序，问共有多少种不同的乘法？思考题例如n＝4时有5种：(((a1a2)a3)a4)((a1(a2a3))a4)(a1((a2a3)a4))(a1(a2(a3a4)))((a1a2)(a3a4))2039动物园的门票票价1元,每人限购买1张,现有2n位小朋友在排队买票,其中n位小朋友持的是面值为1元的纸币,另外n位小朋友持的是面值为2元的纸币。售票员没有准备零钱，2n位小朋友排队,不同的排队方法共有(2n)！,问其中有多少种排队方法使售票员能找开零钱？思考题40小结：1、折线及其性质2、折线法的应用3、增路4、Catalan数2141课后练习P642.3;2.4;2.5;2.6；2.8;2.9*;2.10*;42本讲内容1、折线及其性质2、折线法的应用3、增路4、Catalan数2243yxo(2,1)(3,1)(3,2)1、格子点直角坐标系中格子点：每个分量为整数的点(x,y)边：单位线段端点：边、节44通道：点边交错序列路：格点相异增路——最短性任一边不能位于它前面各边的下方yxo2、增路2345()!!!nmnmnnm定理2.1从（0,0）到（n,m）的增路个数是从（0,0）到（n,m）的增路P上包含n个x和m个y;由n个x和m个y组成的序列可构成唯一一条增路.yxo3、增路的计数4601krnrnkrk利用格子点证明组合恒等式证法一（1）是重集{n+1•x，k•y}的全排列数1nkk（2）是重集{n•x，r•y}的全排列数nrrn+1个x，k个yxy…yxyxyyyn个x，r个yn+1k-r个ynrr例12447证法二利用增路.（1）（0,0）到（n+1,k）的增路数是1