2 1 母函数与指数型母函数ppt课件

第二章母函数与递推关系 2 1母函数与指数型母函数2 2递推关系与Fibonacci数列2 3线性常系数递推关系2 4非线性递推关系举例2 5应用举例 2 1母函数与指数型母函数 母函数母函数的性质整数的拆分Ferrers图像指数型母函数 1 母函数 母函数方法是一套非常有用的方法 应用极广 这套方法的系统叙述 最早见于Laplace在1812年的名著 概率解析理论 我们来看如下的例子 两个骰子掷出6点 有多少种选法 注意到 出现1 5有两种选法 出现2 4也有两种选法 而出现3 3只有一种选法 按加法法则 共有2 2 1 5种不同选法 或者 第一个骰子除了6以外都可选 有5种选法 一旦第一个选定 第二个骰子就只有一种可能的选法 按乘法法则有5 1 5种 但碰到用三个或四个骰子掷出n点 上述两方法就不胜其烦了 设想把骰子出现的点数1 2 6和t t2 t6对应起来 则每个骰子可能出现的点数与 t t2 t6 中t的各次幂一一对应 若有两个骰子 则 其中t6的系数为5 显然来自于 这表明 掷出6点的方法一一对应于得到t6的方法 故使两个骰子掷出n点的方法数等价于求 中tn的系数 这个函数f t 称为母函数 母函数方法的基本思想 把离散数列和幂级数一一对应起来 把离散数列间的相互结合关系对应成为幂级数间的运算关系 最后由幂级数形式来确定离散数列的构造 再来看下面的例子 若令a1 a2 an 1 则有 这就是二项式展开定理 比较等号两端项对应系数 可以得到恒等式 比较等式两端的常数项 可以得到恒等式 中令x 1可得 又如在等式 两端对x求导可得 再令x 1可得 类似还可以得到 还可以类似地推出一些等式 但通过上面一些例子已可见函数 1 x n在研究序列C n 0 C n 1 C n n 的关系时所起的作用 定义 对于序列a0 a1 a2 函数 称为序列a0 a1 a2 的母函数 例如函数 1 x n就是序列C n 0 C n 1 C n n 的母函数 如若已知序列 则对应的母函数可根据定义给出 反之 如果已经求出序列的母函数G x 则该序列也随之确定 例1下图是一逻辑回路 符号D是一延迟装置 即在时间t输入一个信号给延迟装置D 在t 1时刻D将输出同样的信号 符号 表示加法装置 若在t 0 1 2 时刻的输入为u0 u1 u2 求在这些时刻的输出v0 v1 v2 显然 一般的有 若信号输入的序列u0 u1 的母函数为U x 输出的信号序列v0 v1 的母函数为V x 则 其中 被装置的特性所确定 称为该装置的传递函数 设r w y分别代表红球 白球 黄球 例2有红球两个 白球 黄球各一个 试求有多少种不同的组合方案 1 取一个球的组合数为3 即分别取红 白 黄 2 取两个球的组合数为4 即两个红的 一红一黄 一红一白 一白一黄 3 取三个球的组合数为3 即两红一黄 两红一白 一红一黄一白 4 取四个球的组合数为1 即两红一黄一白 共有1 3 4 3 1 12种组合方式 令取r的组合数为 则序列 的母函数为 令an为从8位男同志中抽取出n个的允许组合数 由于要男同志的数目必须是偶数 故 例3某单位有8个男同志 5个女同志 现要组织一个由数目为偶数的男同志和数目不少于2的女同志组成的小组 试求有多少种组成方式 因此序列a1 a2 a8对应的母函数为 类似可得女同志的允许组合数对应的母函数为 其中xk的系数就是组成符合要求的k人小组的数目 2 母函数的性质 设序列ak bk对应的母函数分别为A x B x 则下面的两个性质显然成立 1 A x B x 当且仅当ak bk 2 若A x B x c0 c1x c2x2 则ck ak bk 性质1 若则B x xlA x 证 则 例4已知 性质2 若bk ak l 则 则 例5已知 性质3 若bk a0 ak 则 1 x x2 xk 则 例6已知 性质4 若bk ak ak 1 则 1 x x2 性质5 若bk kak 则 性质6 若bk ak 1 k 则 则 例7已知 性质7 若ck a0bk a1bk 1 ak 1b1 akb0 则 1 x x2 令 例8已知 则 3 整数的拆分 所谓正整数拆分即把正整数分解成若干正整数的和 相当于把n个无区别的球放到n个无标志的盒子 盒子允许空着 也允许放多于一个球 整数拆分成若干整数的和 办法不一 不同拆分法的总数叫做拆分数 拆分可以分为无序拆分和有序拆分 不允许重复的拆分和允许重复的拆分 例9若有1克 2克 3克 4克的砝码各一枚 问能称出那几种重量 有几种可能方案 从右端的母函数知可称出从1克到10克 系数便是方案数 例如右端有2x5项 即称出5克的方案有2种 5 2 3 1 4 类似的 称出6克的方案也有2种 6 2 4 1 2 3 例10求用1分 2分 3分的邮票贴出不同数值的方案数 以x4为例 其系数为4 即4拆分成1 2 3之和的允许重复的拆分数为4 4 1 1 1 1 1 1 2 1 3 2 2 注意邮票允许重复 因此母函数为 例11若有1克砝码3枚 2克砝码4枚 4克砝码2枚 问能称出那几种质量 各有几种方案 即可称出1至19克的质量 不同的方案数即为对应项前面的系数 母函数为 例12把整数N无序拆分成整数a1 a2 an的和 且不允许重复 求不同的拆分数 的不同解的个数 这个问题对应于求不定方程 令bN表示不同的拆分数 则其对应的母函数为 特殊的 当ai i时 对应的母函数为 例13把整数N无序拆分成整数a1 a2 an的和 允许重复 求不同的拆分数 的不同解的个数 这个问题对应于求不定方程 令bN表示不同的拆分数 则其对应的母函数为 特殊的 当ai i时 对应的母函数为 例14把整数N无序拆分成奇整数的和 允许重复 求不同的拆分数 这相当于在上例中把ai取成奇数 因此拆分数对应的母函数为 例15把整数N无序拆分成2的幂次的和 求不同的拆分数 这相当于把N拆分成1 2 4 8 的和 但不允许重复 因此拆分数对应的母函数为 例16把整数N无序拆分1 2 m的和 允许重复 求不同的拆分数 若要求m至少出现一次呢 若无要求 由例13可知其母函数为 若要求m至少出现一次 则拆分数对应的母函数为 这个等式的组合意义很明显 整数n拆分成1到m的和的拆分数减去拆分成1到m 1的和的拆分数 即为至少出现一个m的拆分数 显然有 设bN表示N剖分成不同正整数和的剖分数 则其对应的母函数为 定理1整数剖分成不同整数的和的剖分数 不允许重复 等于剖分成奇数的剖分数 允许重复 设bN表示N剖分成重复数不超过2的正整数之和的剖分数 则其对应的母函数为 定理2N剖分成其他数之和但重复数不超过2 其剖分数等于它剖分成不被3整除的数的和的剖分数 定理3N被剖分成一些重复次数不超过k次的整数的和 其剖分数等于被剖分成不被k 1除尽的数的和的剖分数 定理4对任意整数N 它被无序剖分成2的幂次的和的剖分方式一定唯一 例17若有1 2 4 8 16克的砝码各一枚 问能称出那几种质量 有几种可能方案 这说明用这些砝码可以称出从1克到31克的质量 而且方案都是唯一的 实际上这说明整数的二进制表示是唯一的 4 Ferrers图像 一个从上而下的n层格子组成的图像 mi为第i层的格子数 当mi mi 1 即上层的格子数不少于下层的格子数时 称之为Ferrers图像 如下图 每一层至少有一个格子 绕虚线轴旋转所得的图仍然是Ferrers图像 这样的两个Ferrers图像称为一对共轭的Ferrers图像 1 整数n拆分成k个数的和的拆分数 与数n拆分成最大数为k的拆分数相等 因为整数n拆分成k个数的和的拆分可以用一个k行的图像表示 所得的Ferrers图像的共轭图像最上面一行有k个格子 例如 利用Ferrers图像可以得到一些关于整数拆分的结果 24 6 6 5 4 35个数 最大数为6 24 5 5 5 4 3 26个数 最大数为5 理由和 1 相类似 因此 拆分成最多不超过m个数的和的拆分数的母函数是 2 整数n拆分成最多不超过m个数的和的拆分数 与n拆分成最大不超过m的拆分数相等 正好拆分成m个数的和的拆分数的母函数为 3 整数n拆分成互不相同的若干奇数的和的的拆分数 与n拆分成自共轭的Ferrers图像的拆分数相等 设整数n拆分为n 2n1 1 2n2 1 2nk 1 其中n1 n2 nk 构造一个Ferrers图像 第一行第一列都是n1 1格 对应于2n1 1 第二行第二列都是n2 1格 对应于2n2 1 依此类推 这样得到的Ferrers图像一定是自共轭的 反过来 自共轭的Ferrers图像也可以对应到一些不同奇数的和 例如17 9 5 3对应的Ferrers图像为 4 正整数n剖分成不超过k个数的和的剖分数 等于将n k剖分成恰好k个数的剖分数 不超过k层的Ferrers图像的每一层加上一个格子 一一对应到一个刚好k层的Ferrers图像 5 指数型母函数 考虑n个元素组成的多重集 其中a1重复了n1次 a2重复了n2次 ak重复了nk次 n n1 n2 nk 从中取r个排列 求不同的排列数 若r n 即考虑n个元素的全排列 则不同的排列数为 但是对于一般的r 情况就比较复杂了 先看一个具体的问题 假设有8个元素 其中a1重复3次 a2重复2次 a3重复3次 从中取r个组合 其组合数为cr 则其对应的母函数为 从x4的系数可知 从这8个元素中取4个组合 不同的组合数为10 这10个组合可从下面的展开式中得到 其中4次方项表示了所有从8个元素中取4个的组合方案 例如表示一个a1三个a3的组合 表示两个a1两个a3的组合 依此类推 接下来讨论从这8个元素中取4个的不同排列总数 以两个a1两个a3组合为例 不同排列数为4 2 2 同样一个a1三个a3的不同排列数为4 1 3 依此类推可以得到不同的排列总数为 为了便于计算 利用上述特点 形式地引进函数 从右边很容易可以看出 取2个的排列数为9 取3个的排列数为28 取4个的排列数为70 依此类推 定义 对于序列a0 a1 a2 函数 称为序列a0 a1 a2 对应的指数型母函数 这样 对于一个多重集 其中a1重复n1次 a2重复n2次 ak重复nk次 从中取r个排列的不同排列数所对应的指数型母函数为 例18求下列数列的指数型母函数 例19由1 2 3 4四个数字组成的五位数中 要求数1出现次数不超过2次 但不能不出现 2出现次数不超过1次 3出现次数最多3次 可以不出现 4出现次数为偶数 求满足上述条件的数的个数 设满足上述条件的r位数个数为cr 则其对应的指数型母函数为 由此可见满足条件的5位数共215个 例20求由1 3 5 7 9五个数字组成的n位数的个数 要求其中3 7出现的次数为偶数 其他1 5 9出现次数不加限制 设满足上述条件的n位数个数为cn 则其对应的指数型母函数为 因此 例217个有区别的球放进4个有标志