组合数学课件-chapter

2023/1/8计算机科学与技术学院1第五章生成函数5.1生成函数的定义5.2生成函数的性质5.3组合数的生成函数5.4排列数的指数型生成函数5.5Catalan数列与Stirling数列的生成函数5.6分配问题5.7分拆数的生成函数2023/1/8计算机科学与技术学院2生成函数又称母函数或发生函数，可求解组合计数问题。基本计数原理和容斥原理已解决了部分排列组合问题。但对于元素的部分排列和组合，用基本计数原理和容斥原理这些方法是比较麻烦的，若改用生成函数方法，问题将显得容易多了。在求解递推关系的解、整数分拆以及证明组合恒等式时，生成函数是组合数学中的基本而重要的手段和方法，它是连接离散数学与连续数学的桥梁，组合数学中的问题能借助于生成函数的方法、原理，获得统一的处理和解决方式。生成函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转换为多项式或幂级数之间的运算。几类特殊的生成函数，包括组合数序列、排列数序列、分拆数序列、组合分配数序列以及排列分配数序列的生成函数，以及Catalan数和第一类Stirling数的生成函数。2023/1/8计算机科学与技术学院3生成函数的定义2023/1/8计算机科学与技术学院4生成函数的定义2023/1/8计算机科学与技术学院5生成函数的定义2023/1/8计算机科学与技术学院6生成函数的定义2023/1/8计算机科学与技术学院7生成函数的定义2023/1/8计算机科学与技术学院8生成函数的定义2023/1/8计算机科学与技术学院9生成函数的定义2023/1/8计算机科学与技术学院10生成函数的定义2023/1/8计算机科学与技术学院11生成函数的定义i=20j=0i=14j=1i=8j=2i=2j=32023/1/8计算机科学与技术学院12生成函数的性质2023/1/8计算机科学与技术学院13生成函数的性质2023/1/8计算机科学与技术学院14生成函数的性质2023/1/8计算机科学与技术学院15生成函数的性质2023/1/8计算机科学与技术学院16生成函数的性质2023/1/8计算机科学与技术学院17生成函数的性质2023/1/8计算机科学与技术学院18生成函数的性质积分满足结合律2023/1/8计算机科学与技术学院19生成函数的性质形式幂级数的数乘形式幂级数的加法形式幂级数的乘法2023/1/8计算机科学与技术学院20生成函数的性质2023/1/8计算机科学与技术学院21生成函数的性质证明:(1)

(2)

(3)

k=0?牛顿二项式定理2023/1/8计算机科学与技术学院22(4)

设

则

所以

(5)

生成函数的性质2023/1/8计算机科学与技术学院23(6)

设

则

所以

故

生成函数的性质2023/1/8计算机科学与技术学院24(7)

(8)

即二项式展开式,

生成函数的性质既可以将其看作定义，也可以利用x=0的指数函数的Taylor展开式证明此结果。2023/1/8计算机科学与技术学院25生成函数的性质(9)

前面学到的牛顿二项式定理知,有

故

用n+1替换n2023/1/8计算机科学与技术学院26生成函数的性质2023/1/8计算机科学与技术学院27生成函数的性质2023/1/8计算机科学与技术学院28生成函数的性质k=n-1k=n-22023/1/8计算机科学与技术学院29作业5.1

