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

组合数学课件 制作讲授 王继顺 目录 1 第1章什么是组合数学1 1引例1 2组合数学研究对象 内容和方法第2章鸽巢原理2 1鸽巢原理 简单形式2 2鸽巢原理 加强形式2 3Ramsey定理2 4鸽巢原理与Ramsey定理的应用本章小结习题第3章排列与组合3 1两个基本的计数原理3 2集合的排列与组合3 3多重集的排列与组合本章小结习题 第四章二项式系数4 1二项式定理4 2组合恒等式4 3非降路径问题4 4牛顿二项式定理4 5多项式定理4 6基本组合计数的应用本章小结习题第五章包含排斥原理5 1包含排斥原理5 2多重集的r 组合数5 3错位排列5 4有限制条件的排列问题5 5有禁区的排列问题本章小结习题 目录 目录 2 第六章递推关系6 1Fibonacci数列6 2常系数线性齐次递推关系的求解6 3常系数线性非齐次递推关系的求解6 4用迭代和归纳法求解递推关系本章小结习题第七章生成函数7 1生成函数的定义和性质7 2多重集的r 组合数7 3正整数的划分7 4指数生成函数与多重集的排列问题7 5Catalan数和Stiring数本章小结习题 第八章Polya定理8 1置换群中的共轭类与轨道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 1 kC n k 1 k 的生成函数 解 由定义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 4 2 C 2n n 的生成函数 证明 由牛顿二项式定理有由定义知 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 1 2 3 2 3 4 n n 1 n 2 的生成函数 7 1指数生成函数概念 7 1生成函数的基本概念 定义7 2 7 1 2指数生成函数 注 fe x 也是形式幂函数 经常可结合以下公式运算 给定一无穷序列 a0 a1 an 简记为 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 n 的指数生成函数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 1 4 1 4 7 1 4 7 3n 1 的指数生成函数 解 由定义7 2和二项式定理 有 7 1生成函数定理1 7 1生成函数的基本概念 定理7 1 7 1 2指数生成函数 设f x fe x 分别为序列 an 的普通 指数生成函数 则 解 由指数生成函数的定义7 2 有将上式两边同乘以e s并从0到 积分得由分部积分法有故 设A x B x C x 分别是序列 an bn 和 cn 的生成函数 则C x A x B x 当且仅当ci ai bi i 0 1 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生成函数的基本运算 六个推论 推论7 2 1 7 2生成函数运算推论2 7 2生成函数的基本运算 六个推论 推论7 2 1 推论7 2 2 7 2生成函数运算推论3 7 2生成函数的基本运算 六个推论 推论7 2 1 推论7 2 2 推论7 2 3 见本节例1 7 2生成函数运算推论4 7 2生成函数的基本运算 六个推论 推论7 2 4 7 2生成函数运算推论5 6 7 2生成函数的基本运算 六个推论 推论7 2 5 推论7 2 4 推论7 2 6 设A x B x C x 分别是序列 an bn 和 cn 的指数生成函数 则C x A x B x 当且仅当ci ai bi i 0 1 r C x A x B x 当且仅当 i 0 1 r 7 2生成函数定理3 7 2生成函数的基本运算 定理7 3 6 5母函数在递推关系中的应用 6 5母函数在递推关系中的应用 母函数法是求解递推关系的一种重要方法 不仅可以求解常系数线性 非 齐次递推关系 也可以求解非线性 非常系数的递推关系 求解的方法和步骤为 用f x 表示序列 an 的普通母函数 利用递推关系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 令an 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位的十进制数的全体共9 10n 2 从中去掉含有偶数个5的数 余下的便是n 1位中含有奇数个5的数 故有 6 5母函数的应用例6 6 5母函数在递推关系中的应用 例题 例6 求递归关系 Hanoi塔 解 设序列 an 的普通母函数为 7 3排列组合概述 7 3在排列组合中的应用 生成函数有着极其广泛的应用 从本节开始介绍生成函数在某些组合数学的问题中的应用 本节介绍生成函数在组合中的应用和指数生成函数在排列中的应用 主要是计数问题 也有部分方案方法问题 考虑三个不同的物体a b c的选取方法 如果对选取方法的个数感兴趣 而不是对不同的选取方法感兴趣 则可令a b c 1 有 7 3组合应用例1 7 3在排列组合中的应用 7 3 1在组合中的应用 例题 例1 有红球两只 白球 黄球各一只 试求有多少种不同的组合方案 随机组合 解 设r w y分别代表红球 白球和黄球 由此可见 除一个球也不取的情况外 有 a 取一个球的组合数为三 即分别取红 白 黄 三种 b 取两个球的组合数为四 即两个红的 一红一黄 一红一白 一白一黄 c 取三个球的组合数为三 即两红一黄 两红一白 一红一黄一白 d 取四个球的组合数为一 即两红一黄一白 令取i个球的组合数为ai 则序列a0 a1 a2 a3 a4的生成函数为故共有1 3 4 3 1 12 或3 22 12 种组合方式 7 3组合应用例2 7 3在排列组合中的应用 7 3 1在组合中的应用 例题 例2 n个完全一样的球放到m个有标志的盒子中 不允许有空盒 问有多少种不同的方案 其中n m重复组合 解 由于不允许有空盒 令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 1 5x 令cn为为符合要求的n个人组成的小组的数目 由乘法法则 序列 cn 对应的生成函数为h x f x g x 1 x 8 1 x 8 1 x 5 1 5x 2故总的组成方式数目为128 26 3328 7 3组合应用例4 7 3在排列组合中的应用 7 3 1在组合中的应用 例题 例4 证明从n个不同的物体中允许重复地选取r个物体的方式数为F n r C n r 1 r 证明 设ar表示从n个不同的物体中允许重复的选取r个物体的方式数 序列 ar 的生成函数为 7 3组合应用例5 7 3在排列组合中的应用 7 3 1在组合中的应用 例题 例5 求从n个不同物体中允许重复地选取r个物体 但每个物体出现偶数次的方式数 解 设ar为所求的方式数 由于每个物体出现偶数次 故可用因子 1 x2 x4 示某一物体可以不选 或选取2次 或选取4次 因此序列 ar 的生成函数为 7 3组合应用例6 7 3在排列组合中的应用 7 3 1在组合中的应用 例题 例6 在一个书架上共有16本书 其中4本是高等数学 3本是普通物理 4本是数据结构 5本是离散数学 求从中选取r本数的方式数 其中r 12 解 这实际上是求重集 4 M 3 P 4 S 5 D 的12 组合数 设ar是选取r本书的方式数 由于高等数学最多只能选取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个字生成的不同的方式数 解 这个问题实际上是求重集 2n A 2n B 2n C 的3n 组合数 设ar为所求的方式数 则序列 ar 的生成函数为 7 3排列应用例8 7 3在排列组合中的应用 4 3 2在排列中的应用 例题 例8 由1 2 3 4四个数字组成的五位数中 要求数1出现次数不超过2次 但不能不出现 2出现不超过1次 3出现次数可达3次 也可不出现 4出现次数为偶数 求满足上述条件的数的个数 容斥原理 解 设满足条件的r位数的个数为ar 序列 ar 的指数母函数为由此可见满足条件的5位数ar 215个 7 3排列应用例9 7 3在排列组合中的应用 4 3 2在排列中的应用 例题 例9 求1 3 5 7 9五个数字组成的n位数的个数 要求其中3 7出现的次数为偶数 其他1 5 9出现的次数不加限制 解 设满足上述条件的r位数的个数为ar 序列 ar 的指数母函数为 7 3排列应用例10 7 3在排列组合中的应用 7 3 2在排列中的应用 例题 例10 证明从n个不同的物体中允许重复地选取r个物体的排列数为nr 证明 这个问题实际上是证明重集B b1 b2 bn 的r 排列数为nr 设ar为所求的排列数 则序列 ar 的指数母函数为 7 3排列应用例11 4 3在排列组合中的应用 4 3 2在排列中的应用 例题 例11 用红 白 绿三种颜色给1 n棋盘中的正方形着色 要求偶数个正方形着红色 而着白色和绿色的正方形个数不加限制 求不同的着色方式数 证明 若用R W和G分别表示红 白和绿三种颜色 则该问题实际上是求重集B R W G 的n 排列数 其中要求R出现偶数次 设an为所求的排列数 则序列 an 的指数母函数为 7 3排列应用例12 7 3在排列组合中的应用 7 3 2在排列中的应用 例题 例12 在所有的n位数中 包含数字3 8 9 但不包含数字0 4的数有多少 解 这个问题实际上是求重集B 1 2 3 5 6 7 8 9 的n 排列数 其中要求3 8 9至少出现一次 而其他的数不加限制 设符合题意的数有an个 则序列 an 的指数生成函数为 7 3排列应用例13 4 3在排列组合中的应用 4 3 2在排列中的应用 例题 例13 求1 2 3 4 5五个数字组成的r位数的个数 要求其中1出现的次数与2出现的次数的和必须是偶数 解 设an为符合题意的个数 由于1出现的次数与2出现的次数的和为偶数 可分为两种情况 1出现的次数与2出现的次数都为偶数 1出现的次数与2出现的次数都为奇数 由加法法则知 序列 an 的指数生成函数为 这是生成函数的应用实例之一 整数的拆分就是把整数分成若干个正整数部分 并且不考虑各部分的次序 不同的拆分方法的总数叫拆分数P n 相当于把n个无区别的球放到1 m n个无标志的盒子中的方法数 7 4整数的拆分概念 7 4整数的拆分 7 4整数的拆分定理4 7 4整数的拆分 定理7 4 设a b c 为大于0的整数 则1 1 xa 1 xb 1 xc 的级数展开式中xn的系数等于把正整数n拆分为a b c 的和的方法数P n 证明 注意到如果项xn是由x3a xb x2c 的乘积所组成的 则于是 每当n可以拆分为a b c的和时 xn就会出现 这就证明了定理的结论 7 4整数的拆分例1 7 4整数的拆分 例题 例1 若有1克 2克 3克 4克的砝码各一枚 问能称出哪几种重量 有几种可能方案 证明 我们采用如下办法来产生拆分数的生成函数 从右端的生成函数知能称出从1克到10克的重量 系数便是方案数 例如右端有2x5项 即称出5克的方案有2种 5 2 3 1 4 同样6 1 2 3 2 4 10 1 2 3 4 即称出6克的方案有2种 称出10克的方案有1种 7 4整数的拆分例2 7 4整数的拆分 例2 求用1分 2分 3分的邮票贴出不同数值的方案数 解 因邮票允许重复 故生成函数为以其中x4为例 其系数为4 即4拆分成1 2 3之和的拆分数为4 即 例题 7 4整数的拆分例3 7 4整数的拆分 例3 若有1克的砝码3枚 2克的4枚 4克的2枚 问能称出哪些重量 各有几种方案 解 上面的1 x4 x8项表示4克砝码只有两枚 或不取 或取一枚 或取2枚 x8项的系数为5 说明称8克的方案有5种 例题 7 4整数的拆分例4 7 4整数的拆分 例4 整数n拆分成1 2 3 m的和 并允许重复 求其生成函数 如若其中m至少出现一次 其生成函数如何 解 若整数n拆分成1 2 3 m的和 并允许重复 其生成函数为 若拆分中m至少出现一次 其生成函数为 上式的组合意义 整数n拆分成1到m的和的拆分数减去拆分成1到m 1的和的拆分数 即为至少出现一个m的拆分数 例题 7 4整数的拆分定义 7 4整数的拆分 定义7 3 用Pk n 表示n拆分为1 2 k允许重复的方法数 用Po n 表示n拆分为奇整数的方法数 用Pd n 表示n拆分为不同整数的方法数 用Pt n 表示n拆分为2的不同幂 1 2 4 的方法数 7 4整数的拆分推论 7 4整数的拆分 四个推论 推论7 4 1 P3 n 的普通母函数是1 1 x 1 x2 1 x3 推论7 4 2 Pk n 的普通母函数是1 1 x 1 x2 1 xk 推论7 4 3 P n 的普通母函数是1 1 x 1 x2 1 x3 推论7 4 4 Po n 的普通母函数是1 1 x 1 x3 1 x5 7 4整数的拆分定理5 7 4整数的拆分 定理7 5 设a b c 为不同的正整数 则 1 xa 1 xb 1 xc 的级数展开式中xn的系数就是把n拆分为a b c 的和 且a b c 最多只出现一次的方法数 两个推论 推论7 5 1 Pd n 的生成函数为 1 x 1 x2 1 x3 1 x4 推论7 5 2 Pt n 的生成函数是 1 x 1 x2 1 x4 1 x8 7 4整数的拆分定理6 1 7 4整数的拆分 定理7 6 Euler定理 Po n Pd n 证明 根据推论7 5 1 Pd n 的生成函数为等式右端正好是Po n 的生成函数 推论7 4 4 所以Po n Pd n 即把n拆分成奇整数的和的方法数等于把n拆分成不同的整数和的方法数 7 4整数的拆分定理6 2 7 4整数的拆分 定理7 6 Euler定理 Po n Pd n 可以验证当n 7的情况 7 4整数的拆分定理7 7 4整数的拆分 定理7 7 Sylvester定理 对任意正整数n有Pt n 1 证明I 因为任何一个正整数都可惟一地用一二进制数来表示 而一个二进制数又可惟一地表示成2的次幂的和 由此即得结论 证明II 因为序列 1 1 1 的生成函数为上式的左端正好是Pt n 的生成函数 推论4 5 2 7 4整数的拆分例5 7 4整数的拆分 例题 例5 设有1 2 4 8 16 32克砝码各一枚 试问能称出哪些重量 分别有几种方案 证明 从生成函数f x 可以得知 用这些砝码可以称出从0克到63克的重量 而且办法都是惟一的 实际是0到63的数的二进制表示是惟一的 7 4整数的拆分例6 7 4整数的拆分 例题 例6 证明以下恒等式并说明其组合含义 证明 因此这个恒等式表明 任何正整数都可以惟一地拆分成形式为的不同部分 换句话说 任何正整数的十进制表示是惟一的 7 4整数的拆分定理8 1 7 4整数的拆分 定理4 8 拆分数的估计式 对任意正整数n 有 证明 由推论4 4 3知 P n 的生成函数为 对上式两端取对数得由对数的泰勒展开式知 A 7 4整数的拆分定理8 2 7 4整数的拆分 定理7 8 拆分数的估计式 对任意正整数n 有 7 4整数的拆分定理8 3 7 4整数的拆分 定理4 8 拆分数的估计式 对任意正整数n 有 7 4整数的拆分定理8 4 7 4整数的拆分 定理4 8 拆分数的估计式 对任意正整数n 有 7 4整数的拆分定理8 5 7 4整数的拆分 定理7 8 拆分数的估计式 对任意正整数n 有 7 5Ferrers图定义 7 5Ferrers图 定义7 4 设n的一个拆分为n a1 a2 ak 其中a1 a2 ak 1 如从上到下依次画ai个格子 点 i 1 2 k 称此图称为Ferrers图 Ferrers图像具有如下性质 1 每一层至少有一个格子 2 第一行与第一列互换 第二行于第二列互换 即下图绕虚线轴旋转所得的图仍然是Ferrers图像 两个Ferrers图像称为一对共轭的Ferrers图像 7 5Ferrers图定理9 7 5Ferrers图 定理7 9 正整数n拆分为k项和的拆分数等于数n拆分为最大数为k的拆分数 7 5Ferrers图定理10 11 7 5Ferrers图 定理7 10 正整数n拆分为最多不超过k个数的和的拆分数等于数n拆分为最大数不超过k的拆分数 定理7 11 正整数n拆分为互不相同的若干奇数的和的拆分数等于数n拆分成有自共轭的Ferrers图的拆分数 7 6组合恒等式应用 生成函数不仅在计数中有广泛应用 而且在证明 推导 组合恒等式中提供了一种重要方法 其中用二项式定理的 参见 1 4 7 6在组合恒等式中的应用 7 6组合恒等式应用例1 1 例题