《第20讲组合计数》由会员分享，可在线阅读，更多相关《第20讲组合计数（64页珍藏版）》请在金锄头文库上搜索。
1、第20讲 组合计数n n主要内容：n n1.排列组合与二项式定理排列组合与二项式定理 n n2.生成函数生成函数n n3. 递归关系递归关系Chapter 8 组合计数组合计数 n n我们知道，离散数学研究离散对象我们知道，离散数学研究离散对象. . 组合计数，组合计数，简称计数简称计数(counting)(counting)就是计算满足一定条件的离就是计算满足一定条件的离散对象的安置方式的数目散对象的安置方式的数目. . n n对于给定离散对象的安置方式，要考虑其存在性对于给定离散对象的安置方式，要考虑其存在性问题、计数问题、构造方法、最优化问题，这些问题、计数问题、构造方法、最优化问题，这
2、些是组合数学研究的全部内容是组合数学研究的全部内容( (参见文献参见文献6). 6). 组合组合数学发源于数学消遣和数学游戏，其研究历史可数学发源于数学消遣和数学游戏，其研究历史可追溯到公元前追溯到公元前22002200年中国的大禹治水时代，从洛年中国的大禹治水时代，从洛河中浮出的神龟背部上出现的三阶幻方开始，该河中浮出的神龟背部上出现的三阶幻方开始，该方阵的每一行、每一列以及两条对角线的三个数方阵的每一行、每一列以及两条对角线的三个数字之和都等于字之和都等于1515，其研究方兴未艾，其研究方兴未艾. . n n计算机科学是研究算法的一门科学，组合计数是算法分析与设计的基础，它对于分析算法的时
3、间复杂度和空间复杂度是至关重要的. 当然，组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性. n n本章主要讨论组合计数的基本计数技巧和方法，包括计数的基本原理、排列组合、二项式定理、生成函数与递归关系等内容，它们都与集合、映射、运算和关系密切联系. 8.1 排列组合与二项式定理排列组合与二项式定理 n n8.1.1 排列排列n n1. n个元素的r-排列n n从n个不同的元素中，取r个出来按顺序排列，就是n个元素的r-排列排列(permutation)，其排列个数记为 或P(n, r). n n注意到n n随着n的增大，n!呈指数增长. n nStir
4、ling给出的近似公式为: n n利用乘法原理有下述结论. n n定理定理8-1 对于任意r n, 有n n显然 , n个元素的全排列个数为n!. n n约定n n2. n个元素的r-圆排列n n实际上, n个元素的r-排列是线排列. 如果从n个不同的元素中, 取r个出来按顺序排列成一个圆, 就是n个元素的r-圆排列圆排列(circular permutation), 这样的排列个数记为 或P(n, r). 中国传统（上下左右）？n n上面的圆排列可以得到1234,2341,3412和4123四个线排列. n n一般地, 一个r-圆排列可以得到r个r-排列,于是 n n3. n个元素的r-可重
5、排列n n 前面所讨论的排列中要求没有重复元素. 如果从n个不同的元素中，可重复取r个元素按顺序排列，就是n个元素的r-可重排列可重排列(permutation with repetition)，这样的排列个数记为 或U(n, r).n n可以这样理解r-可重排列: 先从n个元素中任取一个元素出来排在第一位置, 有n种选取方式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有n种选取方式. 这样一直进行下去, 直到有r个元素排列为止. 因此, 根据乘法原理有n n4. 有重复元素的全排列n n定理定理8-2 设A1, A2, , Ak是k个不同元素，现有ni个Ai元素(i = 1, 2
6、, , k, n1 + n2 + + nk = n), 即n n(可重集)n n则这n个元素的全排列个数为n nProof 记这n个可重元素的全排列个数为N. 将ni个Ai元素看作不同的元素n n于是得到n1 + n2 + + nk = n个不同元素，其全排列个数为n!. 由于ni个不同的元素的全排列个数为ni! (i = 1,2,k),于是所给n个可重元素的一个全排列可以得到n1! n2! nk!个n个不同元素的全排列, 根据乘法原理知N n1! n2! nk! = n!，进而n n2 组合组合n n1. n个元素的r-组合n n从n个不同的元素中, 取r个出来放成一堆而不考虑其顺序, 就是
7、n个元素的r-组合组合(combination), 其组合个数记为 或 或C(n, r). n n上面的三个组合个数的记号都是标准的, 但n n 和 容易混淆. n n约定当r n时, ；同时约定, n n由于一个r-组合可以得到r!个r-排列，根据乘法原理有下述结论. n n定理定理8-3 n n2. n个元素的r-可重组合n n如果从n个不同的元素中, 可重复地取r个元素而不考虑其顺序, 就是n个元素的r-可重可重组合组合(combination with repetition)，这样的组合个数记为 或F(n, r). n n定理定理8-4 n nRemark 一一对应是组合计数常用的解题
8、技一一对应是组合计数常用的解题技巧之一巧之一. n n证证(Euler证法) 不妨设n个不同元素分别为1, 2, , n. 可重复选取的r个元素为c1, c2, , cr, 可设c1c2cr. 记d1 = c1, d2 = c2+ 1, , dr = cr+ (r - 1), 于是得到另外一个组合d1, d2, , dr. 显然, n n是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
9、个不同的元素的r-组合, 其个数为n n容易证明, n个元素的r-可重组合个数与不定方程n n的非负整数解的个数相同. 利用这一点, 可以证明：若n个元素的r-可重组合中每个元素至少出现一次, 则r n且这样的组合个数为 n n例例8-1 从为数众多的一元币、五元币、十元币、五十元币和一百元币中选取6张出来，有多少种选取方式？ n nSolution n n根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合, 其组合个数为n n与组合有关的恒等式有近1000个,下面是常用的三个组合恒等式,可采用组合的计算公式定理8-3加以证明,也可以根据组合的意义进行“组合证
10、明”. n n(1) 对称公式对称公式n n(2) 加法公式加法公式 n n(3) 移进移出公式移进移出公式n n3 二项式定理二项式定理n n与组合密切相关的是下述二项式定理.n n定理定理8-5(二项式定理二项式定理) 设n为正整数, 则对于任意x和y, 有 n n正因为这样，组合数又称为二项式系数二项式系数. 根据二项式定理，有n n思考思考 将所有n个元素的r-排列和r-组合列举出来的方法. n n作业 1,2,3,4.8.2 生成函数生成函数n n前面从计数的加法原理和乘法原理出发，介绍了前面从计数的加法原理和乘法原理出发，介绍了排列组合的概念以及一些计算其个数的公式排列组合的概念以
11、及一些计算其个数的公式. . n n生成函数生成函数生成函数生成函数(generating function)(generating function)又称为母函数，它又称为母函数，它是解决满足一定要求的排列组合计数问题的一种是解决满足一定要求的排列组合计数问题的一种重要工具重要工具, , 也是求解递归关系的一种工具也是求解递归关系的一种工具. . n n利用生成函数解决计数问题的基本思想就是将要利用生成函数解决计数问题的基本思想就是将要计算的个数计算的个数a ar r = = f f( (r r) ) 转化为一个关于转化为一个关于x x的函数，通的函数，通过对过对x xr r或或 的系数的讨
12、论得出结论的系数的讨论得出结论( (r r = 0, 1, 2, = 0, 1, 2, ).). n n8.2.1 组合计数生成函数组合计数生成函数n n定义定义8-1 对于数列a0，a1，ar，其组合计数生成函数组合计数生成函数(ordinary generating function)为n n(形式)幂级数?n n(1) 设n个元素的r-组合个数为ar，r = 0, 1, 2, . 显然, 有 n n其组合计数生成函数为n n于是, ar就是其组合计数生成函数 中xr的系数且 n n实际上, 中第i个(1 + x)可理解为n个元素中的第i个元素，其中的“1”表示在组合中不取第i个元素，“x
13、”表示在组合中选取了第i元素(i = 1, 2, , n). n n(2) 设n个元素的r-可重组合个数为ar，r = 0, 1, 2, . 显然,有n n特别地a0 = 1. 现考虑 n n其展开式中xr来源于第一个括号(1 + x + x2 + )中的 , 第二个括号(1 + x + x2 + )中的 , , 第n个括号(1 + x + x2 + )中的 的乘积，即n n这时, n n该不定方程的非负整数解的个数即为 换句话说,有 n n因此, 上式右边展开式中xr的系数就是ar.实际上， n n中的第i个(1 + x + x2 + ) 可理解为n个元素中的第i个元素, 其中的“1”表示在
14、组合中不取第i个元素, “x”表示在组合中第i个元素取一次, “x2”表示在组合中第i个元素取了两次, “x3”表示在组合中第i个元素取了三次, , (i = 1, 2, , n). n n上述思想还可以推广, 例如在组合计数生成函数中出现乘积项(x2 + x4)，则表示对应的元素可取两次或四次. n n(1)n n(2)n n(m为实数). n n(3)n n下面通过例子说明如何利用组合计数生成函数解决一般的组合计数问题. n n例例8-2 一口袋中有5个红球, 3个黄球, 绿、白、黑球可任意多提供. 现从中取3个球, 有多少种选取方式?n nSolution 设取r个球的方法有ar种(r
15、= 0, 1, 2, ), 则组合计数生成函数 n n例例8-3 现有2n个A, 2n个B, 2n个C, 求从它们中选出3n个字母的方式数. n nSolution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数n n2 排列计数生成函数排列计数生成函数n nDef 8-2 对于数列a0, a1, , ar, , 其排列排列计数生成函数计数生成函数(exponential generating function)为n n这时, 排列个数ar是 的系数. n n可以证明下述定理.n nTheorem 8-6 设A1 , A2 , , Ak是k个不同元素, 现有ni个
16、Ai元素(i = 1, 2, , k, n1 + n2 + + nk = n), 则在这n个元素中任取r个元素的排列个数为ar, 则其排列计数生成函数为n n实际上, 上式右边的第i个括号表示第i个元素, 其中的“1”表示不取第i个元素, “x”表示第i个元素取了一次用来排列, “ x2/2!”表示第i个元素取了两次用来排列, , “ ”表示第i个元素取了ni次用来排列, 当然第i个元素最多取ni次(i = 1, 2, , k). n n若一个元素在排列中至少取两次, 至多取五次, 则在排列计数生成函数中应出现 n n乘积项. n n利用该思想可以解决很多的排列计数问题.n n例例8-4 用0
17、, 1, 2, 3, 4五个数字, 求可组成六位数的个数, 其中0恰出现一次, 1出现两次或三次, 2不出现或出现一次, 3没有限制, 4出现奇数次. n nSolution 先计算不出现0的满足其余条件的五位数个数. n n设不出现0的满足其余条件的r位数个数为ar，则排列计数生成函数n n由于在满足要求的六位数中, 0恰出现一次, 而由所求出的每个五位数可得到5个不同的六位数, 如由12134可得到121340, 121034, 121304, 120134, 102134, 故满足要求的六位数有140 5 = 700. n n例例8-5 将n个点排成一条直线, 用红、白、黑三种颜色对其任
18、意涂色, 要求同色点为偶数(包括0), 有多少种涂法?n nSolution 这是一个排列问题, 设排成一行的r个点满足要求的涂法有ar种, r = 0, 1, 2, , 则排列计数生成函数n n作业 习题8.2 15.8.3 递归关系递归关系n n还有一些计数问题可以归结到建立和求解递归关系还有一些计数问题可以归结到建立和求解递归关系. . 在学在学习数列时，有时会出现数列的后项是由前项或前几项确定习数列时，有时会出现数列的后项是由前项或前几项确定的，这实际上就是递归关系，又称为递推关系的，这实际上就是递归关系，又称为递推关系. .n n利用递归关系解决计数问题是很重要的方法之一，在其他利用
19、递归关系解决计数问题是很重要的方法之一，在其他数学分支中都会用到此技巧数学分支中都会用到此技巧. . 就计算机科学来说，大多数就计算机科学来说，大多数算法的执行都表现为按某种条件重复地执行一些循环，而算法的执行都表现为按某种条件重复地执行一些循环，而这些循环经常可以用递归关系来表达这些循环经常可以用递归关系来表达. . 因此，递归关系的因此，递归关系的建立和求解对算法分析来讲就变得至关重要建立和求解对算法分析来讲就变得至关重要. .n n本节先举例说明如何建立递归关系，再给出常用的求解递本节先举例说明如何建立递归关系，再给出常用的求解递归关系的方法归关系的方法. . 部分内容讨论涉及到高等数学
20、中幂级数及部分内容讨论涉及到高等数学中幂级数及其运算等有关内容其运算等有关内容. . n n1 递归关系的概念递归关系的概念n n如果一个问题可以归结到其前面一个问题或前面一些问题, 这就是递归问题, 递归递归(recurrence)又称为递推. n n在知道a0 = 1时, 对于任意正整数n,定义an = nan-1,这实际上是阶乘函数的递归定义或者说借助于递归给出集合 a0, a1, an,的定义, an的计算归结到其前面的一个an-1的计算,这时an = nan-1就是一个递归关系,或称为递归方程,或递归函数,其中a0 = 1称为初始条件或边界条件. n n给定数列a0, a1, , a
21、n , , 该数列中除有限项以外的任何项an与其前面一项或前面一些项的一个方程称为递归递归关系关系(recurrence relation), 它表示an与其前面一项或前面一些项的一种关系. n n为了求解该递归关系, 所给出的一些条件称为初始条件初始条件(initial condition). n n对于数列a0, a1, , an , ,需要一定的技巧才能得出其递归关系, 要知道an是n的一个解析表达式f(n)有时也是比较困难的, 它通常由其初始条件和递归关系来确定. n n我们现在感兴趣的是得出an是n的解析表达式, 虽然一般情况下很难办到这一点. n n下面是根据具体问题建立递归关系的
22、两个例子. n n例例8-6(汉诺塔汉诺塔, Hanoi tower) n n(1) 一次只能移动一个金盘;n n(2) 金盘只能在三根宝石针上存放;n n(3) 不允许将大金盘放在小金盘上. n n假设n是金盘的数目(如n = 64), hn按规则需要移动的次数,求hn的初始条件及递归关系. n nSolution 显然, 初始条件为h1 = 1. n n当有n个金盘时, 可以先将宝石针A最上面的n - 1个金盘按规则移动另外一根宝石针上, 可设为B, 需要移动hn 1次. 再将A上最大的金盘移动到C, 移动一次. 最后将宝石针B上的n - 1个金盘按规则移动到C, 要移动hn 1次. n
23、n根据加法原理, 有递归关系n n例例8-7(斐波那契数列斐波那契数列,Fibonacci sequence) n nSolution 显然,初始条件为F1 = 1, F2 = 1. n nFn = 第n个月大兔子的对数 + 第n个月小兔子的对数, n n而第n个月大兔子的对数 = 第n - 1个月兔子的对数Fn -1, n n第n个月小兔子的对数 = 第n 1大兔子的对数 = 第n 2兔子的对数Fn -2, n n见图8-3, 其中实心点表示大兔子对, 空心点表示小兔子对. n n2 常用的递归关系求解方法常用的递归关系求解方法n n1. 递归法递归法n n递归法又称为递推法, 是将对数列第
24、n项an的计算转化为对其前面的一个项或一些项的计算, 直到最后归结到初始条件. n n例例8-8 在h1 = 1时, 求解递归关系n nSolution n n另解另解 由于h1 = 1且hn = 2hn 1 + 1，于是h2 = 2h1 + 1 = 3 = 22 1. 进而有h3 = 2h2 + 1 = 7 = 23 1, , hn = 2n - 1. n n迭代法与递归法是不同的. n n当n = 64时, n nh64 = 264 - 1 = 18,446,744,073,709,551,615.n n若移动一次只需用1s，约需5845亿年. n n2. 生成函数法生成函数法n n(1)
25、 根据所给数列构造其生成函数；n n(2) 利用递归关系以及已知函数的形式幂级数求出该生成函数；n n(3) 想办法得出生成函数中xn或 xn /n!的系数即为所求an. n n例例8-8 在初始条件a1 =1, a2 = 1下, 求解递归关系n nSolution n n由数列a1, a2, , an, , 构造组合计数生成函数 n n例例8-9 在初始条件D0 =1下, 求解递归关系(n 1)n nSolution 由数列D0, D1, , Dn, , 构造排列计数生成函数n n3. 特征方程法特征方程法n n对于常系数线性递归关系, 可以考虑用特征方程法求解. 分两种情况分别进行讨论.n
26、 n(1) 常系数线性齐次递归关系常系数线性齐次递归关系n n设k为正整数, 在初始条件a0, a1, , ak-1下，递归关系n n称为k阶常系数线性齐次递归关系阶常系数线性齐次递归关系(linear homogeneous recurrence relation of order k with constant coefficient), 其中c1, c2, , ck为常数且ck 0. n nk阶常系数线性齐次递归关系的特征方程特征方程(characteristic equation)定义为n nTheorem 8-7 若递归关系n n的特征方程有k个不同的根n n则其通解为n n给定初始
27、条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.n n例例8-10 在初始条件F1 = 1, F2 = 1下, 求解递归关系Fn = Fn 1 + Fn 2 (n 3). n nSolution 递归关系Fn = Fn 1 + Fn 2的特征方程为n n其根为 n nTheorem 8-8 若递归关系n n的特征方程有t个不同的根n n其重数分别为n n则其通解为n n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.n n例例8-11 在初始条件a0 = 1, a1 = 2, a2 = 7下, 求解递归关系n nS
28、olution 递归关系的特征方程为n n其根为n n于是n n(2) 某些常系数线性非齐次递归关系某些常系数线性非齐次递归关系n n设k为正整数, 在初始条件a0, a1, , ak-1下，递归关系n n称为k阶常系数线性非齐次递归关系阶常系数线性非齐次递归关系(linear non-homogeneous recurrence relation of order k with constant coefficient), 其中c1, c2, , ck为常数且ck 0, 非齐次项f(n) 是关于n的函数且f(n) 0. n n对于一般的非齐次项f(n)没有统一的求解方法. 一般情况下有下述定
29、理. n nTheorem 8-9 若k阶常系数线性非齐次递归关系有特解bn, 且对应的k阶常系数线性齐次递归关系n n的通解为Bn, 则通解为n n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.n n例例8-12 在初始条件a1 = 2下, 求解递归关系n nSolution 因为 n n例例8-13 求n nSolution 根据题意, 有 n n4. 其他方法其他方法n n例例8-14 在初始条件f(1) =1下, 求解递归关系n n其中n = 2k, k为正整数. n nSolution 令n n于是原递归关系变为 n n作业 习题8.3 (单数或双数)