2023/1/8计算机科学与技术学院30组合数的生成函数2023/1/8计算机科学与技术学院31组合数的生成函数选取的元素个数为k2023/1/8计算机科学与技术学院32组合数的生成函数2023/1/8计算机科学与技术学院33组合数的生成函数2023/1/8计算机科学与技术学院34组合数的生成函数连续的整数区间任意的整数集合2023/1/8计算机科学与技术学院35组合数的生成函数2023/1/8计算机科学与技术学院36组合数的生成函数2023/1/8计算机科学与技术学院37组合数的生成函数n=10n=6n=5n=4n=1n=0注意符号！2023/1/8计算机科学与技术学院38组合数的生成函数二项式定理2023/1/8计算机科学与技术学院39组合数的生成函数2023/1/8计算机科学与技术学院40组合数的生成函数利用推论5.3.12023/1/8计算机科学与技术学院41组合数的生成函数每一项xk的系数是取k个元素的组合数，所以总的组合方式数实际上是求多项式中所有项的系数之和。只需令x=1，G(1)即为总的组合方式数2023/1/8计算机科学与技术学院42组合数的生成函数2023/1/8计算机科学与技术学院43组合数的生成函数2023/1/8计算机科学与技术学院44组合数的生成函数将y2看作一个变量r=152023/1/8计算机科学与技术学院45一般说来，不定方程的非负整数解的个数设为ar，考虑下面的函数组合数的生成函数2023/1/8计算机科学与技术学院46组合数的生成函数2023/1/8计算机科学与技术学院47组合数的生成函数2023/1/8计算机科学与技术学院48组合数的生成函数2023/1/8计算机科学与技术学院49组合数的生成函数2023/1/8计算机科学与技术学院50组合数的生成函数2023/1/8计算机科学与技术学院51所以有用生成函数的方法也可以求解不定方程的整数解的个数。组合数的生成函数2023/1/8计算机科学与技术学院52例:求方程x1+x2+x3=1的整数解的个数，其中这个方程与原方程的解的个数相等。设解的个数为a13，则{ar}的生成函数是组合数的生成函数所以有2023/1/8计算机科学与技术学院53排列数的指数型生成函数2023/1/8计算机科学与技术学院54排列数的指数型生成函数2023/1/8计算机科学与技术学院55排列数的指数型生成函数2023/1/8计算机科学与技术学院56排列数的指数型生成函数2023/1/8计算机科学与技术学院57排列数的指数型生成函数2023/1/8计算机科学与技术学院58排列数的指数型生成函数2023/1/8计算机科学与技术学院59排列数的指数型生成函数2023/1/8计算机科学与技术学院60排列数的指数型生成函数2023/1/8计算机科学与技术学院61排列数的指数型生成函数2023/1/8计算机科学与技术学院62排列数的指数型生成函数2023/1/8计算机科学与技术学院63排列数的指数型生成函数2023/1/8计算机科学与技术学院64(令n=k+l)排列数的指数型生成函数2023/1/8计算机科学与技术学院65比较上式两边xn的系数得排列数的指数型生成函数2023/1/8计算机科学与技术学院66排列数的指数型生成函数2023/1/8计算机科学与技术学院67排列数的指数型生成函数2023/1/8计算机科学与技术学院68排列数的指数型生成函数2023/1/8计算机科学与技术学院69排列数的指数型生成函数2023/1/8计算机科学与技术学院70排列数的指数型生成函数2023/1/8计算机科学与技术学院71排列数的指数型生成函数2023/1/8计算机科学与技术学院72排列数的指数型生成函数2023/1/8计算机科学与技术学院73排列数的指数型生成函数2023/1/8计算机科学与技术学院74排列数的指数型生成函数2023/1/8计算机科学与技术学院75排列数的指数型生成函数2023/1/8计算机科学与技术学院76所以有排列数的指数型生成函数2023/1/8计算机科学与技术学院77比较上式两边xn的系数得所以有排列数的指数型生成函数2023/1/8计算机科学与技术学院78排列数的指数型生成函数2023/1/8计算机科学与技术学院79排列数的指数型生成函数2023/1/8计算机科学与技术学院80得排列数的指数型生成函数2023/1/8计算机科学与技术学院81作业5.2

5.6

