组合数学课件第二章母函数与递推关系.ppt

《组合数学课件第二章母函数与递推关系.ppt》由会员分享，可在线阅读，更多相关《组合数学课件第二章母函数与递推关系.ppt（356页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章 母函数与递推关系组合数学组合数学2.1 2.1 母函数母函数 递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如2.1 2.1 母函数母函数 项的系数 中所有的项包括n个元素a1，a2，an中取两个组合的全体；同理项系数包含了从n个元素a1，a2，an中取3个元素组合的全体。以此类推。2.1 2.1 母函数母函数 若令a1=a2=an=1 1，在（2-1-1）式中 项系数：中每一个组合有1个贡献，其他各项以此类推。故有：2.1 2.1 母函数母函数 另一方面：2.1 2.1 母函

2、数母函数比较等号两端项对应系数，可得一等式2.1 2.1 母函数母函数 同样对于 ，（设 ），用类似的方法可得等式：正法如下：2.1 2.1 母函数母函数比较等式两端的常数项，即得公式(2-1-3)2.1 2.1 母函数母函数又如等式：令x=1 可得2.1 2.1 母函数母函数(2-1-2)式等号的两端对x求导可得：等式(2-1-5)两端令x=1，得：2.1 2.1 母函数母函数 用类似的方法还可以得到：定义：定义：对于序列 构造一函数：2.1 2.1 母函数母函数 还可以类似地推出一些等式，但通过上面一些例子已可见函数 在研究序列 的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概

3、念如下：称函数G(x)是序列 的母函数序列 可记为 。如若已知序列 则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。2.1 2.1 母函数母函数 例如 是序列 的母函数。2.2 2.2 递推关系递推关系 利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。2.2 2.2

4、递推关系递推关系 Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。算法：算法：N=2时第一步先把最上面的一个圆盘套在B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B C2.2 2.2 递推关系递推关系z 对于一般n个圆盘的问题，z 假定n-1个盘子的转移算法已经确定。z 先把上面的n-1个圆盘经过C转移到B。z 第二步把A下面一个圆盘移到C上z 最后再把B上的n-1个圆盘经过A转移到C上A B C2.2 2.2 递推关系递推关系 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二

5、步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。2.2 2.2 递推关系递推关系 算法分析：算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有2.2 2.2 递推关系递推关系算法复杂度为：H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。2

6、.2 2.2 递推关系递推关系 下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。2.2 2.2 递推关系递推关系 根据(2-2-1)，或利用递推关系(2-2-1)有2.2 2.2 递推关系递推关系 上式左端为：右端第一项为：右端第二项为：2.2 2.2 递推关系递推关系 整理得 这两种做法得到的结果是一样的。即：2.2 2.2 递推关系递推关系 令 如何从母函数得到序列？下面介绍一种化为部分分数的算法。2.2 2.2 递推关系递推关系 由上式可得：即：2.2 2.2 递推关系递推关系因为：2.2 2.2 递

7、推关系递推关系 例例2.求n位十进制数中出现偶数个5的数的个数。先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。2.2 2.2 递推关系递推关系 解法解法1：令 位十进制数中出现5的数的个数，位十进制数中出现奇数个5的数 的个数。故有：也有类似解释。2.2 2.2 递推关系递推关系 (2-2-2)式中的 表达了含有偶数个5的n位十进制数的两个组成部分。表达由含有偶数个5的n-1位十进制数 ，令 取5以外的0，1，2，3，4，6，7，8，9

8、九个数中的一个数构成的。项表示当 是含有奇数个5的n-1位十进制数，令 而得 是含偶数个5的n位十进制数。(2-2-2)是关于序列 和 的连立关系。2.2 2.2 递推关系递推关系 设序列 的母函数为 ，序列 的母函数为 。即：2.2 2.2 递推关系递推关系承前页：2.2 2.2 递推关系递推关系 又：故得关于母函数 和 得连立方程组：2.2 2.2 递推关系递推关系2.2 2.2 递推关系递推关系2.2 2.2 递推关系递推关系 解法二：解法二：n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：2.2 2.2 递推关系递推关系令2.2 2.2

