组合数学课件(第七章-生成函数).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,组合数学课件(第七章-生成函数),组合数学课件(第七章-生成函数)组合数学课件(第七章-生成函数)目录（1）第1章 什么是组合数学,1.1引例,1.2组合数学研究对象、内容和方法,第2章 鸽巢原理,2.1 鸽巢原理：简单形式,2.2 鸽巢原理：加强形式,2.3 Ramsey定理,2.4 鸽巢原理与Ramsey定理的应用,本章小结,习题,第3章 排列与组合,3.1 两个基本的计数原理,3.2 集合的排列与组合,3.3 多重集的排列与组合,本章小结,习题第四章 二项式系数,4.1 二项式定理,4.2组合恒等式,4.3非降路径问题,4.4牛顿二项式定理,4.5多项式定理,4.6 基本组合计数的应用,本章小结,习题,第五章 包含排斥原理,5.1 包含排斥原理,5.2 多重集的r-组合数,5.3错位排列,5.4 有限制条件的排列问题,5.5有禁区的排列问题,本章小结,习题目 录,目录（1）,第1章 什么是组合数学,1.1引例,1.2组合数学研究对象、内容和方法,第2章 鸽巢原理,2.1 鸽巢原理：简单形式,2.2 鸽巢原理：加强形式,2.3 Ramsey定理,2.4 鸽巢原理与Ramsey定理的应用,本章小结,习题,第3章 排列与组合,3.1 两个基本的计数原理,3.2 集合的排列与组合,3.3 多重集的排列与组合,本章小结,习题,第四章 二项式系数,4.1 二项式定理,4.2组合恒等式,4.3非降路径问题,4.4牛顿二项式定理,4.5多项式定理,4.6 基本组合计数的应用,本章小结,习题,第五章 包含排斥原理,5.1 包含排斥原理,5.2 多重集的r-组合数,5.3错位排列,5.4 有限制条件的排列问题,5.5有禁区的排列问题,本章小结,习题,目 录,目录（2）,第六章 递推关系,6.1 Fibonacci数列,6.2 常系数线性齐次递推关系的求解,6.3 常系数线性非齐次递推关系的求解,6.4 用迭代和归纳法求解递推关系,本章小结,习题,第七章 生成函数,7.1生成函数的定义和性质,7.2多重集的r-组合数,7.3正整数的划分,7.4指数生成函数与多重集的排列问题,7.5 Catalan数和Stiring数,本章小结,习题,第八章 Polya定理,8.1置换群中的共轭类与轨道,8.2 Polya定理的特殊形式及其应用,本章小结,习题,*,课程总结,第7章 生成函数,本章重点介绍,生成函数（生成函数、指数生成函数）的基本概念及其在排列组合中的应用,：,生成函数的基本概念,生成函数的基本运算,生成函数在排列、组合中的应用,整数拆分,生成函数在组合恒等式中的应用,第7章 生成函数,7.1生成函数的定义和性质,7.2多重集的r-组合数,7.3正整数的划分,7.4指数生成函数与多重集的排列问题,7.5Catalan数和Stiring,第7章 生成函数,7.1 生成函数概念,4.1 生成函数的基本概念,定义 4.1,4.1.1 生成函数,注：,f,(,x,)是无穷级数，不管其收敛性；,x,为形式变元，,f,(,x,)为形式幂级数；,序列与生成函数一一对应；,生成函数是序列的另一表达形式；,有限序列也可用生成函数表示；,可与二项式定理结合应用。,给定一无穷序列(,a,0,a,1,a,n,)(简记为,a,n,)，称函数,为序列,a,n,的生成函数（发生、普通母函数）。,7.1 生成函数,例,1,7.1 生成函数的基本概念,例 题,7.1.1 生成函数,例1、,求序列(,C,(,n,0),C,(,n,1),C,(,n,2),C,(,n,n,)的生成函数。,解：,由定义7.1及二项式定理的推论有,7.1 生成函数,例,2,7.1 生成函数的基本概念,例 题,7.1.1 生成函数,例2、,求序列(,C,(,n,-1,0),-,C,(,n,1),C,(,n,+1,2),(-1),k,C,(,n,+,k,-1,k,),)的生成函数。,解：,由定义7.1及二项式定理的推论3.10.2有,7.1 生成函数,例,3,4.1 生成函数的基本概念,例 题,4.1.1 生成函数,例3、,证明(1-4,x,),-1/2,是序列(,C,(0,0),C,(2,1),C,(4,2),C,(2,n,n,),)的生成函数。,证明：,由牛顿二项式定理有,由定义知，(1-4,x,),-1/2,是序列(,C,(0,0),C,(2,1),C,(4,2),C,(2,n,n,),)的生成函数。,7.1 生成函数,例,4,7.1 生成函数的基本概念,例 题,7.1.1 生成函数,例4、,求序列(0,1,2,3,2,3,4,n,(,n,+1)(,n,+2),)的生成函数。,7.1 指数生成函数概念,7.1 生成函数的基本概念,定义 7.2,7.1.2 指数生成函数,注：,f,e,(,x,)也是形式幂函数。,经常可结合以下公式运算：,给定一无穷序列(,a,0,a,1,a,n,)（简记为,a,n,），称函数,为序列,a,n,的指数生成函数。,7.1,指数,生成函数,例5,7.1 生成函数的基本概念,例 题,7.1.2 指数生成函数,例5、,设,n,是整数，求序列(,p,(,n,0),p,(,n,1),p,(,n,n,)的指数生成函数,f,e,(,x,)。,解：,由定义7.2及公式,P,(,n,r,)=,r,!,C,(,n,r,),以及例1的结论，有,7.1,指数,生成函数,例6,7.1 生成函数的基本概念,例 题,7.1.2 指数生成函数,例6、,求序列(,p,(0,0),p,(2,1),p,(4,2),p,(2,n,n,),)的指数生成函数,f,e,(,x,)。,解：,由定义7.2及公式,P,(,n,r,)=,r,!,C,(,n,r,)，以及例3的结论，有,7.1,指数,生成函数,例7,7.1 生成函数的基本概念,例 题,7.1.2 指数生成函数,例7、,求序列1,2,n,的指数生成函数,f,e,(,x,)。其中,是实数。,解：,由定义7.2，有,特别地：若,=1，则序列(1,1,1,)的指数生成函数为,e,x,。,7.1,指数,生成函数,例8,7.1 生成函数的基本概念,例 题,7.1.2 指数生成函数,例8、,求序列(1,1,4,1,4,7,1,4,7,(3,n,+1),)的指数生成函数。,解：,由定义7.2和二项式定理，有,7.1 生成函数定理1,7.1 生成函数的基本概念,定理 7.1,7.1.2 指数生成函数,设,f,(,x,)、,f,e,(,x,)分别为序列,a,n,的普通、指数生成函数，则,解：,由指数生成函数的定义7.2，有,将上式两边同乘以,e,-s,并从0到,积分得,由分部积分法有,故,设,A,(,x,),B,(,x,),C,(,x,)分别是序列,a,n,b,n,和,c,n,的生成函数，则,C,(,x,)=,A,(,x,)+,B,(,x,)当且仅当,c,i,=,a,i,+,b,i,(,i,=0,1,r,),C,(,x,)=,A,(,x,),B,(,x,)当且仅当,(,i,=0,1,r,),7.2 生成函数,运算定理2,7.2 生成函数的基本运算,定理 7.2,7.2 生成函数运算,例,1,7.2 生成函数的基本运算,例 题,例1、,设,A,(,x,)是序列,a,n,的生成函数，则,A,(,x,)/(1-,x,)是序列,a,0,a,0,+,a,1,a,0,+,a,1,+,a,n,的生成函数。,7.2 生成函数运算,例,2,4.2 生成函数的基本运算,例 题,例2、,求和 的值。,7.2 生成函数运算推论1,7.2 生成函数的基本运算,六个推论,推论7.2.1：,7.2 生成函数运算推论2,7.2 生成函数的基本运算,六个推论,推论7.2.1：,推论7.2.2：,7.2 生成函数运算推论3,7.2 生成函数的基本运算,六个推论,推论7.2.1：,推论7.2.2：,推论7.2.3：,见本节例1。,7.2 生成函数运算推论4,7.2 生成函数的基本运算,六个推论,推论7.2.4：,7.2 生成函数运算推论5、6,7.2 生成函数的基本运算,六个推论,推论7.2.5：,推论7.2.4：,推论7.2.6：,设,A,(,x,),B,(,x,),C,(,x,)分别是序列,a,n,b,n,和,c,n,的指数生成函数，则,C,(,x,)=,A,(,x,)+,B,(,x,)当且仅当,c,i,=,a,i,+,b,i,(,i,=0,1,r,),C,(,x,)=,A,(,x,),B,(,x,)当且仅当,(,i,=0,1,r,),7.2 生成函数,定理3,7.2 生成函数的基本运算,定理 7.3,6.5 母函数在递推关系中的应用,6.5 母函数在递推关系中的应用,母函数法是求解递推关系的一种重要方法，不仅可以求解常系数线性（非）齐次递推关系，也可以求解非线性、非常系数的递推关系。,求解的,方法和步骤,为：,用,f,(,x,),表示序列,a,n,的普通母函数；,利用递推关系,a,n,的表达式代入母函数的右端，或采用多项式形式算法，转化为关于,f,(,x,),的方程,g,(,f,(,x,)=0,；,解出,f,(,x,),再展开成幂级数，即可求得,a,n,的初等表达式。,6.5 母函数的应用,例1-1,6.5 母函数在递推关系中的应用,例 题,例1、,求递归关系,6.5 母函数的应用,例1-2,6.5 母函数在递推关系中的应用,例 题,例1、,求递归关系,6.5 母函数的应用,例2,6.5 母函数在递推关系中的应用,例 题,例2、,求递归关系,6.5 母函数,的应用,例3-1,6.5 母函数在递推关系中的应用,例 题,例3、,求递归关系,6.5 母函数,的应用,例3-2,6.5 母函数在递推关系中的应用,例 题,例3、,求递归关系,注：,通常，称满足上述递推关系的序列(,a,1,a,2,a,n,)为Catalan序列，称序列中的数,为Catalan数。,这个数很重要，它在各种不同的范围里经常出现，许多有意义的计数问题都与这个数有关。,6.5 母函数,的应用,例4-1,6.5 母函数在递推关系中的应用,例 题,例4、,求递归关系,6.5 母函数,的应用,例4-2,6.5 母函数在递推关系中的应用,例 题,例4、,求递归关系,6.5 母函数,的应用,例5-1,6.5 母函数在递推关系中的应用,例 题,例5、,求,n,位十进制正整数中出现偶数个5的数的个数。,解I：,令,a,n,=,n,位十进制数中出现偶数个5的数的个数,b,n,=,n,位十进制数中出现奇数个5的数的个数,建立递推关系如下,这是关于序列,a,n,和,b,n,的联立关系。,设序列,a,n,b,n,的普通母函数分别为,A,(,x,),B,(,x,)。其中,6.5 母函数,的应用,例5-2,6.5 母函数在递推关系中的应用,例 题,例5、,求,n,位十进制正整数中出现偶数个5的数的个数。,6.5 母函数,的应用,例5-3,6.5 母函数在递推关系中的应用,例 题,例5、,求,n,位十进制正整数中出现偶数个5的数的个数。,解II：,n,-1位的十进制数的全体共 9,10,n,-2,从中去掉含有偶数个5的数，余下的便是,n,-1位中含有奇数个5的数。故有：,6.5 母函数,的应用,例6,6.5 母函数在递推关系中的应用,例 题,例6、,求递归关系（Hanoi塔）,解：,设序列,a,n,的普通母函数为,7.3 排列组合概述,7.3 在排列组合中的应用,生成函数有着极其广泛的应用，从本节开始介绍生成函数在某些组合数学的问题中的应用。,本节介绍生成函数在,组合,中的应用和指数生成函数在,排列,中的应用，主要是计数问题，也有部分方案方法问题。,考虑三个不同的物体,a,、,b,、,c,的选取方法。,如果对选取方法的个数感兴趣，而不是对不同的选取方法感兴趣，则可令,a,=,b,=,c,=1，有,7.3 组合应用,例,1,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例1、,有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。,随机组合,解：,设,r,w,y,分别代表红球，白球和黄球。,由此可见，除一个球也不取的情况外，有：(a)取一个球的组合数为三，即分别取红，白，黄，三种；(b)取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄；(c)取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白；(d)取四个球的组合数为一，即两红一黄一白。,令取,i,个球的组合数为,a,i,，则序列,a,0,a,1,a,2,a,3,a,4,的生成函数为,故共有1+3+4+3+1=12（或3,2,2,=12）种组合方式。,7.3 组合应用,例,2,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例2、,n,个完全一样的球放到,m,个有标志的盒子中，不允许有空盒，问有多少种不同的方案？其中,n,m,重复组合,解：,由于不允许有空盒，令,n,个球放到,m,个有标志的盒子的方案数为,a,n,，序列,a,n,对应的生成函数为,f,(,x,)。则,7.3 组合应用,例,3,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例3、,某单位有8个男同志，5个女同志，现要组织一个由数目为偶数的男同志，和数目不少于2的女同志组成的小组，试求有多少种组成方式。,随机组合,解：,令,a,n,为从8位男同志中抽取出,n,个的允许组合数。由于要男同志的数目必须是偶数，故序列,a,n,对应的生成函数为,f,(,x,)=(1+,x,),8,+(1-,x,),8,/2,类似女同志的允许组合数对应的生成函数为,g,(,x,)=(1+,x,),5,-(1+5,x,),令,c,n,为为符合要求的,n,个人组成的小组的数目，,由乘法法则，,序列,c,n,对应的生成函数为,h,(,x,)=,f,(,x,),g,(,x,)=(1+,x,),8,+(1-,x,),8,(1+,x,),5,-(1+5,x,)/2,故总的组成方式数目,为128,26=3328。,7.3 组合应用,例,4,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例4、,证明从,n,个不同的物体中允许重复地选取,r,个物体的方式数为,F,(,n,r,)=,C,(,n,+,r,-1,r,)。,证明：,设,a,r,表示从,n,个不同的物体中允许重复的选取,r,个物体的方式数。序列,a,r,的生成函数为,7.3 组合应用,例,5,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例5、,求从,n,个不同物体中允许重复地选取,r,个物体，但每个物体出现偶数次的方式数。,解：,设,a,r,为所求的方式数。由于每个物体出现偶数次，故可用因子(1+,x,2,+,x,4,+)示某一物体可以不选，或选取2次，或选取4次，。因此序列,a,r,的生成函数为,7.3 组合应用,例,6,7.3 在排列组合中的应用,7.3.1 在组合中的应用,例 题,例6、,在一个书架上共有16本书，其中4本是高等数学，3本是普通物理，4本是数据结构，5本是离散数学。求从中选取,r,本数的方式数，其中,r,=12。,解：,这实际上是求重集4*,M,3*,P,4*,S,5*,D,的12组合数。,设,a,r,是选取,r,本书的方式数。由于高等数学最多只能选取,4,本，普通物理最多只能选取,3,本，数据结构最多只能选取,4,本，离散数学最多只能选取,5,本，故序列,a,r,的生成函数为,取,f,(,x,)展开式中,x,r,的系数即为所求的方式数。当,r,=12时，,x,12,的系数为34，即,a,12,=34。,7.3 组合应用,例,7,7.3 在排列组合中的应用,4.3.1 在组合中的应用,例 题,例7、,现有2,n,个A，2,n,个B，2,n,个C，求从它们之中选出3,n,个字生成的不同的方式数。,解：,这个问题实际上是求重集2,n,*A,2,n,*B,2,n,*C的3,n,组合数。设,a,r,为所求的方式数。则序列,a,r,的生成函数为,7.3 排列应用,例8,7.3 在排列组合中的应用,4.3.2 在排列中的应用,例 题,例8、,由1,2,3,4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现不超过1次；3出现次数可达3次，也可不出现；4出现次数为偶数。求满足上述条件的数的个数。,容斥原理,解：,设满足条件的,r,位数的个数为,a,r,，序列,a,r,的指数母函数为,由此可见满足条件的5位数,a,r,=215个。,7.3 排列应用,例9,7.3 在排列组合中的应用,4.3.2 在排列中的应用,例 题,例9、,求1,3,5,7,9五个数字组成的,n,位数的个数，要求其中3,7出现的次数为偶数，其他1,5,9出现的次数不加限制,。,解：,设满足上述条件的,r,位数的个数为,a,r,，序列,a,r,的指数母函数为,7.3 排列应用,例10,7.3 在排列组合中的应用,7.3.2 在排列中的应用,例 题,例10、,证明从,n,个不同的物体中允许重复地选取,r,个物体的排列数为,n,r,。,证明：,这个问题实际上是证明重集,B,=,*b,1,*b,2,*b,n,的,r,排列数为,n,r,。设,a,r,为所求的排列数。则序列,a,r,的指数母函数为,7.3 排列应用,例11,4.3 在排列组合中的应用,4.3.2 在排列中的应用,例 题,例11、,用红、白、绿三种颜色给1,n,棋盘中的正方形着色，要求偶数个正方形着红色，而着白色和绿色的正方形个数不加限制，求不同的着色方式数。,证明：,若用,R,W,和,G,分别表示红、白和绿三种颜色，则该问题实际上是求重集,B,=,*R,*W,*G,的,n,排列数，其中要求,R,出现偶数次。设,a,n,为所求的排列数。则序列,a,n,的指数母函数为,7.3 排列应用,例12,7.3 在排列组合中的应用,7.3.2 在排列中的应用,例 题,例12、,在所有的,n,位数中，包含数字3,8,9，但不包含数字0,4的数有多少？,解：,这个问题实际上是求重集,B,=,*1,*2,*3,*5,*6,*7,*8,*9的,n,排列数，其中要求3,8,9至少出现一次，而其他的数不加限制。设符合题意的数有,a,n,个。则序列,a,n,的指数生成函数为,7.3 排列应用,例13,4.3 在排列组合中的应用,4.3.2 在排列中的应用,例 题,例13、,求1,2,3,4,5五个数字组成的,r,位数的个数，要求其中1出现的次数与2出现的次数的和必须是偶数。,解：,设,a,n,为符合题意的个数。由于1出现的次数与2出现的次数的和为偶数，可分为两种情况：,1出现的次数与2出现的次数都为偶数；,1出现的次数与2出现的次数都为奇数。,由加法法则知，序列,a,n,的指数生成函数为,这是生成函数的应用实例之一。整数的拆分就是把整数分成若干个正整数部分，并且不考虑各部分的次序，不同的拆分方法的总数叫,拆分数,P,(,n,)。相当于把,n,个无区别的球放到1,m,n,个无标志的盒子中的方法数。,7.4 整数的拆分概念,7.4 整数的拆分,7.4 整数的拆分定理4,7.4 整数的拆分,定理 7.4,设,a,b,c,.为大于0的整数，则1/(1-,x,a,)(1-,x,b,)(1-,x,c,)的级数展开式中,x,n,的系数等于把正整数,n,拆分为,a,b,c,的和的方法数,P,(,n,)。,证明：,注意到,如果项,x,n,是由,x,3,a,x,b,x,2,c,的乘积所组成的，则,于是，每当,n,可以拆分为,a,b,c,的和时，,x,n,就会出现，这就证明了定理的结论。,7.4 整数的拆分,例1,7.4 整数的拆分,例 题,例1、,若有1克、2克、3克、4克的砝码各一枚，问能称出哪几种重量？有几种可能方案？,证明：,我们采用如下办法来产生拆分数的生成函数：,从右端的生成函数知,能,称出从1克到10克的,重量,，系数便是方案数。,例如右端有2,x,5,项，即称出5克的方案有2,种,，5=2+3=1+4。,同样6=1+2+3=2+4，10=1+2+3+4，即称出6克的方案有2,种,，称出10克的方案有1,种,。,7.4 整数的拆分,例2,7.4 整数的拆分,例2、,求用1分、2分、3分的邮票贴出不同数值的方案数。,解：,因邮票允许重复，故生成函数为,以其中,x,4,为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即,例 题,7.4 整数的拆分,例3,7.4 整数的拆分,例3、,若有1克的砝码3枚，2克的4枚，4克的2枚，问能称出哪些重量？各有几种方案？,解：,上面的1+,x,4,+,x,8,项表示4克砝码只有两枚，或不取，或取一枚，或取2枚。,x,8,项的系数为5，说明称8克的方案有5种：,例 题,7.4 整数的拆分,例4,7.4 整数的拆分,例4、,整数,n,拆分成1,2,3,m,的和，并允许重复，求其生成函数。如若其中,m,至少出现一次，其生成函数如何？,解：,若整数,n,拆分成1,2,3,m,的和，并允许重复，其生成函数为：,若拆分中,m,至少出现一次，其生成函数为：,上式的组合意义：整数,n,拆分成1到,m,的和的拆分数减去拆分成1到,m,-1的和的拆分数，即为至少出现一个,m,的拆分数。,例 题,7.4 整数的拆分,定义,7.4 整数的拆分,定义,7.3,用,P,k,(,n,),表示,n,拆分为,1,2,k,允许重复的方法数。,用,P,o,(,n,),表示,n,拆分为奇整数的方法数。,用,P,d,(,n,),表示,n,拆分为不同整数的方法数。,用,P,t,(,n,),表示,n,拆分为,2,的不同幂（,1,2,4,）的方法数。,7.4 整数的拆分推论,7.4 整数的拆分,四个推论,推论7.4.1：,P,3,(,n,)的普通母函数是1/(1-,x,)(1-,x,2,)(1-,x,3,),推论7.4.2：,P,k,(,n,)的普通母函数是1/(1-,x,)(1-,x,2,)(1-,x,k,),推论7.4.3：,P,(,n,)的普通母函数是1/(1-,x,)(1-,x,2,)(1-,x,3,),推论7.4.4：,P,o,(,n,)的普通母函数是1/(1-,x,)(1-,x,3),(1-,x,5,),7.4 整数的拆分,定理5,7.4 整数的拆分,定理 7.5,设,a,b,c,为不同的正整数，则(1+,x,a,)(1+,x,b,)(1+,x,c,),的级数展开式中,x,n,的系数就是把,n,拆分为,a,b,c,的和，且,a,b,c,最多只出现一次的方法数。,两个推论,推论7.5.1：,P,d,(,n,)的生成函数为(1+,x,)(1+,x,2,)(1+,x,3,)(1+,x,4,),推论7.5.2：,P,t,(,n,)的生成函数是(1+,x,)(1+,x,2,)(1+,x,4,)(1+,x,8,),7.4 整数的拆分,定理6-1,7.4 整数的拆分,定理 7.6,Euler,定理：,P,o,(,n,),=P,d,(,n,),证明：,根据推论7.5.1，,P,d,(,n,)的生成函数为,等式右端正好是,P,o,(,n,)的生成函数（推论7.4.4)。,所以,P,o,(,n,)=,P,d,(,n,)，,即,把,n,拆分成奇整数的和的方法数等于把,n,拆分成不同的整数和的方法数。,7.4 整数的拆分,定理6-2,7.4 整数的拆分,定理 7.6,Euler,定理：,P,o,(,n,),=P,d,(,n,),可以验证,当,n,=7的情况：,7.4 整数的拆分,定理7,7.4 整数的拆分,定理 7.7,Sylvester,定理：对任意正整数,n,有,P,t,(,n,)=1,证明I：,因为任何一个正整数都可惟一地用一二进制数来表示，而一个二进制数又可惟一地表示成2的次幂的和，由此即得结论。,证明II：,因为序列1,1,1,的生成函数为,上式的左端正好是,P,t,(,n,)的生成函数（推论4.5.2),7.4 整数的拆分,例,5,7.4 整数的拆分,例 题,例5、,设有1,2,4,8,16,32克砝码各一枚，试问能称出哪些重量？分别有几种方案？,证明：,从生成函数,f,(,x,)可以得知，用这些砝码可以称出从0克到63克的重量，而且办法都是惟一的。,实际是0到63的数的二进制表示是惟一的。,7.4 整数的拆分,例6,7.4 整数的拆分,例 题,例6、,证明以下恒等式并说明其组合含义。,证明：,因此这个恒等式表明，任何正整数都可以惟一地拆分成形式为,的不同部分。换句话说，任何正整数的十进制表示是惟一的。,7.4 整数的拆分定理8-1,7.4 整数的拆分,定理 4.8,拆分数的估计式,：对任意正整数,n,，有,证明：,由推论4.4.3知，,P,(,n,)的生成函数为：,对上式两端取对数得,由对数的泰勒展开式知,（,A,）,7.4 整数的拆分,定理8-2,7.4 整数的拆分,定理 7.8,拆分数的估计式,：对任意正整数,n,，有,7.4 整数的拆分,定理8-3,7.4 整数的拆分,定理 4.8,拆分数的估计式,：对任意正整数,n,，有,7.4 整数的拆分,定理8-4,7.4 整数的拆分,定理 4.8,拆分数的估计式,：对任意正整数,n,，有,7.4 整数的拆分,定理8-5,7.4 整数的拆分,定理 7.8,拆分数的估计式,：对任意正整数,n,，有,7.5 Ferrers图定义,7.5 Ferrers图,定义 7.4,设,n,的一个拆分为,n,=,a,1,+,a,2,+,a,k,，,其中,a,1,a,2,a,k,1,，,如从上到下依次画,a,i,个格子（点）(,i,=1,2,k,)，称此图称为,Ferrers,图,。,Ferrers图像具有如下性质：,1、每一层至少有一个格子。,2、第一行与第一列互换，第二行于第二列互换，即下图绕虚线轴旋转所得的图仍然是Ferrers图像。,两个Ferrers图像称为一对,共轭的,Ferrers图像。,7.5 Ferrers图,定理9,7.5 Ferrers图,定理 7.9,正整数,n,拆分为,k,项和的拆分数等于数,n,拆分为最大数为,k,的拆分数。,证明：,考虑Ferrers图与其共轭图的关系，即可得证。因整数,n,拆分成,k,个数的和的拆分可用一,k,行的Ferrers图表示，所得的Ferrers图的共轭图最上面一行有,k,个格子。,例如：,24=6+6+5+4+3,5个数，最大数为6,24=5+5+5+4+3+2,6个数，最大数为5,7.5 Ferrers图,定理10、11,7.5 Ferrers图,定理 7.10,正整数,n,拆分为最多不超过,k,个数的和的拆分数等于数,n,拆分为最大数不超过,k,的拆分数。,定理 7.11,正整数,n,拆分为互不相同的若干奇数的和的拆分数等于数,n,拆分成有自共轭的Ferrers图的拆分数。,证明：,设,构造一个Ferrers图像，其第一行，第一列都是,n,1,+1 格，对应于2,n,1,+1，第二行，第二列各,n,2,+1 格，对应于2,n,2,+1。以此类推。由此得到的Ferrers图像是共轭的。反过来也一样。,例如,17=9+5+3,对应为Ferrers图像为,9+5+3=17,7.6 组合恒等式应用,生成函数不仅在计数中有广泛应用，而且在证明（推导）组合恒等式中提供了一种重要方法。其中用二项式定理的，参见,1.4,。,7.6 在组合恒等式中的应用,7.6 组合恒等式应用,例1-1,例 题,例1、,设,p,q,为任意正整数，,证明：,7.6 在组合恒等式中的应用,证明：,由于一个序列是与它的母函数一一对应的，而两个母函数间的乘积关系必然反映为两个母函数对应的序列与其乘积对应的序列之间的关系。为了证明上面的恒等式，只需求出两个序列,对应的母函数，使得其乘积对应的序列为,先求形如序列,的母函数。,在上式中分别令,n,=,p,和,n,=,q,得,7.6 组合恒等式应用,例1-2,例 题,例1、,设,p,q,为任意正整数，,证明：,7.6 在组合恒等式中的应用,7.6 组合恒等式应用,例2,例 题,7.6 在组合恒等式中的应用,例2、,设,p,为非负整数，且,p,n,，,证明：,证明：,由式,将上式两边对,x,微分,p,次得,将上式两边同乘以1/,p,!得,在上式中，令,x,=,-1，有,故恒等式成立。,注意,，若令,x,=,1,又可得到如下的恒等式：,本例中的恒等式还表明序列 与序列 是一对互相,正交,的序列（当,p,n,时），故此恒等式在组合分析中极为有用。,7.6 组合恒等式应用,例3-1,例 题,7.6 在组合恒等式中的应用,例3、,证明：,证明：,由式,于是我们分别得到下列各式,将以上各式两端分别相加，则其右端和中,x,n,的系数正好是要证的恒等式的左端，其左端的和为,如果我们能求出,f,(,x,)展开式中,x,n,的系数是2,2,n,则此例中恒等式得证。,7.6 组合恒等式应用,例3-2,例 题,7.6 在组合恒等式中的应用,例3、,证明：,7.6 组合恒等式应用,例4,例 题,7.6 在组合恒等式中的应用,例4、,证明：,证明：,由二项式定理分别有以下各式,将以上各式两端分别相加，则其右端和中,x,k,的系数正好是要证的恒等式的左端，其左端的和为,7.6 组合恒等式应用,例5,例 题,7.6 在组合恒等式中的应用,例5、,证明：,证明：,由于左端出现形如 的序列，故自然要考虑求序列 的母函数。由7.1节例3知序列,的母函数为 ，即,根据定理7.2，上式中,x,k,的系数是,又由二项式定理有,也就是说，,上式中,x,k,的系数是4,n,第7章 小结,本章小结,本章主要研究了序列的生成函数表示法，生成函数表示法不仅可以使得对数列的代数处理更容易些，而且它对事件的符号描述也是很有用的。在以后的学习中，这是一个重要的概念。,本章重点需要掌握生成函数、指数生成函数的基本概念，及其在排列、组合中的应用，并了解生成函数的一个应用实例整数拆分和Ferrers图。,第7章 习题,习 题,P81,6、7、8、10、11、12、13。,结束,谢 谢,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富知识，,培养逻辑思维能力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培养文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的知识面。,有许多书籍还能培养我们的道德情操，,给我们巨大的精神力量，,鼓舞我们前进,。,