组合数学第二章1母函数.ppt

2 1母函数 母函数方法是一套非常有用的方法 应用极广 这套方法的系统叙述 最早见于Laplace在1812年的名著 概率解析理论 两个色子掷出6点 有多少种选法 我们来看如下的例子 方法的引入 我们也可以从另一角度来看 要使两个色子掷出6点 第一个色子除了6以外的都可选 这有5种选法 一旦第一个选定 第二个色子就只有一种可能的选法按乘法法则有5 1 5种 注意到 出现1 5有两种选法 出现2 4也有两种选法 而出现3 3只有一种选法 这些选法互斥且穷尽了出现6点的一切可能的选法 按加法法则 共有2 2 1 5种不同选法 但碰到用三个或四个色子掷出n点 上述两方法就不胜其烦了 这就需要引进新的方法 这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来 故使两个色子掷出6点的方法数等价于求 母函数的思想很简单 即 把离散数列和幂级数一一对应起来 把离散数列间的相互结合关系对应成为幂级数间的运算关系 最后由幂级数形式来确定离散数列的构造 看下面的例子 2 1母函数 中所有的项包括n个元素a1 a2 an中取两个组合的全体 同理x3项系数包含了从n个元素a1 a2 an中取3个元素组合全体 以此类推 若令a1 a2 an 1 在 2 1 1 式 项系数 中每一个组合有1个贡献 其他各项以此类推 2 1母函数 故有 另一方面 比较等号两端项对应系数 可得一等式 2 1母函数 用类似的方法可得等式 证法如下 比较等式两端的常数项 即得公式 2 1 3 又如等式 令x 1可得 2 1 2 式等号的两端对x求导可得 等式 2 1 5 两端令x 1 得 2 1母函数 用类似的方法还可以得到 2 1母函数 已可见函数 还可以类似地推出一些等式 但通过上面一些例子 的关系时所起的作用 对其他序列也有同样的结果 现引进母函数概念如下 在研究序列 2 1母函数 2 2母函数的性质 一个序列和它的母函数一一对应 给了序列便得知它的母函数 反之 求得母函数序列也随之而定 这种关系颇像数学中的积分变换 特别酷似离散序列的Z变换 如前的例子所示的那样 为了求满足某种递推关系的序列 可把它转换为求对应的母函数G x G x 可能满足一代数方程 或代数方程组 甚至于是微分方程 最后求逆变换 即从已求得的母函数G x 得到序列 an 关键在于要搭起从序列到母函数 从母函数到序列这两座桥 这一节便是以此为目的的 2 2母函数的性质 2 2母函数的性质 性质1 证 2 2母函数的性质 例 已知 则 2 2母函数的性质 性质2 则 若 2 2母函数的性质 证 2 2母函数的性质 例 2 2母函数的性质 性质3 若 则 2 2母函数的性质 2 2母函数的性质 证 例 已知 2 2母函数的性质 类似可得 2 2母函数的性质 性质4 则 2 2母函数的性质 证 2 2母函数的性质 2 2母函数的性质 例 则 性质5 2 2母函数的性质 性质5和性质6的结论是显而易见的 性质6 2 2母函数的性质 性质7 若 则 2 2母函数的性质 证 2 2母函数的性质 已知 例 则 2 2母函数的性质 所谓正整数拆分即把正整数分解成若干整数的和 相当于把n个无区别的球放到n个无标志的盒子 盒子允许空着 也允许放多于一个球 整数拆分成若干整数的和 办法不一 不同拆分法的总数叫做拆分数 拆分可以分为无序拆分和有序拆分 不允许重复的拆分和允许重复的拆分 2 3整数的拆分 2 3 1问题描述 2 3 2问题举例 例1 若有1克 2克 3克 4克的砝码各一枚 问能称出那几种重量 有几种可能方案 从右端的母函数知可称出从1克到10克 系数便是方案数 例如右端有项 即称出5克的方案有2 同样 故称出6克的方案有2 称出10克的方案有1 2 3 2问题举例 例2 求用1分 2分 3分的邮票贴出不同数值的方案数 解 因邮票允许重复 故母函数为 2 3 2问题举例 例3 若有1克砝码3枚 2克砝码4枚 4克砝码2枚的砝码各一枚 问能称出那几种重量 各有几种方案 2 3 2问题举例 解 作目函数 2 3 2问题举例 2 3 2问题举例 2 3 2问题举例 2 3 2问题举例 例6对N进行无序且允许重复的任意剖分 设剖分数为P N 求 P N 的母函数G y 2 3 2问题举例 解这相当于把N无序剖分成1 2 3 n 且允许重复 类似上例 我们有 例7对N进行无序且允许重复的剖分 使得剖分后的正整数都是奇数 求这种剖分方案数 P0 N 的生成函数G0 y 2 3 2问题举例 解 这是把N剖分成1 3 5 且允许重复 类似于上例 我们有 例8对N进行无序剖分 使得剖分后的整数各不相等 求这种剖分方案数 Pd N 的生成函数Gd y 2 3 2问题举例 解 这相当于把N剖分成1 2 3 n 且不允许重复 类似于 b 式 有 例9对N进行无序剖分 使得剖分后的整数都是2的幂 求这种剖分方法数 Pt N 的母函数Gt y 2 3 2问题举例 解 这相当于把N剖分成1 2 4 8 16 但不允许重复 类似于 a 可得 例10 整数n拆分成1 2 3 m的和 并允许重复 若其中m至少出现一次 其母函数如何 若整数n拆分成1 2 3 m的和 并允许重复 由 d 式 其母函数为 2 3 2问题举例 若拆分中m至少出现一次 其母函数则为 2 3 2问题举例 等式 g 的组合意义 即整数n拆分成1到m的和的拆分数减去拆分成1到m 1的和的拆分数 即为至少出现一个m的拆分数 2 3 2问题举例 显然有 从以上例子可以归结如下的结论 2 3 2问题举例 定理1整数剖分成不同数的和的剖分数等于剖分成奇整数的剖分数 2 3 2问题举例 证明 设bN表示N剖分成不同正整数和的剖分数 则序列 bN 的生成函数为 定理2N剖分成其他数之和但重复数不超过2 其剖分数等于它剖分成不被3整除的数的和的剖分数 2 3 2问题举例 证明 N剖分成其他数之和但重复数不超过2的剖分数所构成序列的母函数为 2 3 2问题举例 2 3 2问题举例 定理3N被剖分成其重复度不超过k次的数的和 其剖分数等于被剖分成不被k 1除尽的数的和的剖分数 定理4对一切N 有Pt N 1 2 3 2问题举例 定理5设Pod N N被剖分成奇数个不同正整数的和的剖分数 Pev N N被剖分成偶数个不同正整数的和的剖分数 则 2 3 2问题举例 定理6对一切N 有 例11 若有1 2 4 8 16 32克的砝码各一枚 问能称出那几种重量 有几种可能方案 2 3 2问题举例 从母函数可以得知 用这些砝码可以称出从1克到63克的重量 而且办法都是唯一的 这问题可以推广到证明任一十进制数n 可表示为 而且是唯一的 2 3 2问题举例 2 4Ferrers图像 一个从上而下的n层格子 mi为第i层的格子数 当 即上层的格子数不少于下层的格子数时 称之为Ferrers图像 如图 2 4 1 示 图2 4 1 Ferrers图像具有如下性质 1 每一层至少有一个格子 2 第一行与第一列互换 第二行于第二列互换 即图 2 4 1 绕虚线轴旋转所得的图仍然是Ferrers图像 两个Ferrers图像称为一对共轭的Ferrers图像 2 4Ferrers图像 利用Ferrers图像可得关于整数拆分的十分有趣的结果 a 整数n拆分成k个数的和的拆分数 和数n拆分成最大数为k的拆分数相等 因整数n拆分成k个数的和的拆分可用一k行的图像表示 所得的Ferrers图像的共轭图像最上面一行有k个格子 例如 2 4Ferrers图像 24 6 6 5 4 35个数 最大数为6 24 5 5 5 4 3 26个数 最大数为5 图 2 4 2 2 4Ferrers图像 b 整数n拆分成最多不超过m个数的和的拆分数 和n拆分成最大不超过m的拆分数相等 理由和 a 相类似 因此 拆分成最多不超过m个数的和的拆分数的母函数是 2 4Ferrers图像 拆分成最多不超过m 1个数的和的拆分数的母函数是 所以正好拆分成m个数的和的拆分数的母函数为 2 4Ferrers图像 2 4Ferrers图像 c 整数n拆分成互不相同的若干奇数的和的的拆分数 和n拆分成自共轭的Ferrers图像的拆分数相等 构造一个Ferrers图像 其第一行 第一列都是格 对应于 第二行 第二列各格 对应于 以此类推 由此得到的Ferres图像是共轭的 反过来也一样 2 4Ferrers图像 例如 对应为Ferrers图像为 9 5 3 17图 2 4 3 2 4Ferrers图像 利用Ferrers图像可以证明定理4正整数N剖分成不超过k个数的和的剖分数等于将N k剖分成恰好k个数的剖分数 2 4Ferrers图像