9、 递推关系递推关系 1）不出现某特定元素设为 ，其组合数为 ，相当于排除 后从 中取r个做允许重复的组合。2.2 2.2 递推关系递推关系 例三：例三：从n个元素 中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。2.2 2.2 递推关系递推关系 2）至少出现一个 ，取组合数为 相当于从 中取r-1个做允许重复的组合，然后再加上一个 得从n个元素中取r个允许重复的组合。依据加法原则可得：因 ，故令2.2 2.2 递推关系递推关系 递推关系(2-2-3)带有两个参数n和r。2.2 2.2 递推关系递推关系 (2-2-3)式是关于 的递推关系，但系数 不是常数。但

10、2.2 2.2 递推关系递推关系 由二项式定理 可得2.3 2.3 母函数的性质母函数的性质2.32.3母函数的性质母函数的性质 一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。如2的例子所示的那样，为了求满足某种第推关系的序列，可把它转换为求对应的母函数 ，可能满足一代数方程，或代数方程组，甚至于是微分方程。2.32.3母函数的性质母函数的性质 最后求逆变换，即从已求得的母函数 得到序列 。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。不特别说明下面假设 、两个序列

11、对应的母函数分别为 、2.32.3母函数的性质母函数的性质 性质性质1：若 则证：证：2.32.3母函数的性质母函数的性质 例例.已知则2.32.3母函数的性质母函数的性质 性质性质2：若 ，则2.32.3母函数的性质母函数的性质证：证：2.32.3母函数的性质母函数的性质 例例.2.32.3母函数的性质母函数的性质 性质性质2：若 ，则证：证：2.32.3母函数的性质母函数的性质2.32.3母函数的性质母函数的性质 例例.已知2.32.3母函数的性质母函数的性质 类似可得：2.32.3母函数的性质母函数的性质 性质性质2：若 收敛，则2.32.3母函数的性质母函数的性质2.32.3母函数的性

12、质母函数的性质 性质性质5.5.若 ，则 。例例.则2.32.3母函数的性质母函数的性质性质5和性质6的结论是显而易见的。性质性质6 6.若 ，则 2.32.3母函数的性质母函数的性质 性质性质7 7.若 则 2.32.3母函数的性质母函数的性质证证:。2.32.3母函数的性质母函数的性质 例例.已知 则 2.4 2.4 FibonacciFibonacci数列数列2.4.12.4.1递推关系递推关系 Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。问题：问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为

13、其中当月新生兔数目设为 对。第n-1个月留下的兔子数目设为 对。2.4.12.4.1递推关系递推关系 但即第n-2个月的所偶兔子到第n个月都有繁殖能力了。由递推关系(2-3-1)式可依次得到2.4.22.4.2问题的求解问题的求解 设2.4.22.4.2问题的求解问题的求解 承前页2.4.22.4.2问题的求解问题的求解承前页2.4.22.4.2问题的求解问题的求解承前页2.4.22.4.2问题的求解问题的求解 其中2.4.32.4.3若干等式若干等式 1）证明：证明：2.4.32.4.3若干等式若干等式 2）证明：证明：2.4.32.4.3若干等式若干等式 3）证明：证明：2.4.42.4.

14、4在选优法上的应用在选优法上的应用 设函数 在区间 上有一单峰极值点，假定为极大点。所谓单峰极值，即只有一个极值点 ，而且当x与 偏离越大，偏差 也越大。如下图：2.4.42.4.4在选优法上的应用在选优法上的应用 设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把 三等分，令：如下图：2.4.42.4.4在选优法上的应用在选优法上的应用 依据 的大小分别讨论如下：当 ，则极大点 必在 区间上，区间 可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用 当 ，则极大点 必在 区间上，区间 可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用

15、 当 ，则极大点 必在 区间上，区间 和 均可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用 可见做两次试验，至少可把区间缩至原来区间的2/3，比如 ，进一步在 区间上找极值点。若继续用三等分法，将面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。2.4.42.4.4在选优法上的应用在选优法上的应用 设保留 区间，继续在 区间的下面两个点 处做试验，若则前一次 的点的试验，这一次可继续使用可节省一次试验。由(2-3-6)式有2.4.42.4.4在选优法上的应用在选优法上的应用 这就是所谓的0.618优选法。即若在 区间上找单峰极大值时，可在

