第20讲组合计数.ppt

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