母函数与递推关系讲义.ppt

第2章 母函数与递推关系;母函数是求解计数问题的一个强有力的工具。 其中心思想是：将一个有限或无限序列 与一个函数项级数 联系起来，使得我们可以通过用解析的方法研究G(x)来得到序列 的一些性质。 最常用的函数项级数： ，;定义2.1 对于序列 ，称函数 为序列 的母函数。 例 序列 的母函数为 例 序列 1,1,…,1,…的母函数为;若我们已知某个序列的母函数，通常可通过对母函数的操作得到该序列的一些重要性质。 例 对等式 两边求导得 再令x=1便得 ;在等式 两边同乘以x，然后再对等式的两边求导得 ;通常序列 与某个问题序列 的计数问题相对应，若已知序列的母函数，则可确定该序列，从而可以解决相应的计数问题。 例2.2 有红球两只，白、黄球各一只，试求有多少种不同的组合方案？ 解 所求组合方案的母函数为;如果只需要求不同的组合方案数，那么可考虑下列母函数 所求组合方案数为：1+3+4+3+1=12。 ;例2.3 某单位有8位男同志，5位女同志。现要组织一个由偶数个男同志和数目不少于两个的女同志组成的小组，试求有多少种组成方式？ 解 所求组成方式数序列的母函数为;所求的组成方式数为 ;几个常见的母函数： (1) (2) ;(3) (4)牛顿二项式公式： ;2.2 母函数的性质;例2.4 已知 ， 求 。 解 ;得 ;2.1 母函数的引入;2.2 母函数的性质;性质2 若 ，则 证 ;性质3 若 ，则 ;性质4 若 收敛， ，则 ;2.2 母函数的性质;性质5 若 ，则 。 证 ;性质6 若 ，则 。 证;性质7 若 ，则 证 ;例 计算下列和式 解 令 ， ， 因为 ，由性质5知 。 又 ，由性质5知 。 ;2.2 母函数的性质; ;1.9 试证n2的正除数的数目是奇数。 证 当n=1时，结论显然正确。 当 时，设n的因子分解为 ， 所以n2的正除数的数目是 ;习题;习题;习题;习题;2.1 2.4 2.6 2.48 ;所谓整数的拆分是把一个正整数n表示成若干个正整数的和，而这些正整数的次序是无关紧要的。 例 5，4+1，3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1是整数5的7个不同的拆分。 在整数的拆分表示 中，常使 不同拆分的总数称为拆分数，通常用 表示n的拆分数。 ;例 求 中项 的系数。 解 项 有以下三种生成方式： ① ：有 种选取方法。 ② ：有 种选取