组合数学完整(第七章 生成函数)ppt课件

结合数学课件，制作讲座：王继顺，目录(1)，第一章组合数学1.1引用案例1.2组合数学研究对象，内容和方法第二章鸽子嵌套原理2.1鸽子嵌套原理：简单形式2.2鸽子嵌套原理：形式2.3Ramsey定理2.4鸽子嵌套原理和Ramsey定理的应用摘要，本章练习3章阵列和组合3.1两个基本计算原理3.2集合阵列和组合3.3.3多集合第四章二项式系数4.1二项式定理4.2组合恒等式4.3非刚性路径问题4.4牛顿二项式定理4.5多项式定理4.6基本组合数的应用本章摘要练习第5章包含排斥原理5.1排除原理5.2多套的r-组合数5.3电位阵列5.4约束阵列问题5.5限制区域阵列问题摘要问题本章练习，目录，目录(2)，第6章递归关系6.1Fibonacci序列6.2常数系数线性齐次递归关系解决6.3常数系数线性非齐次递归关系解决6.4迭代和推导解决递归关系本章摘要练习7章生成函数7.1生成函数定义和特性7.2多集的r-组合数7.3正整数分割7.4指数生成函数和多集排序问题7.5Catalan数第8章Polya定理8.1替换组中的conjugate类和轨道8.2Polya定理的特殊格式，以及应用本章摘要练习的* * * * * * * * * * * * * * * * * * * * * * * * * *课程摘要，第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)是形式幂级数。序列对应于生成函数。生成函数是序列的另一种表示。有限序列也可以用生成函数表示。可以与二项式定理结合应用。无限序列(A0，a1，an、) (简单地称为an，函数称为序列an的生成函数(具体值，普通父函数)。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)，)的生成函数。解决方案：7.1和定义二项式定理的推理3.10.2，7.1生成函数示例3，4.1生成函数的基本概念，示例，4.1.1生成函数，示例3，证明(1-4x)-1/2是序列(c (0，0)，c (2，1)，c (2n)、)的生成函数。证明：由牛顿二项式定理定义，(1-4x)-1/2是序列(c (0，0)，c (2，1)，c (4，2)，c (2n，n)，)的生成函数。7.1生成函数示例4，7.1生成函数的基本概念，示例，7.1.1生成函数，示例4，查找序列(0，123，234，n (n 1) (n 2)、)的生成函数。7.1指数生成函数概念，7.1生成函数的基本概念，定义7.2，7.1.2指数生成函数，注意：fe(x)也是形式力函数。无限序列(A0，a1，an、) (简单地说，您可以经常合并称为指数生成函数的公式，以指定an)。7.1指数生成函数示例5，7.1生成函数的基本概念，示例，7.1.2指数生成函数，示例5，n设置为整数，序列(p (n，0)，p (n，1)，p (n，n)的指数生成函数fe(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 (2n)、)的指数生成函数fe(x)。，解决方案：定义的7.2和公式P(n，r)=r！C(n，r)，和示例3的结论，例如。7.1指数生成函数示例7，7.1生成函数的基本概念，示例，7.1.2指数生成函数，示例7，序列1， 2， n，的指数生成函数fe(x)。这里是个错误。解决方案：定义7.2，特别是=1时的序列(1，1，1，)的指数生成函数是ex。7.1指数生成函数示例8，7.1生成函数的基本概念，示例，7.1.2指数生成函数，示例8，查找序列(1，14，147，147.(3n 1)、)的指数生成函数。解决方案：7.1生成函数定理1，7.1生成函数的基本概念，定理7.1，7.1.2指数生成函数，f(x)，fe(x)分别设置为序列an的一般，指数生成函数，解决方案：由指数生成函数定义的7.2，自下而上两侧的e-，A(x)、B(x)、C(x)分别是序列an、bn和cn的生成函数时，C(x)=A(x) B(x).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)是序列an的生成函数，则A(x)/(1-x)是序列A0，A0 a1，A0 a1.an、的生成函数。7.2生成函数计算示例2，4.2生成函数的基本运算，示例2，总值。7.2生成函数计算推断1，7.2生成函数的基本运算，6个推断，推断7.2.1:7.2生成函数计算推断2，7.2生成函数的基本运算，6个推断，推断7.2.1:推断7.2.2:7.2生成函数计算推理3，7.2生成函数的基本运算，6个推理，推理7.2.1:推理7.2.2:推理7.2.3:参见本节的示例1。7.2生成函数计算推断4，7.2生成函数的基本运算，6个推断，推断7.2.4:7.2生成函数计算推断5，6，7.2生成函数的基本运算，6个推断，7.2.5:推断7.2.4:推断7.2.6:设置A(x)、B(x)和C(x)分别是序列an、bn和cn的指数生成函数，C(x)=A(x) B.r、)c (x)=a (x) b (x)仅当存在(I=0，1)时，r、)，7.2生成函数定理3，7.2生成函数的基本运算，定理7.3，如果6.5父函数在递归关系中应用，则6.5父函数在解决递归关系中具有重要作用，解决方法和步骤是将序列an的常规父函数标记为f(x)。使用递归关系an的表达式替换父函数的右端，或使用多项式格式算法计算f(x)的方程式g(f(x)=0；解F(x)并将其扩展到幂级数，就可以求出an的基本表达式。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，查找递归关系，注：通常满足上述递归关系的序列(a1，a2，an、)是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: n=将递归关系设置为n位十进制数中出现偶数5的数字bn=n位十进制数中出现奇数5的数字。这是关于序列an和bn的联立关系。序列an，bn的一般父函数分别为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位的十进制整数为910n-2，包含偶数5，其他n-1位包含奇数5。例如：6.5父函数应用示例6，6.5父函数在递归关系中应用，示例6，查找递归关系(Hanoi top)，解决方案：序列设置an的常规父函数为，7.3数组组合概述，在7.3数组组合中应用，生成函数应用非常广泛，本节开始介绍生成函数在特定组合数学中的应用。本节主要讨论了生成函数在计算问题或一些方案方法问题排序中的应用和指数生成函数的应用。考虑三种不同物体a、b、c的选择方法。如果您对选取方法的数目感兴趣，而不是对其他选取方法感兴趣，则a=b=c=1，是，7.3组合应用示例1，7.3组合阵列组合，7.3.1组合，示例1，2个红色球，白色球，1个黄色球，尝试各种组合方案。随机组合，解决方案：r、w、y分别表示红色球、白色球和黄色球。这除了一个球也不取的情况外，(a)一个球的组合数是三个，即分别是红、白、黄、三个。(b)两个球体的组合数为4，即红色、红色、黄色、红色、白色、黄色。(c)三个球体的组合数，即两个红色、一个红色、一个红色、一个红色、一个黄色、一个白色；(d)取四个球体的组合数，即两个红色、黄色和白色。如果I球体的组合数为ai，则系列a0、a1、a2、a3、a4的生成函数为1 3 4 3 1=12(或322=12)。7.3组合应用程序示例2，7.3数组组合应用程序，7.3.1组合应用程序，示例，示例2，n个完全相同的球m标志框，不允许空框，还有几种其他方案？其中nm迭代组合，解决：不允许空框，因此将n个球放在m个标志框中的方案数为an，与序列an对应的生成函数为f(x)。7.3组合应用实例3，7.3组合应用程序，7.3.1组合应用程序，例如，3，一个单位要组织8名男同志，5名女同志，现在要组织由偶数数目的男同志、2名以上女同志组成的组时，要试验几种配置方法。随机组合，解法：an让8个男同志提取n个允许的组合数。男同志的数量必须是偶数，因此与序列an对应的生成函数是f(x)=(1 x)8 (1-x)8/2类似女同志允许的组合数对应的生成函数是g(x)=(1 x)5-()，7.3组合应用示例4，7.3组合，7.3.1在组合中应用，示例4，n证明可以在其他对象上重复选择r个对象的方法的数量为F(n，r)=C(n r-1，r)。证明：指示可以从n个不同对象中重复选择r个对象的方法数。序列ar的生成函数为，7.3组合应用示例5，7.3组合，7.3.1在组合中应用，例如，示例5，n个不同对象中的r个对象可重复选择，但每个对象出现几次的方式数。解决方案：将ar设置为所需的方法数。每个物件出现多次，因此可取消选取物件、选取两次或四次的系数(1x2x4.)。因此，序列ar的生成函数为，7.3组合应用示例6，7.3组合，组合应用7.3.1，示例6，书架上共16本书，其中4是高级数学，3是普通物理，4是数据结构，5是离散数学。r查找选定的方法数。其中r=12。解决方案：这实际上是求reset 4 * M，3*P，4*S，5*D的12个组合的数量。r将ar设置为选择书的方法数。高级数学只能选择4个，一般物理只能选择3个，数据结构只能选择4个，不连续数学只能选择5个，因此序列ar的生成函数是f(x)展开中需要xr的系数的方法数。R=12时，x12的系数为34。即a12=34。7.3组合使用案例7，7.3阵列组合应用程式、4.3.1组合应用程式、范例7、现有2n a、2n b、2n c，从这些项目中选取3n字产生的其他方法的数目。解决方案：此问题实际上是查找reset 2n * A，2n*B，2n*C的3n组合数。以所需方式设置应收款。序列ar的生成函数为，7.3阵列应用程式范例8，7.3阵列组合、4.3.2阵列应用程式、范例8、1，2，3，4四个数字组成的5位数中，需求1不会出现两次以上，但不应出现。2未出现超过1次；可能出现3次，也可能不出现。4出现次数是偶数。请找出满足上述条件的数量。回