2023/1/8计算机科学与技术学院82Catalan数列的生成函数TR2R1A1An+1Ak+2AkAk+12023/1/8计算机科学与技术学院83Catalan数列的生成函数TR2R1A1An+1Ak+2AkAk+12023/1/8计算机科学与技术学院84Catalan数列的生成函数2023/1/8计算机科学与技术学院85Catalan数列的生成函数2023/1/8计算机科学与技术学院86Catalan数列的生成函数2023/1/8计算机科学与技术学院87Catalan数列的生成函数在n=5时可得h(5)=C(8,4)/5=14，具体的划分方案如图所示。2023/1/8计算机科学与技术学院88Catalan数列的生成函数2023/1/8计算机科学与技术学院89Catalan数列的生成函数2023/1/8计算机科学与技术学院90Catalan数列的生成函数2023/1/8计算机科学与技术学院912023/1/8计算机科学与技术学院92Stirling数列的生成函数2023/1/8计算机科学与技术学院93Stirling数列的生成函数2023/1/8计算机科学与技术学院94Stirling数列的生成函数2023/1/8计算机科学与技术学院95Stirling数列的生成函数2023/1/8计算机科学与技术学院96Stirling数列的生成函数定义定义2023/1/8计算机科学与技术学院97Stirling数列的生成函数2023/1/8计算机科学与技术学院982023/1/8计算机科学与技术学院99Stirling数列的生成函数2023/1/8计算机科学与技术学院100Stirling数列的生成函数2023/1/8计算机科学与技术学院101Stirling数列的生成函数2023/1/8计算机科学与技术学院102Stirling数列的生成函数2023/1/8计算机科学与技术学院103Stirling数列的生成函数2023/1/8计算机科学与技术学院104Stirling数列的生成函数2023/1/8计算机科学与技术学院105Stirling数列的生成函数=02023/1/8计算机科学与技术学院106Stirling数列的生成函数2023/1/8计算机科学与技术学院107Stirling数列的生成函数2023/1/8计算机科学与技术学院108Stirling数列的生成函数小结2023/1/8计算机科学与技术学院109分配问题2023/1/8计算机科学与技术学院110盒子不相同的分配问题2023/1/8计算机科学与技术学院111盒子不相同的分配问题2023/1/8计算机科学与技术学院112盒子不相同的分配问题2023/1/8计算机科学与技术学院113盒子不相同的分配问题用k替换m+n再用n替换k2023/1/8计算机科学与技术学院114盒子不相同的分配问题用n替换2k2023/1/8计算机科学与技术学院115盒子不相同的分配问题用n替换2k+m2023/1/8计算机科学与技术学院116盒子不相同的分配问题2023/1/8计算机科学与技术学院117盒子不相同的分配问题2023/1/8计算机科学与技术学院118盒子不相同的分配问题2023/1/8计算机科学与技术学院119盒子不相同的分配问题2023/1/8计算机科学与技术学院120盒子不相同的分配问题2023/1/8计算机科学与技术学院121盒子不相同的分配问题2023/1/8计算机科学与技术学院122盒子不相同的分配问题2023/1/8计算机科学与技术学院123盒子不相同的分配问题2023/1/8计算机科学与技术学院124盒子相同的分配问题2023/1/8计算机科学与技术学院125盒子相同的分配问题2023/1/8计算机科学与技术学院126盒子相同的分配问题2023/1/8计算机科学与技术学院127盒子相同的分配问题2023/1/8计算机科学与技术学院128分拆数的生成函数——有序分拆2023/1/8计算机科学与技术学院129有序分拆用n替换n+k2023/1/8计算机科学与技术学院130不定方程的非负整数解的个数设为ar，则生成函数为无序分拆2023/1/8计算机科学与技术学院131无序分拆2023/1/8计算机科学与技术学院132无序分拆2023/1/8计算机科学与技术学院133无序分拆无常数项2023/1/8计算机科学与技术学院134无序分拆2023/1/8计算机科学与技术学院135无序分拆2023/1/8计算机科学与技术学院136盒子相同的分配问题2023/1/8计算机科学与技术学院137的整数解问题。令Bn表示n的分拆方案数，则{Bn}的生成函数是将n无序分拆成正整数1,2,…,k,且不允许重复.这个问题对应于不定方程无序分拆2023/1/8计算机科学与技术学院138无序分拆2023/1/8计算机科学与技术学院139

例对N进行无序分拆，使得剖分后的正整数都是2的幂，求这种分拆方法数{Bt（N）}的生成函数Gt（y）.解这是当于把N分拆成1，2，4，8，…，但不允许重复，有无序分拆2023/1/8计算机科学与技术学院140

这个定理说明任何一个十进制的正整数N可以唯一地表成一个二进制数,而这正是计算机能够工作的基础.(对N进行无序分拆，使得分拆后的整数都是2的幂，而且yN的系数为1）无序分拆2023/1/8计算机科学与技术学院141无序分拆2023/1/8计算机科学与技术学院142无序分拆2023/1/8计算机科学与技术学院143P(N):对N无序且重复剖分无序分拆2023/1/8计算机科学与技术学院144无序分拆2023/1/8计算机科学与技术学院145无序分拆2023/1/8计算机科学与技术学院146把以上的结果代入前式得由于所以有无序分拆2023/1/8计算机科学与技术学院147即这个定理给出了关于P(N)的一个上界.无序分拆2023/1/8计算机科学与技术学院148无序分拆2023/1/8计算机科学与技术学院149无序分拆2023/1/8计算机科学与技术学院150无序分拆2023/1/8计算机科学与技术学院151两个多项式的商表示的函数.有理函数的定义:假定分子与分母之间没有公因