16、点做试验。比如保留区间 ，由于 ，故只要在 点作一次试验。2.4.42.4.4在选优法上的应用在选优法上的应用 优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。(a)所有可能试验数正好是某个 。2.4.42.4.4在选优法上的应用在选优法上的应用 这时两个试验点放在 和 两个分点上，如果 分点比较好，则舍去小于 的部分；如果 点更好，则舍去大于 的部分。在留下的部分共 个分点，其中第 和第 二试验点，恰好有一个是刚才留下来的试验可以利用。可见在 个可能试验中，最多用n-1次试验便可得到所求的极值点2.4.42.4.4在选优法上的应用在选

17、优法上的应用 (b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比 小,但比 大时,可以虚加几个点凑成 个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。2.4.42.4.4在选优法上的应用在选优法上的应用 下面给出两个定理作为这一节的结束。定理：定理：测试n次可将包含单峰极值点的区间缩小到原区间的 ，其中 是任意小的正整数，2.4.42.4.4在选优法上的应用在选优法上的应用 证：证：对n用数学归纳法。n=2时，将区间 平分成 段。在分点（包括端点a，b）分别标上 。在1点的两侧取 ，在 与 两点上测试，

18、无论哪一点较优，保留下来的区间长度均为 ，命题成立。2.4.42.4.4在选优法上的应用在选优法上的应用 假设对于n-1，命题成立 对于n，将 平分成 段，对分点（包括端点a，b）依次标上 。先在 点与 点测试，无论哪一点较优，保留下来的区间均为 段。根据归纳假设，再做n-1次测试（内含前两次测试之一）可将含极值点的区间缩小到 段，即原区间 的 。2.4.42.4.4在选优法上的应用在选优法上的应用 因 ，当n较大时，可将相继的两个测试点取在待测区间的0.618及1-0.618处。由 可知，0.618法比 法最多多测试一次。0.618 法的优点是不必事先定测试次数。2.4.42.4.4在选优法

19、上的应用在选优法上的应用 定理：定理：设在给定区间内有单峰极值点。如果包含极值点在内的可测点为 个，则测试n次必可找到极值点，。证：证：对n用数学归纳法。n=2时，命题成立2.4.42.4.4在选优法上的应用在选优法上的应用 下面证明对n命题成立。设可测试点的标号依次是 。先在 点及 点测试。无论哪一点较优，保留下来的可测点都为 个。根据归纳假设，再测试n-1必可找到极值点。而在保留的 个可测试点中，有一点（或 ）的测试结果下一次比较好时正好用上，这样总测试次数为n。假设对于n-1，命题成立2.5 2.5 线性常系数递推关系线性常系数递推关系 2.5 2.5 线性常系数递推关系线性常系数递推关

20、系 定义定义 如果序列 满足 及 是常数，则称为 的 阶常系数线性递推关系，称为 的初始条件，称为 的特征多项式2.5 2.5 线性常系数递推关系线性常系数递推关系 设 为 的母函数根据(2-5-1)，有2.5 2.5 线性常系数递推关系线性常系数递推关系将这些式子两边分别相加，得到即其中2.5 2.5 线性常系数递推关系线性常系数递推关系 令 ，多项式 的次数不大于 。特征多项式2.5 2.5 线性常系数递推关系线性常系数递推关系因此，是 次多项式，我们知道 在复数域中有 个根。设2.5 2.5 线性常系数递推关系线性常系数递推关系则 于是2.5 2.5 线性常系数递推关系线性常系数递推关系

21、(2-5-3)式是有理式，且分子的次数低于分母的次数，有分项表示，即：2.5 2.5 线性常系数递推关系线性常系数递推关系承上页：的系数是 。是常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 定理：定理：设 是有理分式，多项式的 次数低于 的次数。则 有分项表示，且表示唯一2.5 2.5 线性常系数递推关系线性常系数递推关系 证明：证明：设 的次数为n，对n用数学归纳法。n=1时，是常数，命题成立。假设对小于n的正整数，命题成立。下面证明对正整数n命题成立。设 是 的 重根，2.5 2.5 线性常系数递推关系线性常系数递推关系不妨设 与 互素，设2.5 2.5 线性常系数递推关系线

22、性常系数递推关系 的次数低于 。根据归纳假设，可分项表示。因此，可分项表示。由(2-5-6)式及(2-5-7)式可知表示是唯一的。2.5 2.5 线性常系数递推关系线性常系数递推关系以下分别各种情况讨论具体计算的问题。（1）特征多项式 无重根 设 可见化为2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数是可由线性方程组解出。2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数矩阵的行列式是Vander mond 行列式不难看出 有唯一解。2.5 2.5 线性常系数递推关系线性常系数递推关系（2）特征多项式 有共轭复根 设 是 的一对共轭复根。中 的系数是2.5 2.5 线性

23、常系数递推关系线性常系数递推关系 2.5 2.5 线性常系数递推关系线性常系数递推关系其中在具体计算时，可先求出各对共轭复根，再求待定系数A，B，避免中间过程的复数运算。（3）特征多项式 有重根设 是 的 重根，则(2-5-4)可简化为2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数 。其中是n的j-1次多项式。因此，是 与n的k-1次多项式的乘积。2.5 2.5 线性常系数递推关系线性常系数递推关系 为了简化计算，下面引入一些记号，介绍几个命题。设x是任意变量，n是非负整数，令2.5 2.5 线性常系数递推关系线性常系数递推关系 不难证明，多项式可用 唯一线性表示。其中 是常数2

24、.5 2.5 线性常系数递推关系线性常系数递推关系 设 是给定序列，令 称为 的 阶差分。不难证明，如果对任意的n有 ，则有因而序列 的特征多项式为2.5 2.5 线性常系数递推关系线性常系数递推关系 不难证明，如果 是n的r次多项式，则 是n的r+1次多项式。以上几个命题作为习题，请读者自己证明。2.5 2.5 线性常系数递推关系线性常系数递推关系 总之：总之：(1)若特征多项式 有n个不同零点 则递推关系(2-5-1)的解其中 是待定系数，有初始条件(2-5-2)来确定。2.5 2.5 线性常系数递推关系线性常系数递推关系 (2)若特征多项式 有不同的复根，可依照(1)的办法处理。不过任意

25、复数 可写为 形式，设 是 的一个零点，其共轭复根为2.5 2.5 线性常系数递推关系线性常系数递推关系 和 仍然是待定常数。即 有一对共轭复根 和 时，递推关系(2-5-1)的解有对应的项其中A，B是待定常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 (3)若 k重根。不妨设 是k的重根。则递推关系(2-5-1)的解对应于的项为 其中 是k个待定常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 例例1 1：求下列n阶行列式 的值。2.5 2.5 线性常系数递推关系线性常系数递推关系根据行列式性质对应的特征方程为故 是二重根2.5 2.5 线性常系数递推关系线性常系数递推

26、关系 时有 时有即2.5 2.5 线性常系数递推关系线性常系数递推关系 例例2 2：求同理相减得2.5 2.5 线性常系数递推关系线性常系数递推关系同理对应的特征方程为2.5 2.5 线性常系数递推关系线性常系数递推关系 是三重根即这就证明了2.5 2.5 线性常系数递推关系线性常系数递推关系 例例2 2：求同理相减得2.5 2.5 线性常系数递推关系线性常系数递推关系同理对应的特征方程为相减得同理2.5 2.5 线性常系数递推关系线性常系数递推关系 是四重根依据 得关于A、B、C、D的连立方程组：2.5 2.5 线性常系数递推关系线性常系数递推关系2.5 2.5 线性常系数递推关系线性常系数

27、递推关系 已知 是n的3次式，故不妨令确定待定系数时，比较方便，无需解一联立方程组。例如2.5 2.5 线性常系数递推关系线性常系数递推关系2.5 2.5 线性常系数递推关系线性常系数递推关系 例例4 4：求 解解:是n的3次多项式，因此 是满足递推关系：设2.5 2.5 线性常系数递推关系线性常系数递推关系2.5 2.5 线性常系数递推关系线性常系数递推关系以n=5对上面的结果验证一下2.5 2.5 线性常系数递推关系线性常系数递推关系 例例5 5：求 中 的 系数。解：解：的特征多项式是2.5 2.5 线性常系数递推关系线性常系数递推关系 是3重根 是1重根 的根是2.5 2.5 线性常系

28、数递推关系线性常系数递推关系因此可设2.5 2.5 线性常系数递推关系线性常系数递推关系 通过做长除法，求得2.5 2.5 线性常系数递推关系线性常系数递推关系可知 利用 的值解得。故2.5 2.5 线性常系数递推关系线性常系数递推关系 通过上式，计算得 与用长除法得到的结果相同。2.6 2.6 整数的拆分和整数的拆分和FerrersFerrers图像图像 2.6.1 2.6.1 问题举例问题举例 所谓整数拆分即把整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。2.6.1 2.6

29、.1 问题举例问题举例 例例1 1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？2.6.1 2.6.1 问题举例问题举例 从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有 项，即称出5克的方案有2同样，故称出6克的方案有2，称出10克的方案有12.6.1 2.6.1 问题举例问题举例 例例2 2：求用1分、2分、3分的邮票贴出不同数值的方案数。因邮票允许重复，故母函数为 以其中为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即2.6.1 2.6.1 问题举例问题举例 例例3 3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问

30、能称出那几种重量？各有几种方案？2.6.1 2.6.1 问题举例问题举例2.6.1 2.6.1 问题举例问题举例 例例4:4:整数n拆分成1，2，3，m的和，并允许重复，求其母函数。如若其中m至少出现一次，其母函数如何？若整数n拆分成1，2，3，m的和，并允许重复，其母函数为：2.6.1 2.6.1 问题举例问题举例2.6.1 2.6.1 问题举例问题举例 若拆分中m至少出现一次，其母函数为：2.6.1 2.6.1 问题举例问题举例显然有等式(2-6-1)的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。2.6.1 2.6.1 问题举例问

31、题举例 例例1 1：若有1、2、4、8、16、32克的砝码各一枚，问能称出那几种重量？有几种可能方案？2.6.1 2.6.1 问题举例问题举例 从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n，可表示为而且是唯一的。2.6.2 2.6.2 拆分数估计式拆分数估计式 定理：定理：设 为整数n的拆分数，则 证：证：令 一个整数n拆分成若干整数的和，在拆分中每个整数允许重复出现。故2.6.2 2.6.2 拆分数估计式拆分数估计式2.6.2 2.6.2 拆分数估计式拆分数估计式2.6.2 2.6.2 拆分数估计式拆分数估计式由于2.6.2

32、 2.6.2 拆分数估计式拆分数估计式 把(2-6-3)式代入(2-6-2)式得由于2.6.2 2.6.2 拆分数估计式拆分数估计式因而2.6.2 2.6.2 拆分数估计式拆分数估计式 设 ，有2.6.2 2.6.2 拆分数估计式拆分数估计式把(2-6-4)式代入(2-6-5)式得曲线 是上凸，故曲线位于曲线 的切线下方，点 的切线为故有2.6.2 2.6.2 拆分数估计式拆分数估计式 图 (2-6-1)2.6.2 2.6.2 拆分数估计式拆分数估计式以上式代入(2-6-5)式得：2.6.2 2.6.2 拆分数估计式拆分数估计式 不等式(2-6-7)的左端 是常数，右端是 的函数，即不等式对于

33、 成立。右端函数取极小值时将给出较好的上界值。令求导得2.6.2 2.6.2 拆分数估计式拆分数估计式令 ，得解方程，得2.6.2 2.6.2 拆分数估计式拆分数估计式因为所以 是极小值。以 的值代入 ，得2.6.2 2.6.2 拆分数估计式拆分数估计式利用 ，上式可改进为2.6.3 2.6.3 FerrersFerrers图像图像 一个从上而下的n层格子，为第 层的格子数，当 ，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如图(2-6-2)示。图 2-6-22.6.3 2.6.3 FerrersFerrers图像图像 Ferrers图像具有如下性质：1.每一层至少有一个格子

34、。2.第一行与第一列互换，第二行于第二列互换，即图(2-6-3)绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers 图像称为一对共轭的Ferrers图像。2.6.3 2.6.3 FerrersFerrers图像图像 利用Ferrers图像可得关于整数拆分的十分有趣的结果。(a)整数n拆分成k个数的和的拆分数，和数n拆分成个数的和的拆分数相等。因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如：2.6.3 2.6.3 FerrersFerrers图像图像 24=6+6+5+4+3 5个数，最大数为6 24=5+5+5+4

35、+3+2 6个数，最大数为5图(2-6-3)2.6.3 2.6.3 FerrersFerrers图像图像 (b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。理由和(a)相类似。因此，拆分成最多不超过m个数的和的拆分数的母函数是2.6.3 2.6.3 FerrersFerrers图像图像 拆分成最多不超过m-1个数的和的拆分数的母函数是 所以正好拆分成m个数的和的拆分数的母函数为2.6.3 2.6.3 FerrersFerrers图像图像 所以正好拆分成m个数的和的拆分数的母函数为2.6.3 2.6.3 FerrersFerrers图像图像 (c)整数n拆分成互

36、不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等.设 ，其中 。构造一个Ferrers图像，其第一行，第一列都是 格，对应于 ，第二行，第二列各 格，对应于 。以此类推。由此得到的Ferres图像是共轭的。反过来也一样。2.6.3 2.6.3 FerrersFerrers图像图像例如对应为Ferrers图像为9+5+3=17图(2-6-4)2.7 2.7 指数型母函数指数型母函数 2.7.1 2.7.1 问题提出问题提出 设有n个元素，其中元素 重复了 次，元素 重复了 次，重复了 次，从中取r个排列，求不同的排列数 如果 ，则是一般的排列问题。2.7.1 2.

37、7.1 问题提出问题提出 现在由于出现重复，故不同的排列计数便比较复杂。先考虑 个元素的全排列，若 个元素没有完全一样的元素，则应有 种排列。若考虑 个元素 的全排列数为 ，则真正不同的排列数为2.7.2 2.7.2 解的分析解的分析 先讨论一个具体问题：若有8个元素，其中设 重复3次，重复2次，重复3次。从中取r个组合，其组合数为 ，则序列 的母函数为2.7.2 2.7.2 解的分析解的分析 从 的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到2.7.2 2.7.2 解的分析解的分析 承前页2.7.2 2.7.2 解的分析解的分析其中4次方项有(2-7-2

38、)表达了从8个元素(各3个,2个)中取4个的组合。例如 为一个 ，3个 的组合，为两个 ，两个 的组合，以此类推。2.7.2 2.7.2 解的分析解的分析 若研究从中取4个的不同排列总数，以 对应的两个两个的不同排列为例，其不同排列数为即 六种。同样，1个 3个 的不同排列数为 2.7.2 2.7.2 解的分析解的分析 即 以此类推。故从(2-7-2)式可得问题的解，其不同的排列数为2.7.3 2.7.3 指数型母函数指数型母函数 为了便于计算，利用上述特点，形式地引进函数2.7.3 2.7.3 指数型母函数指数型母函数 承上页2.7.3 2.7.3 指数型母函数指数型母函数 从(2-7-3)

39、式计算结果可以得出：取一个的排列数为，取两个的排列数为 取3个的排列数为 ，取4个的排列数为 ，如此等等。把(2-7-3)式改写成下面形式便一目了然了。2.7.3 2.7.3 指数型母函数指数型母函数 定义：定义：对于序列 ，函数称为是序列 得指数型母函数2.7.3 2.7.3 指数型母函数指数型母函数 综合上述可得如下两个结论：(a)若元素 有 个，元素 有 个，元素 有 个，由此；组成的n个元素的排列，不同的排列总数为其中2.7.3 2.7.3 指数型母函数指数型母函数 (b)若元素 有 个，元素 有 个，元素 有 个，由此；组成的n个元素中取r个排列，设其不同的排列数为 。则序列 的指数

40、型母函数为2.7.3 2.7.3 指数型母函数指数型母函数 与(2)中所用的方法相比，可以看出指数型母函数在解决有重复元素的排列时的优越性。2.7.4 2.7.4 举例举例 例例1 1：求由两个 ，1个 ，2个 组成的不同排列总数。根据结论一，不同的排列总数为2.7.4 2.7.4 举例举例 例例2 2：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。2.7.4 2.7.4 举例举例 设满足上述条件的r位数为 ，序列 的指数型母函数为2.7.4 2.7.4 举例

41、举例由此可见满足条件的5位数共215个。2.7.4 2.7.4 举例举例例例3:求1，3，5，7，9五个数字组成的 位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。设满足条件的 位的个数为 ，则序列 对应的指数型母函数为2.7.4 2.7.4 举例举例由于2.7.4 2.7.4 举例举例2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 例例1 1：下图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，在t+1时刻D将输出同样的信号，符号 表示加法装置DDD输入u输出

42、v图 2-8-12.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 若在 时刻，输入信号 求相同时刻的输出信号 。显然，一般的有2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 若信号输入的序列 的母函数为 ，输出的信号序列 的母函数为 ，则其中被装置（图 2-8-1）的特性所确定，可以看作是该装置的传递函数，如图2-8-22.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 例例2 2：由红球两个，白球、黄球各一个，试求有多少种不同的组合方案。设r，w，y分别代表红球，白球，黄球。2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例由此可

43、见，出一个球也不取的情况外，有：（a）取一个球的组合数为三，即分别取红，白，黄，三种。（b）取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄。（c）取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白。（d）取四个球的组合数为一，即两红一黄一白。2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 令取r的组合数为，则序列 的母函数为共有1+3+4+3+1=12种组合方式。2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 例例3 3：n个完全一样的球放到m个有标志的盒子中，不允许有空盒，问共有多少种不同的方案？其中 由于不允许有空盒，令n个球放到m

44、个有标志的盒子的方案数为 ，序列 对应的母函数为 。则2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例因故二项式 中 项系数为2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例即2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 例例4 4：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式。令 为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数，故 。2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例故数列 对应一母函数类似的方法可得女同志的允许组合

45、数对应的母函数位2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 中 项的系数 为符合要求的 个人组成的小组的数目，总的组成方式数目为2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例 例例5 5：10个数字（0到9）和4个四则运算符 组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。因所求的n个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第n-1位有两种可能，一是数字，一是运算符。如若第n-1位是十个数字之一，则前n-1位必然构成一算术表达式。2.8 2.8 母函数

46、和递推关系应用举例母函数和递推关系应用举例如若不然，即第 位是4个运算符之一，则前 位必然是算术表达式。根据以上分析，令 表 个元素排列成算术表达式的个数。则指的是从0到99的100个数，以及2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例利用递推关系 ，得 特征多项式 。它的根是解方程2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例得2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例例例6 6：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？设满足条件的n条封闭 曲线所分割成的域的数目为 ，

47、其中 条封闭曲线 所分割成的域的数目为图 2-8-32.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例第n条封闭曲线和这些曲线相交于 个点，这 个点把第n条封闭曲线截成 条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为利用递推关系 得2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例设2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例另解：利用欧拉公式 点数+域数-边数=2点数=，边数=点数域数=2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例例例7 7：平面上有一点P，它是n个域的共同交界点，见图 现取k种颜色对这n个域进行着

48、色，要求相邻两个域着的颜色不同。试求着色的方案数。令 表示这n个域的着色方案数。无非有两种情况：图 2-8-42.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例（1）和 有相同的颜色；（2）和 所着颜色不同。第一种情形，域有 种颜色可用，即 域所用颜色除外；而且从 到 的着色方案，和 个域的着色方案一一对应。后一种 域有 种颜色可供使用；而且从 到 的每一个着色方案和 个域的着色方案一一对应。2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例利用 得 的特征方程为2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例解方程得2.8 2.8 母函数和递推关系

49、应用举例母函数和递推关系应用举例例例8 8：求下列行列式（n行n列）2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例利用行列式展开法，沿第一行展开得利用 式得 特征方程是解方程，得2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例设解方程2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例得2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例例例9 9：求n位2进制最后三位出现010图象的数的个数。对于n位2进制数 从左而右进行扫描，一当出现010图象，便从这图象后面一位从头开始扫描，例如对11位2进制数00101001010从左而右的扫描

50、结果应该是2-4，7-9位出现010图象，即2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例而不是4-6，7-9位出现的010图象，即不是 为了区别于前者起见，我们说4-6，9-11位是010，但不是“出现010图象”，这作为约定。为了找出关于数列 的第推关系，需对满足条件的数的结构进行分析。由于n位中除了最后三位是010已确定，其余 位可取0或1：2.8 2.8 母函数和递推关系应用举例母函数和递推关系应用举例故最后3位是010的n位2进制数的个数是 。其中包含最后3位出现010图象的以及在 位到第 位出现010图象，而在最后3位并不出现010图象的两类数，后一种数为2.8