第20讲组合计数.ppt
《第20讲组合计数.ppt》由会员分享,可在线阅读,更多相关《第20讲组合计数.ppt(64页珍藏版)》请在三一文库上搜索。
1、第20讲 组合计数,主要内容: 1.排列组合与二项式定理 2.生成函数 3. 递归关系,Chapter 8 组合计数,我们知道,离散数学研究离散对象. 组合计数,简称计数(counting)就是计算满足一定条件的离散对象的安置方式的数目. 对于给定离散对象的安置方式,要考虑其存在性问题、计数问题、构造方法、最优化问题,这些是组合数学研究的全部内容(参见文献6). 组合数学发源于数学消遣和数学游戏,其研究历史可追溯到公元前2200年中国的大禹治水时代,从洛河中浮出的神龟背部上出现的三阶幻方开始,该方阵的每一行、每一列以及两条对角线的三个数字之和都等于15,其研究方兴未艾.,计算机科学是研究算法的
2、一门科学,组合计数是算法分析与设计的基础,它对于分析算法的时间复杂度和空间复杂度是至关重要的. 当然,组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性. 本章主要讨论组合计数的基本计数技巧和方法,包括计数的基本原理、排列组合、二项式定理、生成函数与递归关系等内容,它们都与集合、映射、运算和关系密切联系.,8.1 排列组合与二项式定理,8.1.1 排列 1. n个元素的r-排列 从n个不同的元素中,取r个出来按顺序排列,就是n个元素的r-排列(permutation),其排列个数记为 或P(n, r).,注意到 随着n的增大,n!呈指数增长. Stirli
3、ng给出的近似公式为:,利用乘法原理有下述结论. 定理8-1 对于任意r n, 有 显然 , n个元素的全排列个数为n!. 约定,2. n个元素的r-圆排列 实际上, n个元素的r-排列是线排列. 如果从n个不同的元素中, 取r个出来按顺序排列成一个圆, 就是n个元素的r-圆排列(circular permutation), 这样的排列个数记为 或P(n, r).,中国传统(上下左右)?,上面的圆排列可以得到1234,2341,3412和4123四个线排列. 一般地, 一个r-圆排列可以得到r个r-排列,于是 ,3. n个元素的r-可重排列 前面所讨论的排列中要求没有重复元素. 如果从n个不同
4、的元素中,可重复取r个元素按顺序排列,就是n个元素的r-可重排列(permutation with repetition),这样的排列个数记为 或U(n, r).,可以这样理解r-可重排列: 先从n个元素中任取一个元素出来排在第一位置, 有n种选取方式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有n种选取方式. 这样一直进行下去, 直到有r个元素排列为止. 因此, 根据乘法原理有,4. 有重复元素的全排列 定理8-2 设A1, A2, , Ak是k个不同元素,现有ni个Ai元素(i = 1, 2, , k, n1 + n2 + + nk = n), 即 (可重集) 则这n个元素的全
5、排列个数为,Proof 记这n个可重元素的全排列个数为N. 将ni个Ai元素看作不同的元素 于是得到n1 + n2 + + nk = n个不同元素,其全排列个数为n!. 由于ni个不同的元素的全排列个数为ni! (i = 1,2,k),于是所给n个可重元素的一个全排列可以得到n1! n2! nk!个n个不同元素的全排列, 根据乘法原理知N n1! n2! nk! = n!,进而,2 组合 1. n个元素的r-组合 从n个不同的元素中, 取r个出来放成一堆而不考虑其顺序, 就是n个元素的r-组合(combination), 其组合个数记为 或 或C(n, r). 上面的三个组合个数的记号都是标准
6、的, 但 和 容易混淆.,约定当r n时, ;同时约定, 由于一个r-组合可以得到r!个r-排列,根据乘法原理有下述结论. 定理8-3,2. n个元素的r-可重组合 如果从n个不同的元素中, 可重复地取r个元素而不考虑其顺序, 就是n个元素的r-可重组合(combination with repetition),这样的组合个数记为 或F(n, r). 定理8-4 Remark 一一对应是组合计数常用的解题技巧之一.,证(Euler证法) 不妨设n个不同元素分别为1, 2, , n. 可重复选取的r个元素为c1, c2, , cr, 可设c1c2cr. 记d1 = c1, d2 = c2+ 1,
7、 , dr = cr+ (r - 1), 于是得到另外一个组合d1, d2, , dr. 显然, 是c1, c2, , cr到d1, d2, , dr的一一对应, 于是组合c1, c2, , cr的个数与组合d1, d2, , dr的个数相同. 而组合d1, d2, , dr是在1, 2, , n, n + 1, , n + (r - 1)这n + r 1个不同的元素的r-组合, 其个数为,容易证明, n个元素的r-可重组合个数与不定方程 的非负整数解的个数相同. 利用这一点, 可以证明:若n个元素的r-可重组合中每个元素至少出现一次, 则r n且这样的组合个数为 例8-1 从为数众多的一元币
8、、五元币、十元币、五十元币和一百元币中选取6张出来,有多少种选取方式?,Solution 根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合, 其组合个数为,与组合有关的恒等式有近1000个,下面是常用的三个组合恒等式,可采用组合的计算公式定理8-3加以证明,也可以根据组合的意义进行“组合证明”. (1) 对称公式 (2) 加法公式 (3) 移进移出公式,3 二项式定理 与组合密切相关的是下述二项式定理. 定理8-5(二项式定理) 设n为正整数, 则对于任意x和y, 有,正因为这样,组合数又称为二项式系数. 根据二项式定理,有 思考 将所有n个元素的r-排列和
9、r-组合列举出来的方法. 作业 1,2,3,4.,8.2 生成函数,前面从计数的加法原理和乘法原理出发,介绍了排列组合的概念以及一些计算其个数的公式. 生成函数(generating function)又称为母函数,它是解决满足一定要求的排列组合计数问题的一种重要工具, 也是求解递归关系的一种工具. 利用生成函数解决计数问题的基本思想就是将要计算的个数ar = f(r) 转化为一个关于x的函数,通过对xr或 的系数的讨论得出结论(r = 0, 1, 2, ).,8.2.1 组合计数生成函数 定义8-1 对于数列a0,a1,ar,其组合计数生成函数(ordinary generating fun
10、ction)为 (形式)幂级数?,(1) 设n个元素的r-组合个数为ar,r = 0, 1, 2, . 显然, 有 其组合计数生成函数为,于是, ar就是其组合计数生成函数 中xr的系数且 实际上, 中第i个(1 + x)可理解为n个元素中的第i个元素,其中的“1”表示在组合中不取第i个元素,“x”表示在组合中选取了第i元素(i = 1, 2, , n).,(2) 设n个元素的r-可重组合个数为ar,r = 0, 1, 2, . 显然,有 特别地a0 = 1. 现考虑 其展开式中xr来源于第一个括号(1 + x + x2 + )中的 , 第二个括号(1 + x + x2 + )中的 , , 第
11、n个括号(1 + x + x2 + )中的 的乘积,即,这时, 该不定方程的非负整数解的个数即为 换句话说,有 因此, 上式右边展开式中xr的系数就是ar.实际上,,中的第i个(1 + x + x2 + ) 可理解为n个元素中的第i个元素, 其中的“1”表示在组合中不取第i个元素, “x”表示在组合中第i个元素取一次, “x2”表示在组合中第i个元素取了两次, “x3”表示在组合中第i个元素取了三次, , (i = 1, 2, , n). 上述思想还可以推广, 例如在组合计数生成函数中出现乘积项(x2 + x4),则表示对应的元素可取两次或四次.,(1) (2) (m为实数). (3),下面通
12、过例子说明如何利用组合计数生成函数解决一般的组合计数问题. 例8-2 一口袋中有5个红球, 3个黄球, 绿、白、黑球可任意多提供. 现从中取3个球, 有多少种选取方式? Solution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数,例8-3 现有2n个A, 2n个B, 2n个C, 求从它们中选出3n个字母的方式数. Solution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数,2 排列计数生成函数 Def 8-2 对于数列a0, a1, , ar, , 其排列计数生成函数(exponential generating func
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 20 组合 计数
链接地址:https://www.31doc.com/p-2565956.html