软件2010组合数学第五章生成函数三

1,第五章生成函数,5.1生成函数的定义和性质5.2组合数的生成函数5.3指数型生成函数与多重集的排列数5.5分拆数的生成函数5.4Catalan数列与Stirling数列的生成函数,5.5.1有序分拆,定理5.5.1对于n的k有序分拆其k有序分拆数数列的生成函数是这个定理等价于如下分配模型：即把n个相同的球放入k个不同的盒子里，第i个盒的容量为，且使每盒非空的方案数为,2,推论5.5.1若对n的k有序分拆的各分量()没有限制，则其k有序分拆数数列的生成函数是，且,3,5.5.2无序分拆,在3.6节中可知无序分拆和有序分拆的区别在于是否考虑分拆后的各分量的顺序，将n分拆为k个分部（每一分部的大小不受限制）的分拆数等于将n分拆为最大分部为k（分部个数不限）的分拆数，该分拆数也记为,4,定理5.5.2令B(n)表示正整数的所有分拆数，Bk(n)表示n的各分部量都不超过k的分拆数，则它们相应的生成函数分别为(1)(2)(3),5,（1）等于不定方程的非负整数解的个数。因此其分拆数列的生成函数为其中展开式中的系数即为n的最大分项不超过k的分拆个数。,6,（2）根据定理3.6.3知，将n分拆为k个分部（每一分部的大小不受限制）的分拆数等于将n分拆为最大分部为k（分部个数不限）的分拆数，其分拆数相当于求方程的整数解的个数，其生成函数为,7,其中展开式中的系数即为n的最大分项等于k的分拆个数容易证明：，因此若，则，因此当，它们对应的生成函数的系数为零，所以,8,（3）等于不定方程的非负整数解的个数。因此其分拆数列的生成函数为,9,推论5.5.2n的各分部量两两互不相同的分拆数等于n的各分部量是奇数的分拆数。证明n的各分部量两两互不相同的分拆数的生成函数为而显然是n的各分部量是奇数的分拆数数列的生成函数，因此结论成立.,10,例5.5.1用1角、2角、3角的邮票贴出面值6角，求有多少种不同的方案？解这是可重复的无序分拆，相应的生成函数为显然所求为的系数，为7，说明贴出6角面值的方案有7种。具体为：6=1+1+1+1，6=2+2+2，6=2+2+1+1，6=2+1+1+1+1，6=3+3，6=3+2+1，6=3+1+1+1.例5.5.1中，若考虑不同面值贴的顺序，则有多少种方案。此问题留作习题,11,5.4Catalan数列的生成函数,5.4.1Catalan数列的生成函数Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。定义:一个凸n+1边形，通过不相交于n+1边形内部的对角线把n+1边形拆分成的三角形个数，记作hn称为Catalan数.,12,5.4Catalan数列的生成函数,5.4.1Catalan数列的生成函数Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。定义:一个凸n+1边形，通过不相交于n+1边形内部的对角线把n+1边形拆分成的三角形个数，记作hn称为Catalan数.,13,例如五边形有如下五种拆分方案，所以h4=5,14,例5.4.1在一个凸n+1边形中，可以用(n-3)条不在内部相交的对角线将其剖分成(n-2)个三角形，问有多少种不同的分法？,解令表示将一个凸(n+1)边形剖为三角形的方法数，规定。当n=2时，(n+1)边形就是三角形，不需剖分，故当考虑一个凸(n+1)边形，它的顶点分别用表示，如图5.4.1所示。取边，任取顶点将分别与之间连线，得三角形T，三角形T将凸(n+1)边形分成T，R1和R2三部分，其中，R1为(k+1)边形，R2为(n-k+1)边形。因此，R1可以用种方法剖分，R2可以用种方法剖分，所以这正是Catalan数列的通项公式。,15,16,那么如何求,本节用的生成函数来计算。解得,17,利用牛顿二项式定理，有因为，开方应该取负号，故舍去显然一个凸n+1边形中有种不同的剖分方法。,18,一般地，我们把称为第k个Catalan数，用Cn表示，有对于Ck-1和Ck的形式我们并不陌生，例3.4.6的结论是从（0，0）点到（n,n）点的除端点外不接触直线y=x的路径数为,从(0,0)点到（n,n）点的除端点外不穿过直线y=x的路径数为如果用Catalan数表示就是，从（0，0）点到（n,n）点的除端点外不接触直线y=x的路径数为，从（0，0）点到（n,n）点的除端点外不穿过直线y=x的路径数为。,19,Catalan数列的应用,1)不同构的有n条边的种植树(plantedtree)的棵数是Catalan数Cn。2)有n片树叶的有序三度根树的个数是Catalan数Cn-1。3)n个顶点的不同二元树的个数是Catalan数Cn。二元树的定义:空集或一组有限个顶点,满足:有一个特定的点称作“根点”;去掉这个根点后,余下的顶点组成两支子二元树:左子树与右子树。4)从点(0,0)到点(n+1,n+1),除端点外与对角线不相交的(在对角线一侧的)非降路径数是Catalan数Cn。5)2n个均匀分布在一个圆周上,用n条不相交的弦将这2n个点配成n对,则不同的配对方式数是Catalan数Cn。6)n个1和n个0组成一2n位的二进制数,要求从左到右扫描,1的累计数不小于0的累计数,满足这一条件的2n位的二进制数的个数是Cn,20,Catalan数列的应用,7)在两个候选人A和B的投票选举中,共有2n个人投票,最终结果是支持A和B票数都是n票。在开票过程中始终使A的票数不少于B的票数的投票方案数是Catalan数Cn。8)有2n个人在剧院票房门前准备买票入场。每张票价是50美分,而且此时票房售票员没有零钱。这2n个人恰好有n个人有50美分的钱,其余n个人只有1美元的钱。如果在任何时候售票员都能找开零钱的2n个人的排列方法数是Catalan数Cn。9)有2n个高低不同的人,排成两行,使得第一排n个人都比第二排n个人高的排列方法数是Catalan数Cn。10)设a1,a2,an与b1,b2,bn是两个完全不同的序列,则把这两个序列融合在一起组成一个新的序列，使得后一个序列与前一个序列相对应的数始终排在前一个序列数后面的排列的个数是Ca