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

《组合数学(第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-组合，若ABAB中的最小整数属于A，则称A先于B。S的r-组合可写成如下形式：a1,a2,…,ar其中，1a1

2、是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是满足ak

3、整数。有两种情况：（1）k=r时,ar=ak

4、,使得ak+1n，且ak+1ai(i=1,2,…,r)2)用a1a2…ak-1(ak+1)…(ak+rk+1)替换a1a2…ar.例应用算法生成{1,2,…,6}的4-组合.123412351236124512461256134513461356145623452346235624563456定理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上的关系定义为XX上的子集，令关系RXX，若（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,xy,若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,)中