组合数学(第4章4.3).ppt

第四章：生成排列和组合,4.4 生成r-组合 4.5 序关系 北京航空航天大学,主要内容,生成r-组合算法 偏序和等价关系,4.4 生成r-组合,集合1,2,3,4的2-组合： 1，2； 1，3; 2，3; 1，4; 2，4; 3，4 字典序：令S=1,2,n, 设A，B是S的两个r-组合，若ABAB中的最小整数属于A，则称A先于B。,S的r-组合可写成如下形式： a1,a2,ar 其中， 1a1a2,ar n 可按字典排序方式排列。,例,S=1,2,3,4,5,6,7,8,9的5-组合按字典序的第一个是：12345, 最后一个：56789 12389的后继是12456,定理4.41,令a1a2ar是1,2,n的一个r-组合, 在字典序中, 第一个r-组合是12r, 最后一个r-组合是(n-r+1) (n-r+2)n, 设a1a2ar (n-r+1) (n-r+2)n。令k是满足akn且使得ak+1不同于a1a2ar中任一数的最大整数。那么, 在字典序中, a1a2ar的直接后继是a1a2ak-1 (ak+1)(ak+r-k+1).,证明：第一个1,2,r; 最后一个(nr+1) (nr+2)n由定义可知。 设a1a2ar不是最后一个r-组合，确定k使得akn且ak+1不同于a1a2ar中任一数的最大整数。有两种情况： （1）k=r时, ar=akn; （2）kr时, ak+2=ak+1+1, ak+3=ak+2+1, , ar=n。,那么， a1a2ar a1ak1ak (nr+k+1) (nr+k+2 )n. 其中，ak+1 ak+1=nr+k+1。 因此，a1a2ar是以a1ak1ak开始的最后的r-组合。而a1ak-1(ak+1)(ak+2)(ak+r-k+1)是以a1ak1(ak+1)开始的第一个r-组合，结论成立。,字典序r-组合生成算法,初始： a1a2ar12r 当a1a2ar (nr+1) (nr+2)n时，Do 1）确定最大整数k, 使得ak+1 n，且ak+1ai (i=1,2,r) 2) 用a1a2ak-1 (ak+1)(ak+rk+1)替换a1a2ar.,例,应用算法生成1,2,6的4-组合. 12341235123612451246 12561345134613561456 23452346235624563456,定理4.4.2,1,2,n的r-组合a1a2ar出现在1,2,n的r-组合中的字典序中的位置号如下：,证明：计算在a1a2ar之后r-组合个数。 1) 在a1a2ar后面存在 个组合，使得其第一个元素大于a1. 2）在a1a2ar后面存在 个组合，其第一个元素是a1，第二个元素大于a2。 r)在a1a2ar后面存在 个组合，从a1a2ar-1开始，第r个元素大于ar。 而总数为 ，结论成立。,例. 求1,2,8的4-组合中1258的字典序位置。 解：1258的位置是：,4.5 偏序和等价关系,定义（关系）：设X是一个集合，X上的关系定义为XX上的子集，令关系R X X，若（a, b）R ,则称a和b有关系R，记为aRb; 否则称a和b没有关系R.,定义2,设R是X上的关系，那么R可能具有下列性质: 自反性: 若对 xX, 均有xRx; 反自反性: 若对 xX, 均有x x; 对称性: 对 x,yX, 若xRy, 则必有yRx; 反对称性: 对 x,yX, xy, 若xRy; 则必有y x; 传递性: 对 x,y,zX, 若xRy, yRz, 则必有xRz;,定义3,设R是X上的二元关系 偏序关系: 若R满足自反性, 反对称性和传递性, 则称R是X上的偏序关系. 记为” ”. 在其上定义了偏序关系的集合称偏序集, 记为(X, ). 严格偏序关系: 若R满足反自反性, 反对称性和传递性, 则称R是X上的严格偏序关系. 记为”. 全序关系: 对x,yX, 若xRy或yRx, 则称x和y是可比的, 否则称x和y是不可比的; 若偏序关系R使X中任两个元素都是可比的, 则R是X上的全序关系, 记为”, 此时(X, )称全序集. 等价关系: 若R满足自反性, 对称性和传递性, 则称R是X上的等价关系. 记为”或”=”.,定义4: 偏序集(P, )中, 设a,bP 覆盖: 若ab, 则称b是a的覆盖; 直接覆盖: 若ab, 且不存在xP, 使得ax, xb, 则称b是a的直接覆盖.,偏序集的几何表示,当b是a的直接覆盖时,b与a画一条线段, b在a的上方. 例. X=1, 2, 3, 画出偏序集(P(A), )的几何表示图。,全序集: x1 x2 x3 x4,例 :X=1, 2, 3, 4, 5, 6, 7, 8, ” ”定义为整除关系, 画出偏序集(P, )的图.,1,2,3,5,7,4,6,8,定义4: 偏序集(P, )中, 若 mP, 对 xP, 均有x m, 则称m是P的最大元.若nP, 对xP, 若n x, 则必有n=x, 称n是P的极大元. 性质: (1)偏序集未必存在最大元(最小元), 若存在必唯一；(2)有限偏序集一定存在极大元(极小元), 但未必唯一.,定理4.5.1 设X是n个元素的有限集, 那么, 在X的全序和排列之间存在一一对应. 特别地, X上的不同全序个数是n! . 证明：设是X上的一个全序, 对应到X的一个排列：a1, a2,an, 其中a1 a2an 对n归纳证明，n1时成立。 * 当n1，证明X对于存在极小元a1。,对集合Xa1应用归纳假设，得到与对应的一个排列a2,a3,an，满足 a2a3an， 那么，a1,a2,a3,an是X的一个排列。 反之，任何一个排列也对应一个全序。 证完。,定义5: 令1和2是集合X上的两个偏序, 对于a,bX,若有a1b, 则必有a2b, 那么称偏序集(X, 2)是偏序集(X, 1)的扩张. 一个偏序可以扩张为一个全序。,定理4.5.2 令(X, )是一个有限偏序集, 则存在X上的线性序, 使得(X, )是(X, )的一个扩展. 证明：偏序的线性扩展算法，对集合 X=x1,x2,xn的排序问题，满足：若xi xj, 则排序xi先于 xj 。,算法描述,1）选出X的一个极小元x1. 2）求出集合Xx1的极小元x2。 n) 剩下元素xn. 可证明x1,x2,xn是(X, )的线性扩展。,证明：,需要证明对ij有 xixj。 反证法。假设存在xjxi， ij，注意到算法中xi先于xj选出，因此，由算法xi是包含了xj的集合的极小元，与xjxi矛盾。,例4：X=1,2,3,4,5,6,7,8, “”定义为整除关系, 确定(X, )的一个线性扩展.,1,2,3,5,7,4,6,8,等价关系与划分,定义6: 对于X中每一个元素a, a的等价类定义为所有与a等价的元素构成的集合.记为a=x xX , xa . 例：整数集Z中，模m同余是等价关系。那么，有m个等价类：0,1,m-1. 其中，0=km| kZ 1=lm+1| lZ,定理4.5.3 X的全部等价类构成X的一个划分, 反之, X的任一个非空划分对应X的一个等价类. 证明：(1) 由一个等价关系构造X的一个划分。每个等价类非空，且对xX, xx,