组合数学第八章

第八章特殊计数序列,刘贵全gqliu,8.1Catalan数,Catalan数列C1,C2,Cn,其中Cn=C(2n,n)/(n+1),(n=0,1,2,),一个凸n边形，通过不相交于其内部的对角线将其划分成三角形区域，不同划分的方法数用hn表示。则hn=C(2n-2,n-1)/n=Cn-1,定理8.1.1n个+1与n个-1组成的2n个数的数列a1,a2,a2n中，其部分和满足a1+a2+ak0,(k=1,2,2n)(8.2)的数列的个数为第n个Catalan数Cn=C(2n,n)/(n+1),8.1Catalan数,8.1Catalan数,证n个+1和n个-1组成的数列的总数为C(2n,n)=(2n)!/(n!n!)设其中满足条件(8.2)的数列个数为An，不满足(8.2)的数列个数为Un，则An+Un=C(2n,n)。求Un：考虑任一由n个+1和n个-1组成的不满足(8.2)的数列，一定存在一个最小的k，使得：a1+a2+ak0.故,a1+a2+ak-1=0,ak=-1可知k是奇数。将a1，a2,ak进行-1/1互换，即ai=-ai,i=1,2,k,则得到一个由n+1个+1和n-1个-1组成的数列。,反之，任给一个由n+1个+1和n-1个-1组成的数列，可得到一个由n个+1和n个-1组成的不满足(8.2)的数列。故Un=(2n)!/(n+1)!(n-1)!)An=(2n)!/(n!n!)-Un=C(2n,n)/(n+1),8.1Catalan数,例2n个人排队进入电影院，门票是5元。2n个人中有n个人有5元零钞，n个人只有10元整钞。售票员开始时没有准备零钱。有多少种方法安排2n个人的排队顺序，使得每个持10元整钞的人都有零钱找？答案：如果只用钱数来区别人，不管人与人之间的其它区别，则方法数为Cn。如果把每个人都看成是有区别的，则方法数为n!n!Cn=n!n!C(2n,n)/(n+1)=(2n)!/(n+1),8.1Catalan数,例某律师住在城市的西南角，每天到城市的东北角上班时需向北走n个街区，向东走n个街区(右图是n=4时的地图)如果她不想穿越对角线，有几种可能的路线？答案：2Cn=2C(2n,n)/(n+1),家,1,1,1,1,0,0,0,0,8.1Catalan数,东,北,例考虑n个数a1,a2,an的乘积，依据乘法的结合律，不改变a1,a2,an的顺序，只用括号表示成对的乘积。试问有几种不同的乘法方案?答案：在n个数的乘积式中插入n-1对括号的不同方案数为Cn-1=C(2n-2,n-1)/n,8.1Catalan数,8.1Catalan数,以n=4为例，C3=h4=5,下面建立这5个乘法式中不同的乘法顺序和一个5边形划分成三角形的不同方案的一一对应关系。,8.1Catalan数,运算用二叉树表示，两片叶子分别表ab乘数和被乘数，分支点为运算符，如图,a,b,ab,8.1Catalan数,8.1Catalan数,8.1Catalan数,因为Cn=C(2n,n)/(n+1)=(2n)!/(n!n!(n+1)Cn-1=C(2n-2,n-1)/n=(2n-2)!/(n-1)!(n-1)!n)Cn/Cn-1=(4n-2)/(n+1)故Catalan数列满足一阶齐次递推关系（不是常系数）：Cn=(4n-2)/(n+1)Cn-1,(n1)C1=1,8.1Catalan数,如果可以改变a1,a2,an的排列顺序，则乘法方案数为n!Cn-1=(n-1)!C(2n-2,n-1)定义伪Catalan数列C1*,C2*,Cn*,其中Cn*=n!Cn-1=(n-1)!C(2n-2,n-1)Cn*满足递推关系：Cn*=n!Cn-1=n!(4n-6)Cn-2/n=(4n-6)(n-1)!Cn-2=(4n-6)Cn-1*(n2)C1*=1,8.1Catalan数,8.2Stirling数,只准备讨论其中的第二类Stirling数,至于第一类的Stirling数只准备给出它的定义和递推关系.,定义:,8.2Stirling数,称为第一类Stirling数,显然有,8.2Stirling数,定义:n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用表示,称为第二类Stirling数.例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种:,8.2Stirling数,其中r表红球,y表黄球,b表蓝球,w表白球,8.2Stirling数,定理:第二类Stirling数有下列性质:,证明:公式(a),(b),(e)是显然的,只证(c),(d).,8.2Stirling数,(c)设有n个不相同的球从中取出球,其余的个球,每个都有与同盒，或不与同盒两种选择.但必须排除一种情况,即全体与同盒,因这时另一盒将是空盒.故实际上只有种方案,即,8.2Stirling数,(d)n个球放到个盒子里,不允许有一空盒,故必有一盒有两个球,从n个有区别的球中取2个共有种组合方案.,定理:第二类Stirling数满足下面的递推关系,证明:设有n个有区别的球从中取一个球设为.把n个球放到m个盒子无一空盒的方案的全体可分为两类。（a）独占一盒，其方案数显然为（b）不独占一盒，这相当于先将剩下的个球放到m个盒子，不允许空盒，共,8.2Stirling数,共有种不同方案，然后将球放进其中一盒，从乘法法则得不独占一盒的方案数应为,根据加法法则有,上述证明过程也就给出构造所有方案的办法。例如今将,8.2Stirling数,红、黄、蓝、白、绿五个球放到无区别的两个盒子里。,故共有15种不同的方案。先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用r，y，b，w分别表示红，黄，蓝，白球，绿球用g表示，故得表,8.2Stirling数,8.2Stirling数,8.2Stirling数,n个球放到m个盒子里，依球和盒子是否有区别？是否允许空盒？共有种状态。其方案计数分别列于下表。,n个球有区别，m个盒子有区别，有空盒时方案计数为,n个球有区别，m个盒子有区别，无空盒时方案计数为,8.2Stirling数,n个球有区别，m个盒子无区别，有空盒时方案计数为,8.2Stirling数,n个球有区别，m个盒子无区别，无空盒时方案计数为,n个球无区别，m个盒子有区别，有空盒时方案计数为,8.2Stirling数,n个球无区别，m个盒子有区别，无空盒时方案计数为,8.2Stirling数,n个球无区别，m个盒子无区别，有空盒时方案计数为,的项系数。,8.2Stirling数,n个球无区别，m个盒子无区别，无空盒时方案计数为,的项系数。,8.3整数拆分,例:整数n拆分成1，2，3，m的和，并允许重复，求其母函数。如若其中m至少出现一次，其母函数如何？,若整数n拆分成1，2，3，m的和，并允许重复，其母函数为：,8.3整数拆分,若拆分中m至少出现一次，其母函数为：,8.3整数拆分,8.3整数拆分,显然有,上式的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。,一个从上而下的n层格子，为第层的格子数，当，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图示。,8.3整数拆分,8.3整数拆分,Ferrers图像具有如下性质：1.每一层至少有一个格子。2.第一行与第一列互换，第二行于第二列互换，即上图绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers图像称为一对共轭的Ferrers图像。,8.3整数拆分,利用Ferrers图像可得关于整数拆分的十分有趣的结果。,(a)整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的若干个数之和的拆分数相等。,因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如：,24=6+6+5+4+35个数，最大数为6,24=5+5+5+4+3+26个数，最大数为5,8.3整数拆分,8.3整数拆分,(b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。,理由和(a)相类似。,因此，拆分成最多不超过m个数的和的拆分数的母函数是,8.3整数拆分,拆分成最多不超过m-1个数的和的拆分数的母函数是,所以正好拆分成m个数的和的拆分数的母函数为,8.3整数拆分,所以正好拆分成m个数的和的