资源描述:
《组合数学(第4章4.3).ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第四章:生成排列和组合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其中,1a12、是12456定理4.41令a1a2…ar是{1,2,…,n}的一个r-组合,在字典序中,第一个r-组合是12…r,最后一个r-组合是(n-r+1)(n-r+2)…n,设a1a2…ar(n-r+1)(n-r+2)…n。令k是满足ak3、整数。有两种情况:(1)k=r时,ar=ak4、,使得ak+1n,且ak+1ai(i=1,2,…,r)2)用a1a2…ak-1(ak+1)…(ak+rk+1)替换a1a2…ar.例应用算法生成{1,2,…,6}的4-组合.123412351236124512461256134513461356145623452346235624563456定理4.4.2{1,2,…,n}的r-组合a1a2…ar出现在{1,2,…,n}的r-组合中的字典序中的位置号如下:证明:计算在a1a2…ar之后r-组合个数。1)在a1a2…ar后面存在个组合,使得其第一个元素大于a1.2)在a1a2…a
5、r后面存在个组合,其第一个元素是a1,第二个元素大于a2。…r)在a1a2…ar后面存在个组合,从a1a2…ar-1开始,第r个元素大于ar。而总数为,结论成立。例.求{1,2,…,8}的4-组合中1258的字典序位置。解:1258的位置是:4.5偏序和等价关系定义(关系):设X是一个集合,X上的关系定义为XX上的子集,令关系RXX,若(a,b)∈R,则称a和b有关系R,记为aRb;否则称a和b没有关系R.定义2设R是X上的关系,那么R可能具有下列性质:自反性:若对x∈X,均有xRx;反自反性:若对x∈X,均有xx;对称性:对x,y∈X,若xRy,则
6、必有yRx;反对称性:对x,y∈X,xy,若xRy;则必有yx;传递性:对x,y,z∈X,若xRy,yRz,则必有xRz;定义3设R是X上的二元关系偏序关系:若R满足自反性,反对称性和传递性,则称R是X上的偏序关系.记为””.在其上定义了偏序关系的集合称偏序集,记为(X,).严格偏序关系:若R满足反自反性,反对称性和传递性,则称R是X上的严格偏序关系.记为”<”.全序关系:对x,y∈X,若xRy或yRx,则称x和y是可比的,否则称x和y是不可比的;若偏序关系R使X中任两个元素都是可比的,则R是X上的全序关系,记为””,此时(X,)称全序集.等价关系
7、:若R满足自反性,对称性和传递性,则称R是X上的等价关系.记为”~”或”=”.定义4:偏序集(P,)中,设a,b∈P覆盖:若a
8、义4:偏序集(P,)中