《组合数学课件(第七章-生成函数)ppt.ppt》由会员分享，可在线阅读，更多相关《组合数学课件(第七章-生成函数)ppt.ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程组合数学课件制作讲授：王继顺病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程目录（目录（1）第第1章章 什么是组合数学什么是组合数学1.1引例引例1.2组合数学研究对象、内容和方法组合数学研究对象、内容和方法第第2章章 鸽巢原理鸽巢原理2.1 鸽巢原理：简单形式鸽巢原理：简单形式2.2 鸽巢原理：加强形式鸽巢原理：加强形式2.3 Ramsey定理定理2.4 鸽巢原理与鸽巢原理与Ramsey定理的应用定理的应用本章小结 习题第
2、第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有禁区
3、的排列问题有禁区的排列问题本章小结 习题目目 录录病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程目录（目录（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置换群中的共
4、轭类与轨道8.2 Polya定理的特殊形式及其应用本章小结 习题*课程总结课程总结病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程本章重点介绍本章重点介绍生成函数（生成函数、指数生成函生成函数（生成函数、指数生成函数）的基本概念及其在排列组合中的应用数）的基本概念及其在排列组合中的应用：生成函数的基本概念生成函数的基本概念 生成函数的基本运算生成函数的基本运算 生成函数在排列、组合中的应用生成函数在排列、组合中的应用 整数拆分整数拆分 生成函数在组合恒等式中的应用生成函数在组合恒等式中的应用病原体侵入机体，消弱机体防御机能，破坏机体
5、内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第7章章 生成函数生成函数7.1生成函数的定义和性质生成函数的定义和性质7.2多重集的多重集的r-组合数组合数7.3正整数的划分正整数的划分7.4指数生成函数与多重集的排列问题指数生成函数与多重集的排列问题7.5Catalan数和数和Stiring病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.1.1 生成函数生成函数 注：注：f(x)是无穷级数，不管其收敛性；是无穷级数，不管其收敛性；x为形式变元，为形式变元，f(x)为形式幂级数为形式幂级数；序列与生成函数
6、一一对应；序列与生成函数一一对应；生成函数是序列的另一表达形式；生成函数是序列的另一表达形式；有限序列也可用生成函数表示；有限序列也可用生成函数表示；可与二项式定理结合应用可与二项式定理结合应用。给定一无穷序列给定一无穷序列(a0,a1,an,)(简记为简记为an)，称，称函数函数 为序列为序列an的生成函数（发生、普的生成函数（发生、普通母函数）通母函数）。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.1 生成函数生成函数 例例1、求求序序列列(C(n,0),C(n,1),C(n,2),C(n,n)的生成函数。的生成函数
7、。解：解：由定义由定义7.1及二项式定理的推论有及二项式定理的推论有 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.1 生成函数生成函数 例例2、求序列求序列(C(n-1,0),-C(n,1),C(n+1,2),(-1)kC(n+k-1,k),)的生成函数。的生成函数。解：解：由定义由定义7.1及二项式定理的推论及二项式定理的推论3.10.2有有 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.1.1 生成函数生成函数 例例3、证证明明(1-4x)-1/2是
8、是序序列列(C(0,0),C(2,1),C(4,2),C(2n,n),)的生成函数。的生成函数。证明：证明：由牛顿二项式定理有由牛顿二项式定理有 由定义知，由定义知，(1-4x)-1/2是序列是序列(C(0,0),C(2,1),C(4,2),C(2n,n),)的生成函数。的生成函数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.1 生成函数生成函数 例例4、求序列求序列(0,123,234,n(n+1)(n+2),)的生成函数。的生成函数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，
9、引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函数 注：注：fe(x)也是形式幂函数。也是形式幂函数。经常可结合以下公式运算：经常可结合以下公式运算：给定一无穷序列给定一无穷序列(a0,a1,an,)（简记为（简记为an），称），称函数函数 为序列为序列an的指数生成函数。的指数生成函数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函数 例例5、设设n是整数，求序列是整数，求序列(p(n,0),p(n,1),p(n,n)的指数生成函数的指数生成函数fe(x)。解：解：由定义由定义7.2
10、及公式及公式P(n,r)=r!C(n,r),以及例以及例1的的结论，有结论，有 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函数 例例6、求序列求序列(p(0,0),p(2,1),p(4,2),p(2n,n),)的指数生成函数的指数生成函数fe(x)。解：解：由定义由定义7.2及公式及公式P(n,r)=r!C(n,r)，以及例，以及例3的结论，有的结论，有病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函
11、数 例例7、求求序序列列1,2,n,的的指指数数生成函数生成函数fe(x)。其中。其中是实数。是实数。解：解：由定义由定义7.2，有，有 特别地：若特别地：若 =1，则序列，则序列(1,1,1,)的指数生成函数为的指数生成函数为ex。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函数 例例8、求序列求序列(1,14,147,147(3n+1),)的指数生成函数。的指数生成函数。解：解：由定义由定义7.2和二项式定理，有和二项式定理，有病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在
12、一定部位生长繁殖，引起不同程度的病理生理过程7.1.2 指数生成函数指数生成函数 解：解：由指数生成函数的定义由指数生成函数的定义7.2，有，有 将上式两边同乘以将上式两边同乘以e-s并从并从0到到 积分得积分得由分部积分法有由分部积分法有故故病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、设设A(x)是序列是序列an的生成函数，则的生成函数，则A(x)/(1-x)是序列是序列a0,a0+a1,a0+a1+an,的生
13、成函数。的生成函数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例2、求和求和 的值。的值。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.2.1：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.2.1：推论推论7.2.2：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.2.1：推论推论7.2.2：推论推论7
14、.2.3：见本节例见本节例1。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.2.4：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.2.5：推论推论7.2.4：推论推论7.2.6：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的
15、相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、求递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、求递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例2、求递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例3、求
16、递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例3、求递归关系求递归关系 注：注：通常，称满足上述递推关系的序列通常，称满足上述递推关系的序列(a1,a2,an,)为为Catalan序列，称序列中的数序列，称序列中的数 为为Catalan数。数。这个数很重要，它在各种不同的范围里经常出现，许多有意这个数很重要，它在各种不同的范围里经常出现，许多有意义的计数问题都与这个数有关。义的计数问题都与这个数有关。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过
17、程例例4、求递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例4、求递归关系求递归关系 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例5、求求n位位十十进进制制正正整整数数中中出出现现偶偶数数个个5的数的个数。的数的个数。解解I：令令an=n位十进制数中出现偶数个位十进制数中出现偶数个5的数的个数的数的个数 bn=n位十进制数中出现奇数个位十进制数中出现奇数个5的数的个数的数的个数建立递推关系如下建立递推关系如下 这是关于序列这是关于序列an和
18、和 bn的联立关系。的联立关系。设序列设序列an,bn的普通母函数分别为的普通母函数分别为A(x),B(x)。其中。其中病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例5、求求n位位十十进进制制正正整整数数中中出出现现偶偶数数个个5的数的个数。的数的个数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例5、求求n位位十十进进制制正正整整数数中中出出现现偶偶数数个个5的数的个数。的数的个数。解解II：n-1位的十进制数的全体共位的十进制数的全体共 9 10n-2,从
19、中去掉含有偶数个从中去掉含有偶数个5的数，余下的便是的数，余下的便是n-1位中含有奇数个位中含有奇数个5的数。故有：的数。故有：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例6、求递归关系（求递归关系（Hanoi塔）塔）解：解：设序列设序列an的普通母函数为的普通母函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用
20、 例例1、有有红红球球两两只只，白白球球、黄黄球球各各一一只只，试试求求有多少种不同的组合方案。有多少种不同的组合方案。随机组合随机组合 解：解：设设r,w,y分别代表红球，白球和黄球。分别代表红球，白球和黄球。由此可见，除一个球也不取的情况外，有：由此可见，除一个球也不取的情况外，有：(a)取一个球的组合取一个球的组合数为三，即分别取红，白，黄，三种；数为三，即分别取红，白，黄，三种；(b)取两个球的组合数为取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄；四，即两个红的，一红一黄，一红一白，一白一黄；(c)取三个取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白；球的组
21、合数为三，即两红一黄，两红一白，一红一黄一白；(d)取四个球的组合数为一，即两红一黄一白。取四个球的组合数为一，即两红一黄一白。令取令取i个球的组合数为个球的组合数为ai，则序列，则序列a0,a1,a2,a3,a4的生成函数为的生成函数为故共有故共有1+3+4+3+1=12（或（或322=12）种组合方式。）种组合方式。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用 例例2、n个个完完全全一一样样的的球球放放到到m个个有有标标志志的的盒盒子子中中，不不允允许许有有空空盒盒，问问有有多多少少种
22、种不不同同的的方方案？其中案？其中nm 重复组合重复组合 解：解：由于不允许有空盒，令由于不允许有空盒，令n个球放到个球放到m个有标志的盒子的方案个有标志的盒子的方案数为数为an，序列，序列an对应的生成函数为对应的生成函数为f(x)。则。则病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用 例例3、某某单单位位有有8个个男男同同志志，5个个女女同同志志，现现要要组组织织一一个个由由数数目目为为偶偶数数的的男男同同志志，和和数数目目不不少少于于2的的女女同同志志组组成成的的小小组组，试试求求有有
23、多多少少种种组组成成方式。方式。随机组合随机组合 解：解：令令an为从为从8位男同志中抽取出位男同志中抽取出n个的允许组合数。由于要男个的允许组合数。由于要男同志的数目必须是偶数，故序列同志的数目必须是偶数，故序列an对应的生成函数为对应的生成函数为f(x)=(1+x)8+(1-x)8/2类似女同志的允许组合数对应的生成函数为类似女同志的允许组合数对应的生成函数为g(x)=(1+x)5-(1+5x)令令cn为为符合要求的为为符合要求的n个人组成的小组的数目，个人组成的小组的数目，由乘法法则，由乘法法则，序序列列cn对应的生成函数为对应的生成函数为h(x)=f(x)g(x)=(1+x)8+(1-
24、x)8(1+x)5-(1+5x)/2故总的组成方式数目故总的组成方式数目为为12826=3328。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用 例例4、证证明明从从n个个不不同同的的物物体体中中允允许许重重复复 地地 选选 取取 r个个 物物 体体 的的 方方 式式 数数 为为F(n,r)=C(n+r-1,r)。证明：证明：设设ar表示从表示从n个不同的物体中允许重复的选取个不同的物体中允许重复的选取r个物体的个物体的方式数。序列方式数。序列ar的生成函数为的生成函数为病原体侵入机体，消弱
25、机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用 例例5、求求从从n个个不不同同物物体体中中允允许许重重复复地地选选取取r个个物体，但每个物体出现偶数次的方式数。物体，但每个物体出现偶数次的方式数。解：解：设设ar为所求的方式数。由于每个物体出现偶数次，故可用为所求的方式数。由于每个物体出现偶数次，故可用因子因子(1+x2+x4+)示某一物体可以不选，或选取示某一物体可以不选，或选取2次，或选取次，或选取4次，次，。因此序列。因此序列ar的生成函数为的生成函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相
26、对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.1 在组合中的应用在组合中的应用 例例6、在在一一个个书书架架上上共共有有16本本书书，其其中中4本本是是高高等等数数学学，3本本是是普普通通物物理理，4本本是是数数据据结结构构，5本本是是离离散散数数学学。求求从从中中选选取取r本数的方式数，其中本数的方式数，其中r=12。解：解：这实际上是求重集这实际上是求重集4*M,3*P,4*S,5*D的的12组合数。组合数。设设ar是选取是选取r本书的方式数。由于高等数学最多只能选取本书的方式数。由于高等数学最多只能选取4本，本，普通物理最多只能选取普通物理最多只能选取3本，数据结构最
27、多只能选取本，数据结构最多只能选取4本，离散本，离散数学最多只能选取数学最多只能选取5本，故序列本，故序列ar的生成函数为的生成函数为取取f(x)展开式中展开式中xr的系数即为所求的方式数。当的系数即为所求的方式数。当r=12时，时，x12的系的系数为数为34，即，即 a12=34。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.3.1 在组合中的应用在组合中的应用 例例7、现现有有2n个个A，2n个个B，2n个个C，求求从从它它们们之中选出之中选出3n个字生成的不同的方式数。个字生成的不同的方式数。解：解：这个问题实际上是求重
28、集这个问题实际上是求重集2n*A,2n*B,2n*C的的3n组合数。组合数。设设ar为所求的方式数。则序列为所求的方式数。则序列ar的生成函数为的生成函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.3.2 在排列中的应用在排列中的应用 例例8、由由1,2,3,4四四个个数数字字组组成成的的五五位位数数中中，要要求求数数1出出现现次次数数不不超超过过2次次，但但不不能能不不出出现现；2出出现现不不超超过过1次次；3出出现现次次数数可可达达3次次，也也可可不不出出现现；4出出现现次次数数为为偶偶数数。求求满满足足上上述述条条件
29、的数的个数。件的数的个数。容斥原理容斥原理 解：解：设满足条件的设满足条件的r位数的个数为位数的个数为ar，序列，序列ar的指数母函数为的指数母函数为由此可见满足条件的由此可见满足条件的5位数位数ar=215个。个。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.3.2 在排列中的应用在排列中的应用 例例9、求求1,3,5,7,9五五个个数数字字组组成成的的n位位数数的的个个数数，要要求求其其中中3,7出出现现的的次次数数为为偶偶数数，其其他他1,5,9出现的次数不加限制出现的次数不加限制。解：解：设满足上述条件的设满足上述条件
30、的r位数的个数为位数的个数为ar，序列，序列ar的指数母函数为的指数母函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.2 在排列中的应用在排列中的应用 例例10、证证明明从从n个个不不同同的的物物体体中中允允许许重重复复地地选取选取r个物体的排列数为个物体的排列数为nr。证明：证明：这个问题实际上是证明重集这个问题实际上是证明重集B=*b1,*b2,*bn的的r排列数为排列数为nr。设。设ar为所求的排列数。则序列为所求的排列数。则序列ar的指数母函数的指数母函数为为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相
31、对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.3.2 在排列中的应用在排列中的应用 例例11、用用红红、白白、绿绿三三种种颜颜色色给给1n棋棋盘盘中中的的正正方方形形着着色色，要要求求偶偶数数个个正正方方形形着着红红色色，而而着着白白色色和和绿绿色色的的正正方方形形个个数数不不加加限限制，求不同的着色方式数。制，求不同的着色方式数。证明：证明：若用若用R,W和和G分别表示红、白和绿三种颜色，则该问题实分别表示红、白和绿三种颜色，则该问题实际上是求重集际上是求重集B=*R,*W,*G的的n排列数，其中要求排列数，其中要求R出现出现偶数次。设偶数次。设an为所求的排列数。则序列为所
32、求的排列数。则序列an的指数母函数为的指数母函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程7.3.2 在排列中的应用在排列中的应用 例例12、在在所所有有的的n位位数数中中，包包含含数数字字3,8,9，但不包含数字但不包含数字0,4的数有多少？的数有多少？解：解：这个问题实际上是求重集这个问题实际上是求重集B=*1,*2,*3,*5,*6,*7,*8,*9的的n排列数，其中要排列数，其中要求求3,8,9至少出现一次，而其他的数不加限制。设符合题意的数至少出现一次，而其他的数不加限制。设符合题意的数有有an个。则序列个。则序列
33、an的指数生成函数为的指数生成函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4.3.2 在排列中的应用在排列中的应用 例例13、求求1,2,3,4,5五五个个数数字字组组成成的的r位位数数的的个个数数，要要求求其其中中1出出现现的的次次数数与与2出出现现的次数的和必须是偶数。的次数的和必须是偶数。解：解：设设an为符合题意的个数。由于为符合题意的个数。由于1出现的次数与出现的次数与2出现的次数出现的次数的和为偶数，可分为两种情况：的和为偶数，可分为两种情况：1出现的次数与出现的次数与2出现的次数都为偶数；出现的次数都为偶数；
34、1出现的次数与出现的次数与2出现的次数都为奇数。出现的次数都为奇数。由加法法则知，序列由加法法则知，序列an的指数生成函数为的指数生成函数为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程证明：证明：注意到注意到如果项如果项xn是由是由x3a,xb,x2c,的乘积所组成的的乘积所组成的，则，则于是，每当于是，每当n可以拆分为可以拆分为a,b,c的和时，的和时，xn就会出现，这就证明了就会出现，这就证明了定理的结论。定理的结论
35、。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、若若有有1克克、2克克、3克克、4克克的的砝砝码码各各一一枚枚，问问能能称称出出哪哪几几种种重重量量？有有几种可能方案？几种可能方案？证明：证明：我们采用如下办法来产生拆分数的生成函数：我们采用如下办法来产生拆分数的生成函数：从右端的生成函数知从右端的生成函数知能能称出从称出从1克到克到10克的克的重量重量，系数便是方案，系数便是方案数。数。例如右端有例如右端有2x5 项，即称出项，即称出5克的方案有克的方案有2种种，5=2+3=1+4。同样同样6=1+2+3=2+4，10=
36、1+2+3+4，即称出，即称出6克的方案有克的方案有2种种，称出，称出10克的方案有克的方案有1种种。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例2、求求用用1分分、2分分、3分分的的邮邮票票贴贴出不同数值的方案数。出不同数值的方案数。解：解：因邮票允许重复，故生成函数为因邮票允许重复，故生成函数为以其中以其中x4为例，其系数为为例，其系数为4，即，即4拆分成拆分成1、2、3之和的拆分数为之和的拆分数为4，即，即病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例
37、3、若若有有1克克的的砝砝码码3枚枚，2克克的的4枚枚，4克克的的2枚枚，问问能能称称出出哪哪些些重重量量？各各有有几几种种方方案？案？解：解：上面的上面的1+x4+x8项表示项表示4克砝码只有两枚，或不取，或取一枚，或克砝码只有两枚，或不取，或取一枚，或取取2枚。枚。x8项的系数为项的系数为5，说明称，说明称8克的方案有克的方案有5种种：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例4、整整数数n拆拆分分成成1,2,3,m的的和和，并并允允许许重重复复，求求其其生生成成函函数数。如如若若其其中中m至至少少出现一次，其生成函数
38、如何？出现一次，其生成函数如何？解：解：若整数若整数n拆分成拆分成1,2,3,m的和，并允许重复，其生成函数为：的和，并允许重复，其生成函数为：若拆分中若拆分中m至少出现一次，其生成函数为：至少出现一次，其生成函数为：上式的组合意义：整数上式的组合意义：整数n拆分成拆分成1到到m的和的拆分数减去拆分成的和的拆分数减去拆分成1到到m-1的和的拆分数，即为至少出现一个的和的拆分数，即为至少出现一个m的拆分数。的拆分数。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部
39、位生长繁殖，引起不同程度的病理生理过程推论推论7.4.1：P3(n)的普通母函数是的普通母函数是1/(1-x)(1-x2)(1-x3)推论推论7.4.2：Pk(n)的普通母函数是的普通母函数是1/(1-x)(1-x2)(1-xk)推论推论7.4.3：P(n)的普通母函数是的普通母函数是1/(1-x)(1-x2)(1-x3)推论推论7.4.4：Po(n)的普通母函数是的普通母函数是1/(1-x)(1-x3)(1-x5)病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程推论推论7.5.1：Pd(n)的生成函数为的生成函数为(1+x)(1+
40、x2)(1+x3)(1+x4)推论推论7.5.2：Pt(n)的生成函数是的生成函数是(1+x)(1+x2)(1+x4)(1+x8)病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程证明：证明：根据推论根据推论7.5.1，Pd(n)的生成函数为的生成函数为等式右端正好是等式右端正好是Po(n)的生成函数（推论的生成函数（推论7.4.4)。所以所以Po(n)=Pd(n)，即即把把n拆分成奇整数的和的方法数等于把拆分成奇整数的和的方法数等于把n拆拆分成不同的整数和的方法数。分成不同的整数和的方法数。病原体侵入机体，消弱机体防御机能，破坏机体
41、内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程可以验证可以验证当当n=7的情况：的情况：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程证明证明I：因为任何一个正整数都可惟一地用一二进制数来表示，因为任何一个正整数都可惟一地用一二进制数来表示，而一个二进制数又可惟一地表示成而一个二进制数又可惟一地表示成2的次幂的和，由此即得结论。的次幂的和，由此即得结论。证明证明II：因为序列因为序列1,1,1,的生成函数为的生成函数为上式的左端正好是上式的左端正好是Pt(n)的生成函数（推论的生成函数（推论4.5.2),病原
42、体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例5、设设有有1,2,4,8,16,32克克砝砝码码各各一一枚枚，试试问问能能称称出出哪哪些些重重量量？分分别别有有几几种种方方案案？证明：证明：从生成函数从生成函数f(x)可以得知，用这些砝码可以称出从可以得知，用这些砝码可以称出从0克到克到63克的重克的重量，而且办法都是惟一的。量，而且办法都是惟一的。实际是实际是0到到63的数的二进制表示是惟一的。的数的二进制表示是惟一的。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程
43、例例6、证明以下恒等式并说明其组合含义。证明以下恒等式并说明其组合含义。证明：证明：因此这个恒等式表明，任何正整数都可以惟一地拆分成形式为因此这个恒等式表明，任何正整数都可以惟一地拆分成形式为的不同部分。换句话说，任何正整数的十进制表示是惟一的。的不同部分。换句话说，任何正整数的十进制表示是惟一的。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程证明：证明：由推论由推论4.4.3知，知，P(n)的生成函数为：的生成函数为：对上式两端取对数得对上式两端取对数得由对数的泰勒展开式知由对数的泰勒展开式知 （A）病原体侵入机体，消弱机体防御
44、机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程设设n的一个拆分为的一个拆分为n=a1+a2+ak，其中其中 a1a2ak1，
45、如从上到下依次画如从上到下依次画ai个格个格子（点）子（点）(i=1,2,k)，称此图称为，称此图称为Ferrers图图。Ferrers图像具有如下性质：图像具有如下性质：1、每一层至少有一个格子。、每一层至少有一个格子。2、第一行与第一列互换，第二行于第二列互换，、第一行与第一列互换，第二行于第二列互换，即下图，即下图绕虚线轴旋转所得的图仍然是绕虚线轴旋转所得的图仍然是Ferrers图像。图像。两个两个Ferrers图像称为一对图像称为一对共轭的共轭的Ferrers图像。图像。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程证明：
46、证明：考虑考虑Ferrers图与其共轭图的关系，即可得证。因整数图与其共轭图的关系，即可得证。因整数n拆分成拆分成k个数的和的拆分可用一个数的和的拆分可用一k行的行的Ferrers图表示，所得的图表示，所得的Ferrers图的共轭图最上面一行有图的共轭图最上面一行有k个格子。个格子。例如：例如：24=6+6+5+4+3 5个数，最大数为个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为个数，最大数为5病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程正整数正整数n拆分为最多不超过拆分为最多不超过k个数的和的拆分个数的和的
47、拆分数等于数数等于数n拆分为最大数不超过拆分为最大数不超过k的拆分数。的拆分数。证明：证明：设设 构造一个构造一个Ferrers图像，其第一行，第一列都是图像，其第一行，第一列都是n1+1 格，对应格，对应于于2n1+1，第二行，第二列各，第二行，第二列各n2+1 格，对应于格，对应于2n2+1。以此类。以此类推。由此得到的推。由此得到的Ferrers图像是共轭的。反过来也一样。图像是共轭的。反过来也一样。例如例如 17=9+5+3,对应为对应为Ferrers图像为图像为病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程病原体侵入机体
48、，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、设设p,q为任意正整数，为任意正整数，证明：证明：证明：证明：由于一个序列是与它的母函数一一对应的，而两个母函数由于一个序列是与它的母函数一一对应的，而两个母函数间的乘积关系必然反映为两个母函数对应的序列与其乘积对应的间的乘积关系必然反映为两个母函数对应的序列与其乘积对应的序列之间的关系。为了证明上面的恒等式，只需求出两个序列序列之间的关系。为了证明上面的恒等式，只需求出两个序列 对应的母函数，使得其乘积对应的序列为对应的母函数，使得其乘积对应的序列为先求形如序列先求形如序列 的母函数。的母
49、函数。在上式中分别令在上式中分别令n=p和和n=q得得病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例1、设设p,q为任意正整数，为任意正整数，证明：证明：病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例2、设设p为非负整数，且为非负整数，且pn，证明：证明：证明：证明：由式由式将上式两边对将上式两边对x微分微分p次得次得将上式两边同乘以将上式两边同乘以1/p!得得 在上式中，令在上式中，令x=-1，有，有 故恒等式成立。故恒等式成立。注意注意，若令，若令x=1,
50、又可得到如下的恒等式：又可得到如下的恒等式：本例中的恒等式还表明序列本例中的恒等式还表明序列 与序列与序列 是一对互相是一对互相正交正交的序列（当的序列（当pn时），故此恒等式在组合分析中极为有用。时），故此恒等式在组合分析中极为有用。病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例3、证明：证明：证明：证明：由式由式于是我们分别得到下列各式于是我们分别得到下列各式将以上各式两端分别相加，则其右端和中将以上各式两端分别相加，则其右端和中xn的系数正好是要证的恒的系数正好是要证的恒等式的左端，其左端的和为等式的左端，其左端的和为